[파이썬으로 구현하는] 분할 정복을 이용한 거듭제곱
"파이썬으로 구현하는"
시리즈 5
분할 정복을 이용한 거듭제곱
가끔씩 백준 문제를 풀다가 보면 어떤 수의 거듭제곱을 매우 빠르게 구해야 할 때가 있다. 물론 나머지 연산을 포함해서.
예를 들어 $2^{100}$을 97로 나눈 나머지를 구한다고 하자.
2를 100번 곱하는 식의 $O(N)$ 풀이는 시간초과가 난다. 분할 정복을 이용하면 이를 $O(log N)$으로 줄일 수 있다.
사실 구현은 매우 간단하다. $2^{100}$은 $2^{50}$을 두 번 곱한 것이라고 볼 수 있다. 이런식으로 계속 절반으로 줄여나가면서 계산하는 것이다.
def mul(b, n):
if n == 1:
return b
if n == 0:
return 1
if n % 2 == 1:
tmp = mul(b, (n-1)//2)
return ((tmp**2)*b) % M
else:
tmp = mul(b, n//2)
return (tmp**2) % M
사실 오늘 내가 이 블로그 글을 적은 이유는 위의 코드를 구현하기 위해서가 아니다!!!!
진짜 이유는, 사실 Python에서는 분할 정복을 이용한 거듭제곱을 직접 구현할 필요 자체가 없다!!!! 불쌍한 C++ 유저들.
파이썬에는 기본적으로 지원해주는 pow() 함수가 있는데, 예를 들어 pow(2, 3)은 $2^3$을 계산해준다. 사실 초보자분들은 이 pow 함수의 진정한 기능을 모르고 있는데, 사실 pow() 함수에는 3번째 인자가 올 수 있다. 바로 나머지 연산을 할 값이다.
그러니까 pow(2, 100, 97)의 경우 $2^{100}$%97을 매우매우 빠르게 계산해줄 수 있다는 것이다. 이 속도는 매우매우 빠르며, 정확한 원리는 모르지만 아마 내부적으로 분할정복을 이용하는 것 같다.
pow() 함수를 이용할 때 주의할 점은, from math import *을 쓰면 안된다는 것이다. 왜냐하면 math 라이브러리에도 pow 함수가 있는데 이 pow 함수는 기본 내장함수랑 달리 세 번째 인자를 받지 않는다. 오버라이딩이 되기 때문에, 문제 풀이에 pow()를 사용하고 있고 math 라이브러리를 사용해야 한다면 math의 모든 요소를 다 불러오는게 아니라, 필요한 것만 불러오자.
그러니까 오늘의 배울 점.