분할 정복(Divide and Conquer)은 하나의 문제를 재귀적으로 여러 개의 동일한 유형을 가진 작은 하위 문제로 나누어, 쉽게 해결할 수 있도록 만드는 패러다임에 기반한 알고리즘입니다.
예시
분할 정복 기법을 더 깊이 이해하기 위해 간단한 예시를 살펴보겠습니다.
function recursive(input x size n)
if(n < k)
입력을 크기가 n/p인 m개의 하위 문제로 분할하고,
각 하위 문제에 대해 f를 재귀적으로 호출
else
x를 직접 해결한 뒤 반환
모든 하위 문제의 결과를 결합(Combine)하여 원래 문제의 최종 해답을 반환합니다.
설명 − 위 문제에서는 전체 문제 집합을 손쉽게 해결할 수 있는 더 작은 하위 문제들로 세분화하는 것이 핵심입니다.
마스터 정리(Master's Theorem)란?
분할 정복을 위한 마스터 정리는 재귀 관계(recurrence relation)로 표현된 알고리즘의 빅오(Big-O) 값을 도출하는 데 사용되는 분석 정리입니다. 알고리즘이 필요로 하는 시간을 계산하여 점근 표기법(asymptotic notation) 형태로 나타내는 데 활용됩니다.
앞선 예시에서 문제의 실행 시간은 다음과 같이 표현할 수 있습니다.
T(n) = f(n) + m.T(n/p)
대부분의 재귀 알고리즘은 마스터 정리를 통해 시간 복잡도를 구할 수 있지만, 일부 경우에는 마스터 정리가 적용되지 않습니다. 마스터 정리가 적용되지 않는 대표적인 경우는 다음과 같습니다.
- 문제 T(n)이 단조 증가(monotone) 함수가 아닌 경우 (예: T(n) = sin n)
- 문제 함수 f(n)이 다항식 형태가 아닌 경우
고급 마스터 정리(Advanced Master Theorem)
이러한 경우에 기존 마스터 정리는 효율적이지 못하기 때문에, 재귀적 점화식을 보다 폭넓게 처리할 수 있도록 고급 마스터 정리가 설계되었습니다. 고급 마스터 정리는 다음 형태의 점화식을 다룹니다.
T(n) = aT(n/b) + ø((n^k)logᵖn)
각 변수의 의미는 다음과 같습니다.
- n : 문제의 크기
- a : 재귀 호출 시 생성되는 하위 문제의 개수 (a > 0)
- n/b : 각 하위 문제의 크기 (b > 1)
- k ≥ 0, p : 실수(real number)
이러한 유형의 문제를 해결하기 위한 판별 기준은 다음과 같습니다.
- a > bk 인 경우 → T(n) = ∅(nlogba)
- a = bk 인 경우
- p > -1 이면 → T(n) = ∅(nlogba · logp+1n)
- p = -1 이면 → T(n) = ∅(nlogba · log log n)
- p < -1 이면 → T(n) = ∅(nlogba)
- a < bk 인 경우
- p ≥ 0 이면 → T(n) = ∅(nk · logp+1n)
- p < 0 이면 → T(n) = ∅(nk)
고급 마스터 정리를 활용한 복잡도 계산 예시
고급 마스터 정리를 사용하면 대표적인 분할 정복 알고리즘들의 시간 복잡도를 손쉽게 계산할 수 있습니다.
이진 탐색(Binary Search) − T(n) = θ(log n)
병합 정렬(Merge Sort) − T(n) = θ(n log n)