🔍 분할 정복을 이용한 거듭제곱: 이진 분할법
오늘은 A^B % C와 같이 큰 수의 거듭제곱과 나머지 연산을 효율적으로 처리하는 이진 분할법(Binary Exponentiation) 알고리즘을 학습했다. 이 기법은 분할 정복(Divide and Conquer) 원리를 기반으로 하며, 단순 반복 계산 시 발생하는 시간 초과 문제를 해결하는 데 필수적이다.
💡 이진 분할법, 왜 배워야 할까?
많은 알고리즘 문제에서 시간 복잡도는 핵심적인 평가 요소다. 특히 지수
B가 10억 단위 이상으로 주어질 경우, O(B)의 시간 복잡도를 갖는 단순 반복문은 사용할 수 없다. 이진 분할법은 이 시간 복잡도를 O(log B) 로 획기적으로 줄여주어, 제한 시간 내에 문제를 해결할 수 있게 해주는 핵심 알고리즘이다.
🚀 이진 분할법의 주요 특징
| 특징 | 설명 |
|---|---|
| 분할 정복 기반 | 큰 문제를 작은 문제로 나누어 해결하는 분할 정복 전략을 사용한다. |
| 로그 시간 복잡도 | 지수 B에 대해 O(log B)의 시간 복잡도를 가져 매우 빠르다. |
| 모듈러 연산 활용 | (X * Y) % C = ((X % C) * (Y % C)) % C 성질을 이용해 오버플로우를 방지한다. |
| 재귀적 구현 | 재귀 함수를 통해 아이디어를 간결하고 직관적으로 구현할 수 있다. |
📊 단순 반복과의 시간 복잡도 비교
이진 분할법의 효율성은 단순 반복 방식과의 비교를 통해 명확하게 이해할 수 있다.
| 알고리즘 | 시간 복잡도 | 지수 B = 2,147,483,647 일 때 |
|---|---|---|
| 단순 반복 | O(B) | 약 21억 번의 연산 (시간 초과) |
| 이진 분할법 | O(log B) | 약 31번의 연산 (통과) |
이진 분할법은 모듈러 산술(Modular Arithmetic) 의 기본 성질을 활용하여, 곱셈 과정에서 발생하는 큰 숫자를 효과적으로 제어한다.
🛠️ 기본 원리 및 재귀 구현
이진 분할법은 지수 B를 짝수와 홀수 케이스로 나누는 분할 정복과, 계산 과정의 숫자를 제어하는 모듈러 산술 두 가지를 핵심 축으로 사용한다.
1. 분할 정복 아이디어
- 지수가 짝수일 때:
A^B = A^(B/2) * A^(B/2) - 지수가 홀수일 때:
A^B = A^(B/2) * A^(B/2) * A
2. 모듈러 산술의 적용
A^(B/2)를 계산하는 과정에서 숫자가 너무 커지면 오버플로우가 발생할 수 있다. 이때 모듈러 산술의 성질인 (X * Y) % C = ((X % C) * (Y % C)) % C 를 적용한다.
이 성질 덕분에, (A^(B/2) * A^(B/2)) % C는 ((A^(B/2) % C) * (A^(B/2) % C)) % C와 동일한 결과를 보장한다. 따라서 재귀 호출의 모든 단계에서 나머지 연산을 적용하여 중간 결과값이 C를 넘지 않도록 제어할 수 있다.
3. 재귀 함수 구현
위 아이디어들을 종합한 재귀 함수는 다음과 같다.
# 분할 정복을 이용한 거듭제곱 함수
def power(a, b, c):
# 베이스 케이스: b가 1이면 a % c를 반환
if b == 1:
return a % c
# 지수를 반으로 나누어 재귀 호출 (분할)
# power(a, b // 2, c)는 (a^(b/2)) % c 의 결과를 반환한다.
res = power(a, b // 2, c)
# 계산된 결과를 모듈러 연산을 이용해 조합 (정복)
res = (res * res) % c
# 지수가 홀수였을 경우, a를 한 번 더 곱함
if b % 2 != 0:
res = (res * a) % c
return res
✨ 요약
- 이진 분할법은 거듭제곱 연산의 시간 복잡도를 O(B)에서 O(log B)로 획기적으로 줄이는 알고리즘이다.
- 분할 정복 원리를 이용해 지수를 절반으로 나누어 재귀적으로 문제를 해결한다.
- 모듈러 산술의
(X * Y) % C = ((X % C) * (Y % C)) % C성질을 모든 계산 단계에 적용하여 오버플로우를 방지하는 것이 핵심이다. - 재귀 함수 구현 시, 지수가 1일 때 값을 반환하는 베이스 케이스를 명확히 설정해야 한다.