분할정복

분할정복

2개 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 즉, 해를 구할 수 있을 만큼 충분히 나누어서 해결하는 방법이다.

하향식 접근법 (top-down)

[세가지 구성요소]

문제를 더 작은 문제로 분할하는 과정(divide)

각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case) 

 

 

분할의 의미로 전체 n을 반으로 나누어 생각할 수 있다(n/2).

병합을 의미하는 n번의 작업(b는 임의 상수).

 

[분할정복의 대표 알고리즘]

병합정렬, 퀵 정렬

 

[분할정복의 예]

아래 그림은 병합정렬의 진행 과정을 도식화 한 것입니다.

정렬되지 않은 값들을 반으로 계속 나누어 가면서 문제들을 최소한의 문제로 분할하는 과정을 거칩니다.
문제를 분할하고 난 다음 문제들을 병합으로서 해결을 합니다.

간단히 생각하면 분리된 문제들을 동일한 방식으로 해결하기 때문에 재귀호출이 반복적으로 일어나게 됩니다.
그런데 완전탐색(재귀를 통한 모든 해결법 수행)과 다른점은 문제의 분리를 통하여 같은 작업을 빠르게 처리해 준다는 점에 있습니다.