12.5 요약
1. 핵심 정리
- 분할 정복은 흔히 쓰이는 알고리즘 설계 전략이다. 분할(나누기)과 정복(합치기)의 두 단계로 이루어지며 보통 재귀로 구현한다.
- 분할 정복 문제를 판단하는 기준은 문제를 나눌 수 있는지, 부분 문제들이 독립적인지, 부분 문제의 해를 합칠 수 있는지다.
- 병합 정렬은 분할 정복 전략의 대표적인 응용이다. 배열을 같은 길이의 두 부분 배열로 재귀적으로 나누고, 원소가 하나만 남으면 단계적으로 병합하여 정렬한다.
- 분할 정복 전략을 도입하면 알고리즘 효율이 높아지는 경우가 많다. 연산 수를 줄일 수 있고, 시스템의 병렬 최적화에도 유리하기 때문이다.
- 분할 정복은 여러 알고리즘 문제를 해결할 뿐 아니라 자료 구조와 알고리즘의 설계에도 널리 사용되어 곳곳에서 찾아볼 수 있다.
- 적응형 탐색은 완전 탐색보다 효율적이다. 시간 복잡도가 \(O(\log n)\)인 탐색 알고리즘은 보통 분할 정복 전략을 기반으로 구현된다.
- 이진 탐색은 분할 정복 전략의 또 다른 대표적인 응용으로, 부분 문제의 해를 합치는 단계가 없다. 재귀적 분할 정복으로 이진 탐색을 구현할 수 있다.
- 이진 트리 구성 문제에서는 트리를 구성하는 원래 문제를 왼쪽 서브트리와 오른쪽 서브트리를 구성하는 부분 문제로 나눌 수 있다. 전위 순회와 중위 순회의 인덱스 구간을 나누어 구현한다.
- 하노이의 탑에서는 크기 \(n\)인 문제를 크기 \(n-1\)인 부분 문제 두 개와 크기 \(1\)인 부분 문제 하나로 나눌 수 있다. 세 부분 문제를 순서대로 해결하면 원래 문제도 해결된다.