nk 을 계산할 때, n을 k번 곱하면 k번의 연산이 필요.
k가 작다면 시간이 적게 걸리겠지만, k가 1012 같이 매우 큰 수로 주어지는 경우 시간 초과가 발생.
이 때, 분할 정복 거듭제곱을 이용하면 연산을 크게 줄일 수 있음.
일반적인 nk 시간 복잡도는 n을 k번 곱하므로 O(N)의 시간복잡도를 가짐.
하지만, 분할 정복 거듭제곱은 O(logN)의 시간 복잡도를 갖게 된다.
def power(n, k):
result = 1
# 더 이상 곱할 것이 없을 때 까지 진행
while k > 0:
# k가 홀수라면, n 곱하기
if k % 2:
result *= n
n *= n
k //= 2
return result
해결가능한 문제
백준 18291
https://www.acmicpc.net/problem/18291
출처 : bomul1128 님의 알고리즘 스터디