일반 거듭제곱과 빠른 거듭제곱

개념

$A^B$ 는 $A$ 를 $B$ 번 곱한 값입니다. 자연수 $A$ 에 대해 $A^0=1$ 입니다.

일반 거듭제곱

결과를 $1$ 로 시작해 $A$ 를 $B$ 번 곱합니다. 곱셈 횟수는 $B$ 번이므로 시간은 $O(B)$ , 추가 공간은 $O(1)$ 입니다.

분할 정복

지수가 짝수이면 $A^{2k}=(A^k)^2$ , 홀수이면 $A^{2k+1}=(A^k)^2A$ 입니다. $A^k$ 를 한 번 구해 저장하고 제곱하면 같은 부분 문제를 반복해서 계산하지 않습니다.

$3^5$ 를 구할 때 $3^2$ 를 먼저 구하고, 그 결과를 제곱한 뒤 $3$ 을 한 번 더 곱합니다. 재귀의 종료 조건은 지수 $0$ 이며 반환값은 $1$ 입니다.

계산을 숫자로 쓰면 $3^2=9$ , $3^4=9\times9=81$ , $3^5=81\times3=243$ 입니다. 지수가 짝수이면 동일한 두 거듭제곱의 곱으로 나누고, 홀수이면 한 번 곱할 $A$ 를 따로 남기는 방식입니다.

지수 $16$ 을 처리하는 과정은 $16\to8\to4\to2\to1\to0$ 으로 줄어듭니다. 각 단계에서 지수를 절반으로 줄인 거듭제곱을 한 번만 구해 재사용하므로, 지수가 클수록 곱셈을 반복하는 방법보다 계산량이 줄어듭니다. 같은 거듭제곱을 재귀 호출로 두 번씩 계산하면 중복 계산이 늘어나 빠른 거듭제곱의 시간복잡도를 얻을 수 없습니다. 지수가 크거나 큰 지수의 거듭제곱을 어떤 수로 나눈 나머지가 필요한 문제에서 사용합니다.

복잡도

지수를 $B$ 라고 합니다. 분할 정복에서는 지수가 매번 절반으로 줄어듭니다. 나머지만 필요한 문제는 각 곱셈 후 모듈러 연산을 적용할 수 있습니다.

연산	시간복잡도	공간복잡도
일반 거듭제곱	$O(B)$	추가 $O(1)$
재귀 빠른 거듭제곱	$O(\log(B+1))$	재귀 $O(\log(B+1))$

예제

문제

$A$ 의 $B$ 제곱을 구하여라.

입력

첫째 줄에 밑 $A$ 와 지수 $B$ 가 공백을 사이에 두고 주어진다. $1\le A\le10$ ; $0\le B\le8$ 이다.

출력

거듭제곱 값을 출력한다.

예제 코드

C++20

#include <iostream>

using namespace std;

int power(int a, int b) {
    int x;

    if (b == 0) return 1;
    x = power(a, b / 2);
    x *= x;
    if (b % 2 == 1) x *= a;
    return x;
}

int main() {
    int a, b;

    cin >> a >> b;
    cout << power(a, b) << '\n';
}

Java 17

import java.util.*;

public class Main {
    static int power(int a, int b) {
        int x;

        if (b == 0) return 1;
        x = power(a, b / 2);
        x *= x;
        if (b % 2 == 1) x *= a;
        return x;
    }

    public static void main(String[] args) {
        Scanner in;
        int a, b;

        in = new Scanner(System.in);
        a = in.nextInt();
        b = in.nextInt();
        System.out.println(power(a, b));
    }
}

Python 3

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


a, b = map(int, input().split())
print(power(a, b))

2.10.2 Exponentiation

개념