[Algorithm] / [Python] 분할정복 - 거듭제곱을 더 빠르게 계산하자 !

이 블로그를 참고하여 작성하였습니다 !

 

수학에서 거듭제곱은 같은 수를 거듭하여 곱한 것으로, 주어진 수를 주어진 횟수만큼 여러 번 곱하는 연산입니다.

 

이는 코드를 통해 쉽게 구현이 가능하지만, 여러 코딩 테스트를 문제를 풀기위해선 효율적으로 구성할 필요가 있습니다.

 

1. 반복문 사용

def power(a, b):
    answer = 1
    for _ in range(b):
    	answer *= a
    return answer

 

2. 재귀함수 사용

\(a^n = a_1 \times a_2 \times a_3 \times \cdots \times a_n\) 는 점화식 \(a^n = a^{n-1} * a\)로 표현할 수 있습니다.

def power(a, b):
    if b == 1:
    	return a
    return power(a, b-1) * a

 

3. 분할정복 활용

지수법칙을 활용하면 거듭제곱을 더욱 효율적으로 구할 수 있습니다.

 

두 거듭제곱 간 밑인 a가 같을 때, a의 n제곱과 a의 m제곱을 곱한 수는 두 지수 n과 m을 더한 값을 지수로 취하는 \(a^{n+m}\)로 표현할 수 있습니다. (\(2^4 = 2^2 * 2^2\))

 

이를 활용한다면, \(a^n\)을 \(a^{n/2} * a^{n/2}\)로 표현할 수 있습니다.

 

그렇다면, n이 2로 나누어 떨어지지 않는 홀수라면 그냥 a를 한 번만 더 곱해주면 해결됩니다. (\(2^5 = 2^2 * 2^2 * 2\))

 

이렇게 n을 매번 2로 나누어 더 작은 무제로 만들어 해결하는 방식을 분할정복 방식이라고 할 수 있습니다.

def power(a, n):
    if n == 0:
    	# a^0 = 1 이므로 1 리턴
        return 1 
    
    if n == 1:
        return a
    
    if n % 2 == 0: # n이 짝수일 때
        return power(a, n//2) * power(a, n//2)
    
    else: # n이 홀수일 때
        return power(a, n//2) * power(a, n//2) * a

하지만 위 함수 역시 \(O(n)\)의 시간복잡도를 가지게 됩니다.

 

위 함수에서 똑같은 값이 나오는 power(a, n//2)를 정의해주면 power함수의 호출을 반으로 줄일 수 있습니다.

def power(a, b):
    if b == 0:
        return 1
        
    x = power(a, b//2)

    if b % 2 == 0:
        return x * x
    
    else:
        return x * x * a

따라서 분할 정복 방식은 \(O(logN)\)의 시간복잡도 안에 거듭제곱 연산을 수행할 수 있습니다.