분할 정복(Divide and Conquer)이란?

분할 정복(Divide and Conquer)은 복잡한 문제를 작은 부분 문제로 나누어 해결한 뒤,
이를 다시 합쳐 원래 문제의 해답을 얻는 알고리즘 설계 기법이다.

쉽게 말해, "문제를 작게 나누고, 각 문제를 해결한 뒤, 그 결과를 합쳐서 큰 문제를 해결하는 방식"

---

1. 분할 정복의 동작 과정

분할 정복 알고리즘은 보통 다음 세 단계로 구성된다.

1. 분할(Divide): 큰 문제를 더 작은 부분 문제로 나눈다.
2. 정복(Conquer): 각각의 작은 부분 문제를 재귀적으로 해결한다.
3. 병합(Combine): 작은 문제들의 결과를 합쳐서 원래 문제의 해답을 얻는다.

---

2. 분할 정복의 특징 및 장점

• 문제를 작은 단위로 나누어 복잡도를 낮추는 데 효과적이다.
• 작은 부분 문제들이 서로 독립적으로 해결 가능하기 때문에 병렬 처리에 유리하다.
• 재귀적 방법을 자주 사용하며, 간결하고 효율적인 코드 작성이 가능하다.

---

3. 분할 정복을 사용하는 대표적인 알고리즘들

알고리즘	설명	시간복잡도
병합 정렬 (Merge Sort)	배열을 반씩 나누어 정렬하고 병합하는 알고리즘	$O(N log N)$
퀵 정렬 (Quick Sort)	피벗을 기준으로 나누어 정렬하는 알고리즘	평균 $O(N log N)$, 최악 $O(N^2)$
이진 탐색 (Binary Search)	정렬된 데이터에서 값을 빠르게 찾는 알고리즘	$O(log N)$
거듭제곱 (Fast Power)	빠르게 제곱수를 계산하는 알고리즘	$O(log N)$
스트라센 알고리즘	행렬 곱셈을 더 빠르게 계산하는 알고리즘	약 $O(N^{2.81})$

---

4. 분할 정복의 시간복잡도 분석

분할 정복 알고리즘의 일반적인 시간 복잡도는 다음과 같이 표현된다.

• $a$ : 재귀 호출 횟수
• $n/b$ : 문제의 크기가 얼마나 작아지는지
• $O(n^d)$ : 분할 및 병합에 걸리는 시간

병합 정렬의 경우

• $T(n) = 2T(n/2) + O(n) = O(n log n)$

---

5. 분할 정복 예시

5-1 거듭제곱(Fast Power)

거듭제곱은 단순히 a^n을 반복 곱셈으로 구하면 $O(n)$의 시간이 걸린다.
하지만 분할 정복을 사용하면 $O(log n)$ 시간에 빠르게 계산할 수 있다.

아이디어

• 짝수 지수
  $a^n = (a^{n/2})^2$
• 홀수 지수
  $a^n = a \times (a^{\lfloor n/2 \rfloor})^2$

예시 코드

def fast_power(a, n):
    if n == 0:
        return 1
    half = fast_power(a, n // 2)
    if n % 2 == 0:
        return half * half
    else:
        return a * half * half

# 예시: 2^10 = 1024
print(fast_power(2, 10))  # 출력: 1024

시간 복잡도

• $O(log n)$ → 재귀 호출이 n을 절반씩 줄이기 때문에 매우 빠름

---

5-2 모듈러(modular) 거듭제곱

큰 수를 계산할 때는 중간에 모듈러 연산을 적용해 오버플로우를 방지하고 효율적으로 계산할 수 있다.

아이디어

• 짝수 지수
  $a^n \bmod m = ( a^{n/2} \bmod m )^2 \bmod m$
• 홀수 지수
  $a^n \bmod m = a \times ( a^{\lfloor n/2 \rfloor} \bmod m )^2 \bmod m$

예시 코드

def fast_power_mod(a, n, mod):
    if n == 0:
        return 1
    half = fast_power_mod(a, n // 2, mod)
    result = (half * half) % mod
    if n % 2 == 1:
        result = (result * a) % mod
    return result

# 예시: 2^10 % 1000 = 24
print(fast_power_mod(2, 10, 1000))  # 출력: 24

파이썬 내장 함수와 비교

import time

# 비교용 큰 수
a = 987654321
n = 10**9
mod = 1_000_000_007

# 사용자 정의 함수 시간 측정
start = time.time()
custom_result = fast_power_mod(a, n, mod)
end = time.time()
print(f"Custom fast_power_mod result: {custom_result}")
print(f"Custom function time: {end - start:.6f} seconds")

# 내장 함수 pow 시간 측정
start = time.time()
builtin_result = pow(a, n, mod)
end = time.time()
print(f"Built-in pow result: {builtin_result}")
print(f"Built-in pow time: {end - start:.6f} seconds")

# 결과
Custom fast_power_mod result: 69424128
Custom function time: 0.000118 seconds
Built-in pow result: 69424128
Built-in pow time: 0.000005 seconds

• 내장 함수 pow(a, b, mod)는 C로 작성되어 있고 파이썬 인터프리터 수준에서 최적화되어 있기 때문에 매우 빠르다.

• 반면, fast_power_mod는 Python으로 작성된 재귀 함수이므로 약간의 오버헤드가 있지만, 그럼에도 불구하고 충분히 빠른 속도를 보여준다.