거듭제곱 더 더 더 빠르게 with 파이썬(Python)

똑같은 수나 문자를 여러 번 곱하는 것을 거듭제곱이라고 한다.

 

흔히 우리가 말하는 2의 4제곱(2^4=16), 5의 3제곱(5^3=125) 등은 거듭제곱을 표현한 것이다.

 

당연히 코드를 통해서 이를 빠르게 계산할 수 있다.

 

반복문 사용

 

a의 n제곱 값을 구하고 싶을 때, for문을 사용해 직관적으로 다음과 같은 코드를 작성할 수 있다.

 

def power(a, n):
    ans = 1
    for _ in range(n):
        ans *= a
    
    return ans

 

재귀함수 사용

 

반복문이 아닌 재귀적 방식으로도 위 코드를 구현할 수 있다.

 

a의 n제곱을 쭉 풀어보면 다음과 같다.

 

http://tcpschool.com/codingmath/square

위 식은 부분문제로 나눌 수 있다.

 

만약 a의 n제곱이 아닌 a의 n+1제곱을 구하고자 할 땐 a^n의 값에 a를 한 번 더 곱해주면 되는데, 즉 a의 n+1 제곱은 a^n * a가 된다.

 

실제 수에 대입해본다고 했을 때, 2의 4제곱(2^4=16)을 구하기 위해선 2의 3제곱(2^3=8)에 2를 한 번 더 곱해주면 되는 것과 같다.

 

이를 점화식으로 표현하면 a^n = a^(n-1) * a가 된다.

 

Base Case는 n이 1일 때 a를 리턴하도록 할 수 있다 (a의 1제곱은 a이므로).

 

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

 

 

위에  살펴본 두 방식은 모두 n번만큼의 연산을 요구하므로 시간복잡도는 O(n)으로 표현할 수 있다.

 

분할정복 활용

지수법칙을 잘 활용하면 a의 n제곱을 보다 효율적으로 구할 수 있다.

 

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

 

이를 활용하면, a^n을 a^(n / 2) * a^(n / 2)로 표현할 수 있다.

 

수식으로 표현해 한 눈에 들어오기 힘들다면 수를 직접 넣어서 살펴보자.

 

2^4은 2^2 와 2^2를 곱한 것이다.

 

즉, 2^4 = 2^2 * 2^2인 것이다.

 

그렇다면 n이 2로 나누어 떨어지지 않는 홀수라면 어떻게 될까? 그냥 a를 한 번만 더 곱해주면 간단히 해결된다.

 

즉, a = 2, n = 5라고 했을 때,

 

2^5 = 2^2 * 2^2 * 2 로 표현할 수 있다.

 

이는 즉, 2^2, 2^2, 2^1을 모두 곱해준 것으로, 지수를 모두 더해주면 2 + 2 + 1 = 5로, 2^5이 된다.

 

이러한 접근 방식은 n을 매번 2로 나눠 더 작은 문제로 만들어 해결하는 분할정복 방식이라고 할 수 있다.

 

분할 정복을 이용할 땐 n을 2로 나누는 과정에서 n이 1일 때 다음 재귀함수에 들어가는 n은 0이 될 수 있으므로(1 // 2 = 0), Base Case에 n이 0일 때 리턴해줄 값도 명시해준다.

 

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) * power2(a, n//2)
    
    else: # n이 홀수일 때
        return power(a, n//2) * power2(a, n//2) * a

 

무언가 훨씬 효율적이게 보이긴 하지만 아쉽게도 위 함수 역시 O(n)의 시간복잡도를 가진다.

 

그렇다면 분할정복 방식도 반복문이나 처음에 구현한 재귀함수와 비교해 별 다른 차이를 보이지 않는 것일까?

 

물론 그렇지 않다. 어차피 똑같은 값이 나오는 power(a, n//2)를 두 번 곱해주면 power함수의 호출을 반으로 줄일 수 있다.

 

이를 코드로 구현하면 다음과 같다.

 

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

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

 

사실 Base Case는 n이 0일때만 처리해주면 된다. n이 1이 될 때는 power(a, 1 // 2)가 호출되므로 이는 즉 power(a, 0)을 호출하기 때문이다.

 

이 방식은 O(logN)의 시간복잡도 안에 거듭제곱 연산을 수행할 수 있다.