분할 정복을 통한 pow 구현하기

저번 글을 통해서 python에서 pow를 어떻게 쓰는지 알아보았는데 

파이썬에서의 pow와 math.pow 차이점

이 함수를 쓰면 안풀릴 때가 있는 문제가 있다.

 

왜냐하면 이 함수들은 기본적으로 시간복잡도가 O(n)이기 때문이다.

 

1629번: 곱셈 (acmicpc.net)

1629번: 곱셈

이 문제를 풀 때 그냥 pow를 이용해서 풀려고 하면 안 풀릴 것이다.

 

이럴 때에는 분할 정복을 통해서 pow를 구현해주면 된다.

def pow(a,b,m):
    result = 1
    while b > 0:
        if b % 2 != 0:
            result = (result * a) % m
        b //= 2
        a = (a * a) % m
    return result

이런식으로 작성해주면 된다. 물론 재귀를 통해서 작성할 수도 있지만 python에서 재귀를 이용하면 recursion error가 발생할수도 있어서 그냥 이렇게 하는 것이 편하다. 또 sys.setrecursion하기 귀찮기도 하고...

이러면 시간복잡도는 O(logn)이 되어 시간을 대폭 줄일 수 있다.

 

만약 그냥 **나 pow를 사용한다면 $2*2*2*2*2*22*2$ 이런식으로 계산하겠지만 위의 코드를 이용하면 $2^8=2^4*2^4$ 가 되어서 8번 계산할것을 2번으로 줄이게 되는 것이다.

 

생각보다 자주 사용되는 것인 반드시 외워두시길!!