문제를 같은 모양의 더 작은 문제로 나누고(분할, Divide), 각각을 풀고(정복, Conquer), 그 결과를 합쳐(결합, Combine) 원래 문제를 푸는 방식. 대개 재귀로 표현하고, 나눌 때마다 크기가 절반으로 줄면 log n 단계 만에 바닥에 닿는다.
- 이진 탐색: 가운데와 비교해 절반을 버린다. 결합 단계가 없는 가장 단순한 형태로
O(log n) - 병합 정렬: 반으로 나눠 각각 정렬한 뒤 합친다.
O(n log n) - 퀵 정렬: 피벗 기준으로 나눈 뒤 각각 정렬한다. 결합이 필요 없다
- 큰 수 곱셈, 가장 가까운 두 점 찾기, 행렬 곱셈 같은 고전 문제도 이 방식으로 빨라진다
동적 프로그래밍과의 차이
나눈 부분 문제들이 서로 겹치지 않으면 분할 정복, 같은 부분 문제가 반복해서 나오면 결과를 저장해 재사용하는 동적 프로그래밍이 맞다. 피보나치를 단순 재귀로 나누면 같은 계산을 수없이 반복하는 것이 그 예다.
다른 패턴은 알고리즘 문제 풀이 접근법, 복잡도 계산은 빅오 표기법.