분할 정복 알고리즘
추파춥스는 빨아먹는데 30분이 걸리지만, 깨뜨려서 잘게 부수면 1분 안에도 먹는다.
사탕의 큰 덩어리를 작은 조각으로 나누면 더 넓은 표면을 입안에서 녹일 수 있기 때문이다.
분할 정복 알고리즘은 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘이다.
•
퀵정렬은 임의의 기준 요소 Pivot 을정하고 기준 요소보다 작은 요소들을 왼편으로, 큰 요소들을 오른편으로 옮긴다. 그 다음에는 기준 요소에 의해 나누어진 양 편에 있는 요소들에 대해 왼쪽/오른쪽에 대하여 각각 분할을 수행한다. 이렇게 분할된 데이터 집합들을 더이상 분할 할 수 없을 때까지 계속 분할한다.
알고리즘
1.
분할 (Divide/Break) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다.
2.
정복 (Conquer/Solve) : 하위 문제가 여전히 분할이 가능한 상태라면 하위 집합에 대해 1을 수행한다. 그렇지 않은 경우 하위 문제를 해결한다.
3.
결합 (Merge/Combine) : 2 과정에서 정복된 답을 취합한다.
분할 정복 알고리즘의 핵심은 “문제를 나누는 것" 이 가장 중요하다.
