분할 정복
분할 정복 (Divide and Conquer)
분할 정복(Divide and Conquer)은 해결하기 어려운 복잡한 문제를 여러 개의 작은 부분 문제로 나눈 뒤, 각 부분 문제의 해를 구하고, 그 해들을 결합하여 최종적으로 원래 문제의 해를 구하는 알고리즘 설계 패러다임입니다. 이름 그대로 '나누고(Divide) 정복(Conquer)한다'는 개념입니다.
🧩 분할 정복의 3단계
1. 분할 (Divide) > * 원래 문제를 해결 가능한 가장 작은 단위까지 재귀적으로 분할합니다. > * 부분 문제들은 원래 문제와 동일한 유형이어야 합니다.
2. 정복 (Conquer) > * 부분 문제들이 충분히 작아져서 더 이상 나눌 수 없을 때, 직접적으로 해를 구합니다. (보통 재귀의 기본 사례(Base Case)에 해당) > * 나누어진 부분 문제들을 재귀적으로 호출하여 해결합니다.
3. 결합 (Combine) > * 정복된 부분 문제들의 해를 통합하여, 원래 문제의 해를 구합니다. 이 결합 과정이 알고리즘의 핵심이 되는 경우가 많습니다.
🆚 다른 알고리즘 패러다임과의 비교
- 동적 계획법 (Dynamic Programming)과의 차이
> * '공통점': 복잡한 문제를 작은 부분 문제로 나누어 푼다는 점에서 유사합니다. > * '차이점': > > * 부분 문제의 중복 : 분할 정복은 나누어진 부분 문제들이 서로 '독립적'이지만, DP는 '중복'되는 경우가 많습니다. > > * 해결 방식 : 분할 정복은 Top-down(재귀) 방식으로 문제를 해결하고, DP는 Bottom-up(반복문) 또는 Top-down(메모이제이션) 방식으로 해결합니다. DP는 중복 계산을 피하기 위해 부분 문제의 해를 저장합니다.
- 그리디 알고리즘 (Greedy Algorithm)과의 차이
> * 그리디 : 매 순간 최적의 선택을 하며, 이 선택을 번복하지 않습니다. 전체적인 그림을 보지 않습니다. > * 분할 정복 : 문제를 나누고 그 해를 다시 조합하는 과정에서 전체적인 해를 구합니다.
💡 개발자 핵심 Point
- 분할 정복은 재귀적인 구조를 가지므로, 재귀 함수로 구현하는 것이 자연스럽습니다.
- 시간 복잡도 : 분할 정복 알고리즘의 시간 복잡도는 보통 점화식(Recurrence Relation)으로 표현되며, 마스터 정리(Master Theorem)를 통해 쉽게 계산할 수 있습니다. `T(n) = aT(n/b) + f(n)`
- 대표적인 분할 정복 알고리즘
> * 병합 정렬 (Merge Sort) : 배열을 절반으로 나누고(Divide), 각 부분을 정렬한 뒤(Conquer), 정렬된 두 부분을 병합(Combine)합니다. > * 퀵 정렬 (Quick Sort) : 피벗을 기준으로 배열을 두 부분으로 나누고(Divide), 각 부분을 정렬(Conquer)합니다. (별도의 결합 과정은 필요 없음) > * 이진 탐색 (Binary Search) : 탐색 범위를 절반으로 나누어(Divide), 한쪽 부분만 탐색(Conquer)합니다. > * 거듭제곱 계산 : `x^n`을 계산할 때, `x^(n/2) * x^(n/2)`으로 나누어 계산합니다.
