[알고리즘] 분할정복으로 거듭제곱 최적화하기

프로그래밍에서 거듭제곱을 구하는 방법은 크게 세 가지이다.

 

pow 내장함수 사용하기

double 실수 자료형을 사용해 거듭제곱을 반환하는 방법이다.

 

하지만 지수가 매우 클 때 정확성의 문제가 발생한다. 그 문제는 아래 글에서 확인 가능하다. C++ 기준 pow에 관한 글이다.

 

2023.04.30 - [TIL] - [C++] pow함수 double 형의 정확성 문제

[C++] pow함수 double 형의 정확성 문제

 

 

 O(N) 구하기

def power(a,b):
	result=1
    for i in range(b):
        result *= a
    return result
    
def power2(a,b):
	if b==0: return 1
    return a * power(a,b-1)

for문이나 재귀로 a를 b번 곱하여 반환하는 함수이다. 정수 자료형을 사용하여 정확도 문제가 발생하지 않으나 O(N)의 시간복잡도를 가지므로 지수가 클 때 비효율적이다.

 

 

분할정복으로 구하기

위 아이디어를 사용해 계산시간을 O(logN)으로 줄인 방법이다. 

 

정리하면 다음과 같다.

>>> python

def power(a,b):
    if b==0: return 1
    if b%2:
        return (power(a,b-1)*a) % MOD
    tmp=power(a,b//2) % MOD
    return tmp*tmp % MOD

>>> c++ mod 연산을 하는 pow 

int modpow(int x,int n, int m){
    if(n==0) return 1%m;
    long long u=modpow(x, n/2, m);
    u = (u*u)%m;
    if(n%2==1) u=(u*x)%m;
    return u;
}

 

정수론, 조합론에서 은근 분할정복이 많이 쓰인다. 같은 연산이 O(N) 수행한다면 sqrt(N) 이나 logN으로 최적화할 수 있나 확인해보자.

 

 

물론 python에서는 ** 연산자와 Math.pow(a,b)로 정확한 결과를 보장한다. 파이썬이 세상을 지배한다...!