분할정복 거듭제곱

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 님의 알고리즘 스터디