**분할 정복(Divide and Conquer)**은 복잡하고 큰 문제를 해결 가능한 작은 문제들로 분할하여 각각 해결(정복)한 후, 그 결과들을 결합하는 알고리즘 설계 패러다임입니다.
1. 분할 정복의 3단계 문제 해결 과정
- 분할 (Divide): 입력 문제를 동일한 유형의 더 작은 부분 문제들로 나눈다.
- 정복 (Conquer): 부분 문제들을 재귀적으로 해결한다. (부분 문제 크기가 충분히 작다면 직접 해를 구함)
- 결합 (Combine): 구해진 부분 문제의 해들을 합쳐 원래 문제의 해를 만든다.
2. 대표적 응용 예시: 거듭제곱 $a^n$ 구하기
일반 반복문으로 $a^n$을 구하면 $O(N)$시간이 걸리지만, 분할 정복을 적용하면 $O(log N)$ 만에 계산 가능합니다.
$$a^n = egin{cases} (a^{n/2})^2 & ext{if } n ext{ is even} \ a imes (a^{(n-1)/2})^2 & ext{if } n ext{ is odd} end{cases}$$
def power(a, n):
if n == 0:
return 1
half = power(a, n // 2)
if n % 2 == 0:
return half * half
else:
return a * half * half
print(power(2, 10)) # 1024
3. 분할 정복 대 대표적 알고리즘
- 병합 정렬 (Merge Sort): 배열을 정확히 2등분으로 분할 ($O(N log N)$).
- 퀵 정렬 (Quick Sort): 피봇을 기반으로 비대칭 분할 후 정렬.
- k-번째 작은 수 찾기 (Quick Select): 축소 정복(Decrease-and-Conquer) 형태로 한쪽 서브 배열만 탐색하여 평균 $O(N)$ 시간에 $k$번째 요소를 탐색.
4. 자주 묻는 질문 (Q&A)
Q. 분할 정복과 동적 계획법(DP)의 결정적 차이는 무엇인가요? A. 분할 정복은 나뉘어진 부분 문제들이 서로 독립적(Disjoint)일 때 사용합니다. 반면, 부분 문제들이 서로 중복(Overlapping)될 때는 동적 계획법(DP)을 사용하여 계산 결과를 재사용해야 합니다.