Divide and Conquer

분할 정복

분할 정복은 그대로 해결하기 어려운 커다란 문제를 동일한 유형의 더 작은 부분 문제들로 나누어 해결하는 알고리즘 설계 기법이다. 문제를 충분히 작아질 때까지 쪼갠 뒤, 각각의 해답을 구하고 이를 다시 합쳐서 원래 문제의 답을 찾아내는 것이 핵심이다.

동작 과정

일반적으로 재귀 함수를 통해 구현하며, 아래의 3단계 과정을 거친다.

1. 분할 (Divide): 원래 문제를 더 작은 부분 문제들로 나눈다.
2. 정복 (Conquer): 각 부분 문제가 충분히 작다면 직접 해결하고, 그렇지 않으면 다시 재귀적으로 분할하여 해결한다.
3. 결합 (Combine): 부분 문제들의 해를 합쳐 원래 문제의 답을 구한다.

주요 활용 사례

제공된 소스코드들에서도 분할 정복의 원리가 다양하게 활용되고 있다.

1. 분할 정복을 이용한 거듭제곱

지수 $y$를 절반씩 나누어($y/2$) 계산함으로써, 기존 $O(N)$의 복잡도를 $O(\log N)$으로 획기적으로 줄이는 방법이다.

• 분할: 지수 $y$가 짝수면 $x^{y/2} \times x^{y/2}$, 홀수면 $x \times x^{y/2} \times x^{y/2}$ 형태로 나눈다.
• 정복: 지수가 0이 될 때까지 반복한다.

2. 카라추바 알고리즘

큰 수 (Big Integer) 의 곱셈에서 숫자를 상위 자릿수와 하위 자릿수로 분할하여 곱셈 연산 횟수를 줄이는 방식이다.

• 분할: $N$자리 숫자를 $N/2$자리 숫자 두 개로 나눈다.
• 결합: 나누어 계산한 부분 곱들을 공식에 맞춰 합쳐 최종 결과값을 얻는다.

3. 세그먼트 트리

구간에 대한 쿼리를 처리할 때 사용하며, 부모 노드가 담당하는 구간을 자식 노드들이 반씩 나누어 가지는 이진 트리 구조를 띤다.

• 구현: init 함수 등을 통해 구간을 계속 반으로 쪼개어 리프 노드까지 도달한 뒤, 다시 부모 노드로 올라오며 결과값을 합쳐 저장한다.

분할 정복 vs 다이나믹 프로그래밍

두 기법 모두 문제를 작은 부분 문제로 나눈다는 공통점이 있으나, 부분 문제의 중복 여부에서 차이가 발생한다.

구분	분할 정복 (Divide & Conquer)	다이나믹 프로그래밍 (DP)
특징	부분 문제가 서로 독립적이며 중복되지 않음	부분 문제가 중복되어 나타남
핵심	문제를 쪼개서 각각 해결함	이전 계산 결과를 저장(Memoization)하여 재활용함
사례	병합 정렬, 퀵 정렬, 거듭제곱	냅색 문제, LCS

시간 복잡도

문제를 매번 절반($1/2$)으로 나누는 경우, 트리의 높이가 $\log N$이 되기 때문에 전체 복잡도는 $O(N \log N)$ 또는 $O(\log N)$으로 나타나는 경우가 많다. 이는 단순 반복문을 사용하는 $O(N)$이나 $O(N^2)$ 방식보다 훨씬 효율적이다.