프로그래밍 대회를 준비하다 보면 "A를 B번 거듭제곱한 결과를 C로 나눈 나머지를 구하시오 (A^B % C)"와 같은 수학 정수론 문제를 심심치 않게 마주치게 됩니다. A가 2, B가 10 정도라면 단순한 for 반복문으로 10번 곱해서 쉽게 구할 수 있습니다. 하지만 만약 B가 1,000억(100,000,000,000)이라면 어떻게 될까요? 1,000억 번의 루프를 도는 것은 최신 CPU로도 수십 초가 걸려 무조건 시간 초과(TLE) 판정을 받게 됩니다. 게다가 숫자가 기하급수적으로 커지면서 변수의 메모리 한도(Long 타입의 오버플로우)를 순식간에 박살 내버립니다. 이 끔찍한 선형 연산의 굴레를 끊고, 1,000억 번의 연산을 단 30번 대의 연산(O(log N))으로 극단적으로 압축해 내는 컴퓨터 과학의 위대한 마법, '분할 정복을 이용한 거듭제곱 최적화(Exponentiation by Squaring)' 알고리즘을 완벽하게 마스터해 보겠습니다.
1. O(N)의 비효율과 모듈러(Modulo) 분배 법칙
기존의 for(int i=0; i<B; i++) result *= A; 방식은 O(B)의 선형 시간이 걸립니다. 이를 줄이기 전, 먼저 거대한 숫자가 변수 한도를 초과하여 오버플로우(Overflow)가 발생하는 것을 막기 위한 필수 수학 지식인 '모듈러 연산의 분배 법칙'을 짚고 넘어가야 합니다.
// 모듈러 곱셈 분배 법칙
(A * B) % C = ((A % C) * (B % C)) % C
이 공식이 의미하는 바는 엄청납니다. 거듭제곱을 전부 다 계산해서 어마어마하게 큰 숫자를 만든 뒤 마지막에 C로 나누어 나머지를 구할 필요가 없다는 뜻입니다. 곱셈을 한 번 할 때마다 그 즉시 C로 나눈 나머지로 숫자를 깎아내려도, 최종 정답은 100% 동일하게 유지됩니다. 이를 통해 변수가 Long 데이터 타입의 한계치를 넘어 터지는 현상을 완벽하게 방지할 수 있습니다.
2. 분할 정복(Divide & Conquer): 반으로 쪼개어 곱하라
이제 O(B)의 시간을 O(log B)로 박살 낼 차례입니다. 수학의 지수 법칙인 $A^{m+n} = A^m \times A^n$을 활용합니다. $A^{10}$을 구하기 위해 A를 10번 곱할 필요 없이, $A^5$를 구한 뒤 그 녀석을 자기 자신과 한 번만 곱해주면($A^5 \times A^5$) 됩니다. 이 아이디어를 재귀 함수로 쪼개어 들어갑니다.
2-1. 지수가 짝수일 때와 홀수일 때의 분기 처리
함수 power(A, B)를 호출했을 때, 지수 B의 상태에 따라 로직이 두 갈래로 나뉩니다.
- 지수 B가 짝수일 때: 예를 들어 $A^8$을 구해야 한다면, $A^4$를 구해서 제곱하면 됩니다.
half = power(A, B / 2); return (half * half) % C; - 지수 B가 홀수일 때: 예를 들어 $A^9$를 구해야 한다면, 짝수 방식을 그대로 쓸 수 없으므로 $A^4 \times A^4$에 마지막으로 A를 한 번 더 곱해줍니다.
half = power(A, B / 2); return (((half * half) % C) * A) % C; - 기저 조건(Base Case): 지수 B가 0이 되는 순간 1을 반환하고 재귀를 멈춥니다.
2-2. O(log N) 성능 최적화의 증명
만약 $2^{1024}$를 구한다고 치면, 재귀 함수는 1024 → 512 → 256 → ... → 1로 단 10번만 호출됩니다. 1,024번 돌아야 할 반복문이 10번으로 압축된 것입니다. 지수 B가 1,000억이 넘어간다고 해도 $\log_2(1,000,000,000,000) \approx 40$이므로, 고작 40번 내외의 재귀 호출만으로 완벽한 정답을 0.001초 만에 도출해 냅니다.
3. 심화 응용: 행렬의 거듭제곱과 피보나치 수열
이 분할 정복 거듭제곱 기법은 단순히 정수의 곱셈에만 쓰이는 것이 아닙니다. 행렬(Matrix)의 거듭제곱에도 100% 동일하게 적용됩니다.
코딩 테스트 단골 문제인 "피보나치 수열의 100억 번째 항을 구하시오"라는 문제에 직면했을 때, DP 타뷸레이션을 쓰더라도 100억 번의 루프를 돌아야 하므로 O(N) 시간 초과가 발생합니다. 하지만 피보나치 수열의 점화식을 $2 \times 2$ 행렬의 곱셈 형태로 변환한 뒤, 이 분할 정복 거듭제곱 알고리즘을 사용해 행렬을 $N$번 제곱하게 되면, 무려 100억 번째 피보나치 수도 O(log N)이라는 경이로운 속도로 즉시 구해낼 수 있습니다. 알고리즘 최적화의 극치를 보여주는 완벽한 테크닉입니다.
1. 분할 정복 거듭제곱 최적화는 거대한 지수(B)를 가진 연산 $A^B$를 구할 때, 선형 시간 O(B)를 O(log B)로 극단적으로 압축해 내는 필수 알고리즘입니다.
2. 수학의 지수 법칙을 활용하여 지수가 짝수일 때는 반으로 나눈 값을 서로 곱하고, 홀수일 때는 반으로 나눈 값의 곱에 밑(A)을 한 번 더 곱하는 재귀 논리를 사용합니다.
3. 중간 연산 과정에서 데이터 오버플로우를 막기 위해 모듈러 분배 법칙을 적용하며, 이 개념은 행렬의 거듭제곱으로 확장되어 피보나치 수열 등을 O(log N)에 구하는 데 쓰입니다.