이전 글에서 피보나치 수를 구하다가 빠른 거듭제곱이 나와 따로 글로 남기게 되었다. 거듭제곱을 위해 다음 코드를 작성하면 O(N)의 시간이 필요하다. def pow(a,n): r = 1 for _ in range(n): r *= a return r 위 코드는 거듭제곱을 an=an−1×a 방식으로 구한다. 이것을 빠르게 해 보자! n이 짝수이면 an=an/2×an/2 n이 홀수이면 an=an/2×an/2×a 가 된다. 이제 이것을 재귀적으로 계산하면 된다. 예를 들어 360을 계산해보자 360=330×330 $3^{30} = 3^{15} \times 3..