😄 개요
a를 n번 거듭제곱 하려면 n-1번의 연산을 수행해야 합니다.
a에 a를 곱하고, 그 결과에 a를 곱하고, 계속 해나가다보면 곱셈연산이 n-1번 이루어지겠지요.
그런데 만약 어마어마하게 큰 숫자의 거듭제곱을 해야한다면 어떨까요?
분할정복을 이용하면 O(n)의 시간 복잡도를 O(log n) 까지 줄일 수 있습니다.
🪡 이론
이론은 연산 과정을 분리하고, 중복되는 결과들을 저장해놓고, 저장된 것이 있다면 꺼내쓰는 것입니다.
거듭 제곱 연산 분할
거듭제곱의 연산과정을 살펴보겠습니다.
을 한다고 가정해보겠습니다.
사실 3의 100거듭제곱은 이렇게도 생각할 수 있습니다.
계속해서 분리할 수 있겠죠?
여기서 을 계산하는 것과 을 계산하는 과정에 들어가는 연산 횟수를 생각해봅시다.
을 계산하는데는 3에 3을 99번 곱하므로 99번의 곱셈연산이 필요합니다.
을 계산하는데는 3을 24번 곱하는것과, 그 결과끼리 4 거듭제곱이 일어나므로 총 27번의 곱셈연산이라고 볼 수 있습니다.
두 번 분할 했더니 99회에서 27회로 줄었습니다.
이렇게 더 작은 단위로 나누면 연산 횟수가 월등히 줄어드는 것을 볼 수있습니다.
거듭 제곱 연산 분할 _ 파이썬 코드
이 과정을 파이썬 코드로 작성하면 다음과 같습니다.
a = 3
##거듭제곱 결과를 저장해놓은 테이블. 미리 기저인 3의 0 거듭 제곱과 1 거듭 제곱을 채워 놓음
involutionTable = {0 : 1, 1 : a}
def involution(n):
#계산된 결과가 있으면 끌어다 쓰기
if n in involutionTable:
return involutionTable[n]
#계산된 결과가 없으므로 계산하기 (분할정복)
involutionTable[n] = involution(n // 2) * involution(n - n // 2)
return involutionTable[n]
print(involution(100))계산 결과를 저장하고 꺼내쓰는 점에서 dp 스킬이 들어갔습니다.
조금 더 빠르게?
분할을 바꾸면 연산 횟수를 더 줄일 수 있습니다.
분할된 지수가 2의 거듭 제곱이 되도록 하는 것입니다.
으로 예시를 들어보면,
이렇게 분할하는 것입니다.
이렇게 분할하는 이유는 거듭제곱 결과를 저장해놓는 테이블을 쉽게 채우는데 있습니다.
위의 방식으로는 어떤 계산결과가 필요할지 몰라 딕셔너리로 선언을 해놓은 후 매번 찾고 없으면 계산해 입력하는것을 볼 수 있습니다.
하지만 2의 거듭 제곱의 지수로만 이루어진 테이블을 만들어 놓고, 해당 지수들을 조합해 전체 결과를 계산하는 방식으로 한다면, 테이블을 만드는데 소요되는 연산이 logn 밖에 걸리지 않습니다.
조금 더 빠르게? _ 파이썬 코드
코드로 살펴보겠습니다.
a = 3
#거듭제곱 계산결과 테이블 채우기
involutionTable = [a]
for i in range(1, 10):
involutionTable.append(involutionTable[i - 1] * involutionTable[i - 1])
def involution(n):
##비트 연산을 이용해 결과 계산
result = 1
i = 0
while n > 0:
if n % 2 == 1:
result *= involutionTable[i]
n //= 2
i += 1
return result
print(involution(100))여기서 입니다.
이렇게 만들어놓고, n을 비트연산 해가며 필요한 3의 거듭제곱을 조합해 전체 결과를 만드는 방식입니다.
이 방식을 이용하면 재귀함수도 하지 않아도 되고, 연산량도 줄어 좋습니다.
🧵 적용
거듭제곱에서 분할정복을 이용하여 빠르게 진행하는 방식은 당연하게도 모든 거듭제곱 연산에 적용이 가능합니다. 대표적으로 행렬의 거듭제곱을 하는데 많이 쓰입니다. 행렬은 곱하는데만 기본적으로 의 시간복잡도를 가지고 있으니 다른 곳에서라도 연산량을 줄일 필요가 있겠죠.
