분할 정복(Divide and Conquer)
다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임
- 문제를 재귀적으로 쪼개어 간단한 문제로 분할
- 간단해진 하위 문제의 결과들을 조합하여 원래 문제의 결과로 변환
- 예) 병합 정렬, 최적 부분 구조(Optimal Substructure)
| 분할 | 문제를 동일한 유형의 여러 하위 문제로 분할 |
| 정복 | 가장 작은 단위의 하위 문제를 해결하여 정복 |
| 조합 | 하위 문제의 결과를 원래 문제에 대한 결과로 조합 |
출처) 파이썬 알고리즘 인터뷰(박상길 저)