분할 정복(Divide and Conquer)은 문제를 더 작은 부분 문제로 분할하고, 각 부분 문제를 재귀적으로 해결한 뒤 합병(Combine) 하는 알고리즘 설계 패러다임이다. 병합 정렬, 퀵 정렬, 이진 탐색, FFT가 대표 예다.
3단계
1. Divide — 문제를 부분 문제로 분할
2. Conquer — 부분 문제를 재귀적으로 해결
3. Combine — 부분 해를 합쳐 전체 해 도출
이진 탐색 (Divide & Conquer 관점)
[1, 3, 5, 7, 9] 에서 7 탐색
Divide: 중간값 5 기준으로 분할
→ 5 < 7이므로 오른쪽 [7, 9]만 탐색
Divide: 중간값 7 = 목표
Conquer: 인덱스 반환
병합 정렬 (T(n) = 2T(n/2) + O(n) = O(n log n))
python
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right) # Combine
마스터 정리 (복잡도 분석)
T(n) = aT(n/b) + f(n)
a=2, b=2, f(n)=O(n) → T(n) = O(n log n) (병합 정렬)
a=1, b=2, f(n)=O(1) → T(n) = O(log n) (이진 탐색)
관련 개념
- •정렬 알고리즘 — 분할 정복 기반 정렬
- •이진 탐색 — 분할 정복 탐색
- •동적 프로그래밍 — 겹치는 부분 문제 있을 때
참고문헌
- •Cormen et al. Introduction to Algorithms — Chapter 4
