분할 정복은 문제를 더 작은 문제들로 나누어 해결하고 그 결과를 결합하는 알고리즘 설계 방법이다.
원리
분할 크기, 하위 문제 수, 결합 비용이 전체 성능을 결정한다. 재귀가 더 작은 입력으로 진행하는 조건과 직접 풀 수 있는 종료 조건을 정의한다.
예시
병합 정렬은 배열을 두 부분으로 나누어 정렬한 후 순서대로 합친다. 각 단계의 결합이 선형이고 단계 수가 로그 규모라 O(n log n)이 된다.
주의할 점
재귀를 사용한다는 사실만으로 분할 정복인 것은 아니다. 같은 부분 문제를 반복 계산한다면 동적 계획법이나 메모이제이션이 더 적절할 수 있다.