분할 정복
문제를 더 작은 동일한 형태의 부분 문제로 나누고(divide), 각각을 재귀적으로 해결한 뒤(conquer), 그 결과를 합쳐(combine) 전체 문제를 해결하는 알고리즘 설계 기법입니다.
동작 과정
예시: 배열 [6, 2, 9, 4, 7, 1, 8]에서 최댓값 찾기.
divide: 배열을 절반으로 쪼갠다
[6, 2, 9, 4, 7, 1, 8]
→ [6, 2, 9, 4] / [7, 1, 8]
→ [6, 2] [9, 4] / [7, 1] [8]
→ [6][2] [9][4] / [7][1] [8]
conquer: 원소가 1개면 그 자체가 최댓값
[6] [2] [9] [4] [7] [1] [8]
combine: 두 부분의 최댓값끼리 비교하며 올라간다
[6][2] → max(6,2)=6 [9][4] → max(9,4)=9
[7][1] → max(7,1)=7 [8] → 8
[6,2]max=6, [9,4]max=9 → max(6,9)=9
[7,1]max=7, [8]max=8 → max(7,8)=8
최종: max(9, 8) = 9
최댓값은 선형 탐색만으로도 O(n)에 구할 수 있어 분할 정복을 쓸 이유는 없지만, divide → conquer → combine 3단계 구조를 가장 단순하게 보여주는 예시입니다. 분할 정복이 실제로 이득을 보는 경우는 부분 문제를 합치는 비용이 작고, 분할을 거듭할수록 문제 크기가 로그 단계로 줄어들 때입니다. 병합 정렬, 퀵 정렬, 이진 탐색이 대표적인 예입니다.
구현
int findMax(int[] arr, int left, int right) {
if (left == right) {
return arr[left];
}
int mid = (left + right) / 2;
int leftMax = findMax(arr, left, mid);
int rightMax = findMax(arr, mid + 1, right);
return Math.max(leftMax, rightMax);
}
복잡도
분할 정복의 전체 복잡도는 점화식 T(n) = a·T(n/b) + f(n) (마스터 정리)으로 분석합니다. a는 재귀 호출 횟수, n/b는 부분 문제의 크기, f(n)은 분할·결합에 드는 비용입니다.
| 알고리즘 | 점화식 | 시간 복잡도 |
|---|---|---|
| 위 최댓값 찾기 | T(n) = 2T(n/2) + O(1) | O(n) |
| 병합 정렬 | T(n) = 2T(n/2) + O(n) | O(n log n) |
| 이진 탐색 | T(n) = T(n/2) + O(1) | O(log n) |
공간 복잡도는 보통 재귀 깊이에 비례해 O(log n)이다. 단 병합 정렬처럼 결합 단계에서 별도 배열이 필요하면 추가로 O(n)이 든다.
주의사항
- 항상 빠른 것은 아니다: 부분 문제로 나누거나 결과를 합치는 비용이 크면 오히려 느려질 수 있다. 최댓값 찾기처럼 선형 탐색 하나로 충분한 문제를 분할 정복으로 풀면 재귀 호출 오버헤드만 늘어난다
- 재귀 깊이와 스택 오버플로: 분할이 균등하지 않으면(퀵 정렬의 최악 케이스처럼) 재귀 깊이가 O(n)까지 커져 스택 오버플로가 날 수 있다
- 동적 계획법과의 차이: 분할 정복은 부분 문제들이 서로 겹치지 않는다고 가정하지만(독립적), DP는 겹치는 부분 문제를 캐싱해 재사용한다. 피보나치수열처럼 겹치는 부분 문제를 그대로 분할 정복으로 풀면 중복 호출이 기하급수적으로 늘어나 비효율적이다