분할 정복

분할 정복은 복잡한 문제를 더 이상 나눌 수 없을 때까지 작은 문제로 쪼개어 해결하는 방법론이다. 이 기법은 문제를 한 조각씩 떼어내는 일반적인 재귀 호출과 달리, 문제를 거의 같은 크기의 부분 문제로 나누는 특징이 있다. 어원은 로마 제국이 식민지의 단결을 막기 위해 사용한 전략인 '분할 통치(Divide and Rule)'에서 유래하였다.

분할 정복 알고리즘은 일반적으로 다음의 세 단계를 거쳐 수행된다.

분할 정복을 성공적으로 적용하기 위해서는 문제를 나누는 자연스러운 방법이 존재해야 하며, 부분 문제의 답을 조합하여 전체 답을 계산하는 효율적인 방법이 뒷받침되어야 한다.

분할 정복은 주로 **재귀 함수(Recursive Function)**를 통해 구현된다. 함수가 자기 자신을 호출하면서 연산의 단위를 점진적으로 줄여나가는 방식이다.

• 장점: 어려운 문제를 해결 가능한 단위로 쪼개어 접근할 수 있으며, 병렬 처리에 유리하다.
• 단점: 재귀 호출 시 함수 호출 오버헤드가 발생하여 실행 속도가 저하될 수 있다. 또한 하위 문제의 결과를 저장하지 않고 반복 계산할 경우 효율성이 떨어질 수 있다.

실행 속도를 높이거나 부문제 해결 순서를 제어하기 위해 재귀 대신 스택(Stack)이나 큐(Queue) 등의 자료구조를 사용하여 구현하기도 한다.

분할 정복 알고리즘의 시간 복잡도는 일반적으로 **마스터 정리(Master Theorem)**를 통해 분석한다. 점화식 $T(n) = aT(n/b) + f(n)$의 형태로 표현되며, 여기서 $a$는 하위 문제의 개수, $b$는 분할 비율, $f(n)$은 분할 및 조합에 드는 비용이다.

예를 들어 병합 정렬은 $T(n) = 2T(n/2) + O(n)$이므로 $O(n \log n)$의 시간 복잡도를 가진다. 퀵 정렬은 평균 $O(n \log n)$이지만 최악의 경우 $O(n^2)$이다. 이분 탐색은 $T(n) = T(n/2) + O(1)$이므로 $O(\log n)$이다.

분할 정복의 효율은 분할 방식과 조합 비용에 크게 의존하므로, 문제의 특성에 맞는 설계가 중요하다.

분할 정복 기법은 다양한 알고리즘의 근간이 된다.

• 정렬 알고리즘: 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 대표적이다.
• 수학적 문제: 고속 푸리에 변환(FFT), 큰 수의 곱셈, 거듭제곱 계산($a^n$) 등에 사용된다.
• 퍼즐 및 탐색: 하노이의 탑 문제 해결, 이분 탐색(Binary Search) 등이 있다.
• 기타: 오토마타의 하향식 파서(Top-down parser) 설계, 최근접 점의 쌍 찾기 등에도 이용된다.

문제를 축소하여 정복한다는 개념은 고대부터 존재하였다. 기원전 유클리드(Euclid)는 『원론』에서 문제를 분할하여 최대공약수를 구하는 알고리즘을 정리하였는데, 이는 인류 최초의 알고리즘으로 평가받는다. 현대 컴퓨터 과학에서는 1945년 존 폰 노이만(John von Neumann)이 병합 정렬을 통해 분할 정복의 개념을 체계적으로 설명하였다. 아이작 뉴턴 또한 미분을 개발할 때 잘게 쪼개어 합친 후 극한으로 보내는 분할 정복과 유사한 아이디어를 활용하였다.