분할 정복은 말 그대로 문제를 1. 분할 과 2.정복으로 나눠서 해결하는 것을 말한다.

분할하는 단계에서는 말 그대로 주어진 문제를 여러 개의 부분 문제들로 나누는데, 문제가 작아지면 작아질 수록 풀기 쉬워지는 성질을 이용하는 것이다.

또 문제의 크기가 줄어든다면 답을 구할 수 있는 수준이 되고, 이게 재귀호출로 문제를 풀때의 기저 사례(base case)와 같다.

대체로 분할 정복은 재귀호출과 아죽 잘 맞는다. 그리고 기저 사례들로 각 문제의 답을 풀고 그 문제들을 불렀던 조금 더 큰 문제는 이 답들을 통해 비교적 간단한 연산처리로 자신의 답을 구할 수 있습니다. 이런 방식으로 첫 문제까지 쌓아 올라가며 답을 풀어내는 것이 최종 목적이다.

그냥 풀었을 때 보다 오히려 할 일이 많아지지 않을까 생각할 수 있는데, 분할 정복 기법이 먹히는 경우는, 그냥 풀었을 때보다 저렇게 이미 풀린 부분 문제들을 합치는게 월등히 빠른 경우 입니다.

아주 대표적인 예가 병합정렬, 이분 탐색, 거듭제곱 연산이다.

분할 정복 알고리즘의 수행시간은 문제마다 다른데 여기서 필요한건 분할할 때

• 나눠지는 문제의 개수
• 분할 후 문제의 크기
• 각 문제마다 병합 단계에서 걸리는 시간

이 수행 시간을 결정한다.

이분 탐색은 특이하게도 병합과정이 없는데 그 이유는 분할을 하지만 그 중 한문제만 풀면 되기 때문입니다.