분할 정복: 쪼개고, 풀고, 꿰매고

"분할 정복은 야망 있는 재귀야: 어려운 문제를 독립된 더 작은 것으로 쪼개고, 각각 풀고, 결과를 꿰매. 쪼개기랑 꿰매기가 싸면, 이게 잔혹한 문제를 순하게 만들어."

세 박자 패턴

병합 정렬, 퀵소트, 이진 탐색에서 이미 분할 정복을 만났어 — 이제 공유 모양에 이름 붙여. 분할 정복 알고리즘은: 문제를 더 작은 독립 부분 문제로 나누고, 각각 재귀로 정복하고, 그 답을 전체 해법으로 결합해. 예술은 나누기랑 결합 단계에; 정복은 그냥 '재귀하고 믿어' (믿음의 도약). 이진 탐색이 최소 케이스 — 둘로 나누지만 한 절반만 재귀해, 정확히 그래서 O(log n).

비용을 결정하는 것

재귀-트리 lesson 에서: 비용은 세 손잡이에 달렸어 — 각 호출이 부분 문제를 몇 개 낳고 (분기), 얼마나 작아지고 (줄이는 속도), 나누고 결합하는 일. 병합 정렬: 부분 문제 2개, 각자 반-크기, O(n) 결합 → O(n log n). 이진 탐색: 사실상 부분 문제 1개, 반-크기, O(1) 결합 → O(log n). master theorem 이 이걸 공식으로 바꾸지만, 직관이면 충분해: 싼 결합 + 좋은 줄이기 = 빠른 알고리즘. 결합 단계가 무차별보다 비싸면, 분할 정복은 안 도와 — 그래서 영리함이 부분답을 함께 꿰매는 싼 방법 찾기에 살아.

분할 정복 = 독립 부분 문제로 쪼개고, 각각 재귀로 풀고, 결합. 비용은 분기 × 깊이 + 나누기/결합 일이 정해. 결합 단계가 직접 푸는 것보다 쌀 때 이겨 — 그 싼 꿰매기가 트릭 전부야.

깔끔한 승리: 빠른 거듭제곱

분할 정복이 허공에서 속도 향상을 만드는 거. a^n 을 당연한 방식으로 계산하면 n−1 곱셈, O(n). 근데 a^n = (a^(n/2))² — 그래서 a^(n/2) 를 한 번 계산하고, 제곱하면, 한 곱셈에 지수를 반 냈어. 재귀하면, 지수가 매 단계 절반: O(n) 대신 O(log n) 곱셈. a^1000000 이 백만이 아니라 ~20 곱셈. 이 '제곱에 의한 거듭제곱' 이 사방에 있어 — 암호학이 수를 거대 거듭제곱하는 법이고, 행렬-거듭제곱 트릭이 피보나치를 O(log n) 에 계산하는 법. 병합 정렬이랑 같은 패턴, 산술을 겨눈.

피파의 고백

난 거대 거듭제곱을 평범한 루프로 계산했고 기었어. 아빠가 a^n = (a^(n/2))² 를 칠판에 쓰고 물었어, "백만을 몇 번 반 낼 수 있어?" 약 스무 번. 루프는 백만 곱셈을 했고; 제곱은 스무 번. 난 분할 정복을 '정렬이 하는 것' 으로 봤는데, 일반 지렛대야: 크기 n 문제를 크기 n/2 문제에서 싸게 다시 지을 수 있으면, 종종 O(n) 을 O(log n) 으로 맞바꿔. 이젠 그 절반 내기를 어디서나 찾아.

Code

빠른 거듭제곱 — 절반 내기로 O(n) 에서 O(log n)·python

# 제곱에 의한 빠른 거듭제곱: a^n 을 O(n) 아니라 O(log n) 곱셈에.
def fast_power(a, n):
    if n == 0:
        return 1                     # base case: a^0 = 1
    half = fast_power(a, n // 2)     # a^(n/2) 를 한 번 풀기 (나누기 + 정복)
    if n % 2 == 0:
        return half * half           # 결합: a^n = (a^(n/2))^2
    else:
        return half * half * a       # 홀수 지수: 곱셈 하나 더

print(fast_power(2, 10))     # 1024
print(fast_power(3, 13))     # 1594323
# a^1000000 은 ~20 재귀 호출 (백만의 log2), 백만이 아니라.
# 지수가 매 레벨 절반 -> O(log n). 병합 정렬이랑 같은 D&C 모양.

# 이미 다른 분할 정복 알고리즘을 만났어:
#   병합 정렬   : 반 2개, O(n) 결합          -> O(n log n)
#   이진 탐색   : 반 1개, O(1) 결합          -> O(log n)
#   퀵소트      : 부분 2개, O(n) 분할        -> 평균 O(n log n)

Exercise

fast_power(2, 8) 을 손으로 추적해: base case 까지 재귀 호출이랑 올라오며 제곱을 보여. 총 곱셈이 몇 번, 순진한 '2 를 여덟 번 곱하기' 대비? 그다음 이게 왜 O(n) 이 아니라 O(log n) 인지 한 문장으로 설명해.

Hint

fast_power(2,8) → (2^4)² → (2^2)² → (2^1)²·… 지수가 8→4→2→1→0 절반, 약 log₂(8)=3 재귀 레벨, ~4 곱셈 vs 순진한 7-8. O(log n) 인 이유는 각 단계가 지수를 절반 내, base case 닿는 데 log₂(n) 단계 걸려.

세 박자 패턴

비용을 결정하는 것

깔끔한 승리: 빠른 거듭제곱

피파의 고백

Code

External links

Exercise

Progress

댓글 0