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

예를 들어 3^5 = 3x3x3x3x3로 5번의 반복이 있어야한다.

즉 n 거듭 제곱을 위해선 시간 복잡도가 O(n)이어야 한다.

하지만, 분할 정복을 이용하면 O(logn)으로 값을 얻을 수 있다.

 

C^n = 

C^(n/2) * C^(n/2) (if n % 2 == 0)

C^((n-1)/2) * C^((n-1)/2) else

 

이러한 방법을 사용해야 하는 알고리즘 문제들의 특징은 n > 10^7이상일 때다.

파이썬 기준, 1초에 10^7번의 작업이 가능하다.

만약 n이 이보다 높다면, O(n)으로 해결할 수 없어, 분할 정복을 이용한 거듭 제곱을 활용해야 할 가능성이 높다.

 

참고 문제

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

https://www.acmicpc.net/problem/18291

18291번: 비요뜨의 징검다리 건너기

import sys
MOD = int(1e9+7)

def square(x,n):
    if n == 1:
        return x
    else:
        c = square(x,n//2)
        if n %2==0:
            return (c*c) % MOD
        else:
            return (c*c*x )%MOD

    
t = int(input())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    # DIV = square(10,9) +7
    if n <= 2:
        print(1)
    else:
        print(square(2,n-2)%MOD)

값을 return 해줄 때 MOD값을 미리 나눠주어야 계산 시간을 줄일 수 있다.