분할정복 거듭제곱

밑을 반복해서 곱하는 대신 지수를 절반씩 줄여가며 a^n을 O(log n)에 계산하는 분할 정복 기법입니다.

동작 과정

예시: 3^13 계산하기. half = pow(base, exp/2)로 지수를 절반으로 나눈 뒤, 짝수면 half*half, 홀수면 base*half*half로 결합한다.

divide: 지수를 절반으로 줄여가며 내려간다
pow(3, 13)  13은 홀수 → half 필요: pow(3, 6)
  pow(3, 6)   6은 짝수 → half 필요: pow(3, 3)
    pow(3, 3)   3은 홀수 → half 필요: pow(3, 1)
      pow(3, 1)   1은 홀수 → half 필요: pow(3, 0)
        pow(3, 0)   base case → 1

combine: 아래에서 위로 올라오며 결합한다
pow(3, 0) = 1
pow(3, 1) = base * half * half = 3 * 1 * 1 = 3        (홀수)
pow(3, 3) = base * half * half = 3 * 3 * 3 = 27        (홀수)
pow(3, 6) = half * half = 27 * 27 = 729                (짝수)
pow(3, 13) = base * half * half = 3 * 729 * 729 = 1594323  (홀수)

지수가 13 → 6 → 3 → 1 → 0으로 매번 절반씩 줄어들기 때문에, 1부터 반복 곱셈하는 O(n) 방식과 달리 재귀 호출이 log₂(n) 단계만에 끝난다.

구현

long power(long base, long exp) {
    if (exp == 0) {
        return 1;
    }
    long half = power(base, exp / 2);
    if (exp % 2 == 0) {
        return half * half;
    }
    return base * half * half;
}

복잡도

지수를 매 호출마다 절반으로 나누므로 재귀 깊이는 log₂(n)이다.

• 시간 복잡도: O(log n) — 호출 횟수가 log₂(n)에 비례
• 공간 복잡도: O(log n) — 재귀 호출 스택 깊이

단순히 base를 exp번 반복해서 곱하는 방식은 O(n)이므로, 지수가 커질수록 분할정복 방식의 이득이 커진다.

주의사항

• 오버플로: half * half는 결과가 매우 빠르게 커지므로 long도 쉽게 넘친다. RSA 같은 암호학 응용에서는 매 곱셈 뒤 바로 나머지 연산을 적용하는 모듈러 거듭제곱 형태로 써야 오버플로를 피할 수 있다
• 홀짝 분기를 빠뜨리면 틀린다: exp / 2는 정수 나눗셈이라 홀수일 때 밑 하나를 추가로 곱해줘야 한다(base * half * half). 이 분기를 빠뜨리면 지수가 짝수일 때만 결과가 맞는다
• 음수 지수: 지수가 음수인 경우는 이 구현이 다루지 않는다. 처리하려면 1.0 / power(base, -exp) 형태로 별도 분기가 필요하다
• 재귀 대신 지수를 이진수로 보고 반복문으로 구현할 수도 있으며, 결과와 시간 복잡도는 동일하다

핵심 정리

• pow(base, exp)를 pow(base, exp/2) 하나로 줄여 재사용하는 분할 정복 기법이다
• 지수가 짝수면 half * half, 홀수면 base * half * half로 결합한다
• 반복 곱셈 O(n)보다 빠른 O(log n)에 거듭제곱을 계산한다
• 모듈러 연산과 결합한 모듈러 거듭제곱은 암호학(RSA 등)에서 핵심적으로 쓰인다

→ 분할 정복