[분할 정복] Divide & Conquer

주어진 문제를 둘 이상의 부분 문제로 나누고

각 문제에 대한 답을 재귀 호출을 이용해 계산

각 부분 문제의 답으로부터 전체 문제의 답을 계산

 

문제를 거의 같은 크기의 부분문제로 나눈다.

 

세가지 구성요소

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

 

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

 

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

 

 

 

자연스러운 방법으로 나누고

나눈 문제의 답을 조합해 원래 문제의 답을 계산하는 

효율적인 방법이 필요

 

어떻게 분할하느냐에 따라 시간 복잡도 차이가 커짐

(부분 문제가 중복된다 overlapping subproblems)

 

같은 아이디어로 정렬을 수행하지만

시간이 많이 걸리는 작업을

분할 단계에서 하느냐,

병합 단계에서 하느냐에 따라

다른 알고리즘이 될 수 있음.(merge sort, quick sort)

 

 

-알고리즘 문제해결전략 175p