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

"분할 정복은 야심 있는 재귀야. 어려운 문제를 서로 독립적인 더 작은 문제로 쪼개고, 각각 풀고, 결과를 꿰매 붙이는 거지. 쪼개기와 꿰매기가 싸게 먹히면 이 방식이 잔혹한 문제를 순하게 만들어."

세 박자 패턴

병합 정렬, 퀵소트, 이진 탐색에서 이미 분할 정복을 만났어. 이제 그 공통 모양에 이름을 붙일 차례야. 분할 정복 알고리즘은 문제를 더 작고 독립적인 부분 문제로 나누고, 각각을 재귀로 정복하고, 그 답들을 전체 해법으로 결합해. 기술은 나누기와 결합 단계에 있어. 정복은 그냥 '재귀하고 믿기'니까(믿음의 도약 말이야). 이진 탐색이 가장 단순한 경우야. 둘로 나누되 한쪽만 재귀하는데, 그래서 O(log n)인 거지.

비용을 결정하는 것

재귀 트리에서 봤듯이 비용은 손잡이 세 개에 달렸어. 호출 하나가 부분 문제를 몇 개 낳는지(분기), 얼마나 작아지는지(축소 속도), 그리고 나누고 결합하는 데 드는 일. 병합 정렬은 절반 크기 부분 문제 두 개에 O(n) 결합이라 O(n log n)이고, 이진 탐색은 사실상 절반 크기 부분 문제 하나에 O(1) 결합이라 O(log n)이야. master theorem이 이걸 공식으로 바꿔 주지만 직관만으로도 충분해. 결합이 싸고 잘 줄어들면 빠른 알고리즘이 나온다는 것. 결합 단계가 무차별 대입보다 비싸면 분할 정복은 도움이 안 되고. 그래서 진짜 기술은 부분 답들을 싸게 꿰매는 방법을 찾는 데 있어.

분할 정복은 독립적인 부분 문제로 쪼개고, 각각 재귀로 풀고, 결합하는 거야. 비용은 분기에 깊이를 곱한 것에 나누기와 결합의 일을 더한 값으로 정해지고. 결합 단계가 직접 푸는 것보다 쌀 때 이겨. 그 싸게 꿰매는 방법을 찾는 게 핵심이야.

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

음이 아닌 정수 지수 n에 대한 제곱을 이용한 거듭제곱은 지수를 매 단계 절반으로 줄여서, 재귀 단계가 O(log n)번이고 단계마다 곱셈이 상수 개야. a^1,000,000이면 절반 내기가 스무 번쯤에 홀수 단계마다 곱셈이 추가로 붙어. 그러니까 곱셈이 정확히 스무 번인 건 아니야. 음수 지수까지 지원하려면 역수를 어떻게 다룰지, 0의 음수 거듭제곱은 어떻게 할지 별도의 계약이 필요하고.

피파의 고백

거대한 거듭제곱을 평범한 반복문으로 계산했더니 기어가더라. 아빠가 칠판에 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)은 n=8,4,2,1,0을 거치며 각 양수 단계에서 제곱 한 번, n=1에서 추가 곱셈 한 번을 해서 이 구현 기준으로 곱셈이 다섯 번이야. 순진한 반복은 일곱 번, 초기값 규약에 따라서는 여덟 번 곱하고. 핵심은 정확한 상수보다 단계 수가 O(log n)이라는 점이야.

세 박자 패턴

비용을 결정하는 것

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

피파의 고백

Code

External links

Exercise

Progress

댓글 0