[알고리즘] 분할 정복을 이용한 거듭제곱

이전 글에서 피보나치 수를 구하다가 빠른 거듭제곱이 나와 따로 글로 남기게 되었다.

 

거듭제곱을 위해 다음 코드를 작성하면 $O(N)$의 시간이 필요하다.

def pow(a,n):
  r = 1
  for _ in range(n):
    r *= a
  return r

 

위 코드는 거듭제곱을 $a^n=a^{n-1} \times a$ 방식으로 구한다.

이것을 빠르게 해 보자!

 

$n$이 짝수이면

$a^n = a^{n/2} \times a^{n/2}$

$n$이 홀수이면

$a^n = a^{n/2} \times a^{n/2} \times a$  가 된다.

 

이제 이것을 재귀적으로 계산하면 된다.

예를 들어 $3^{60}$을 계산해보자

$3^{60} = 3^{30} \times 3^{30}$

$3^{30} = 3^{15} \times 3^{15}$

$3^{15} = 3^7 \times 3^7 \times 3$

$3^7 = 3^3 \times 3^3 \times 3$

$3^3 = 3^1 \times 3^1 \times 3$

 

$5$번의 연산으로 $3^{60}$을 계산했다.

시간 복잡도는 계속해서 반으로 나눠 계산하기 때문에 $O(\log N)$이 된다.

 

많이 쓰이는 알고리즘이라 solved에서 따로 분류가 되어있다.

분할 정복을 이용한 거듭제곱