분할 정복(Divde & Conquer)

분할 정복(divide & conquer)은 가장 유명한 알고리즘 디자인 패러다임 중 하나 이다.
분할 정복은 하나의 큰 문제를 작은 subproblem들로 나누고, 작은 subproblem들을 해결해 나간다는 점에서 각개 격파라고도 불린다.
분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤, 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다.
ex) quick sort, 피보나치 수열.
일반 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 것이 아니라, 문제를 거의 같은 크기의 부분 문제로 나누고 해결한다는 것이다.

분할 정복 구성 요소.

분할 정복의 요소는 크게 세가지이다.
1. 문제를 더 작은 문제로 분할하는 과정 (divde)
2. 각 문제에 대한 구한 답을 원래 문제에 대한 답으로 병합 (merge)
3. 더 이상 답을 분할하지 않고, 곧장 풀 수 있는 매우 작은 문제 (base case)

위와 같이 나눈다면, 분할 정복은 많은 경우 같은 작업을 더 빠르게 처리할 수 있도록 도와준다.

분할 정복으로 풀 수 있는 문제.

병합 정렬과 퀵 정력.

병합 정렬 - 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개로 만든 뒤 이들을 재귀 호출을 이용해 정렬한다. 정렬된 배열을 일렬로 합치면, 전체 수열이 정렬된다.

퀵 정렬 - 배열 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요없도록, 한 쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할한다. pivot을 정해서 pivot보다 큰 수 작은 수로 나눈다.

병합 정렬에서 반으로 나누는 시간은 O(1)이 걸린다. 그리고 합치는 시간은 O(n)이 걸린다.
퀵 정렬 분할은 O(n)의 시간이 걸린다.
병합 정렬의 수행 시간은 두 수열의 길이 합 만큼 반복문을 수행하기 때문에, 병합 과정에 영향을 많이 받는다.

REFERENCE

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 - 구종만