[정수론] 분할 정복(재귀)를 이용한 거듭제곱 - 파이썬 코드 및 설명

목표

- 분할 정복(재귀)를 이용하여 어떤 수의 거듭제곱을 구하는 방법을 알아본다.

과정

 어떤 수의 거듭제곱을 어떻게 구할 수 있을까요? 다른 말로, 어떤 수 A를 N번 곱한 수를 어떻게 구할 수 있을까요? 단순하게 생각하면 실제로 A라는 수를 N번 곱하여 얻을 수 있습니다. 허나, N이 너무 클 때는 그 수를 일일이 N번 곱해야하기 때문에 많은 양의 연산을 피할 수 없습니다. 분할 정복(재귀) 기법을 사용하면 연산의 횟수를 극단적으로 줄일 수 있는데요. 분할 정복(재귀) 기법을 이용해 N번의 연산을 logN번으로 줄이는 방법에 대해 알아보겠습니다.

 

 이해를 위해 어떤 수 A를 2라고 가정해보겠습니다. 2의 N제곱 수는 다음과 같이 나타낼 수 있습니다.

2의 N제곱수는 위와 같이 짝수 홀수 여부에 따라 다르게 표현할 수 있습니다. 이것을 트리 구조로 시각화 하면 다음과 같습니다.

전체 트리의 높이는 N을 1이 될 때까지 제곱근 한 횟수가 되기 때문에 logN이 됩니다. 이것을 코드로 구현하면 다음과 같습니다.

결과

def pow(base, exp):
    if exp == 1:
        return base
    elif exp % 2 == 0:
        half = pow(base, exp // 2)
        return half * half
    else:
        half = pow(base, exp // 2)
        return base * half * half