거듭제곱 알고리즘 :: 마이구미

이 글은 거듭제곱에 대한 알고리즘을 다룬다.

거듭제곱의 성질을 이용하여 성능을 올리는 과정을 확인한다.

백준 알고리즘 문제에서는 다음과 같은 문제를 해결할 수 있다.

백준 1629번 곱셈 - https://www.acmicpc.net/problem/1629

거듭제곱이란 주어진 수를 주어진 횟수만큼 곱하는 연산이다.

똑같은 수를 여러번 곱하기를 원할 때, 이용한다고 우리는 아마 중학교 때 배웠을 것이다.

만약 거듭제곱을 구하는 알고리즘을 작성해야한다면, 쉽게 구현할 수 있을 것이다.

일반적인 방법으로 재귀함수와 반복문 방식은 각각 작성한다면, 다음과 같다.

재귀함수 거듭제곱

public static int pow(int a, int n) {
    if (n == 0) {
        return 1;
    } else {
        return a * pow(a, n - 1);
    }
}

반복문 거듭제곱

public static int pow(int a, int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= a;
    }
    return result;
}

위와 같은 방식의 문제점은 무엇일까?

n 이 클수록 성능이 낮다는 것이다.

왜냐하면 실행 횟수로 보면, n번 만큼 실행해야하기 때문이다.

반복문이 재귀함수보다 성능이 좋기 때문에 "반복문을 쓰면 되지 않은가?" 생각할 수 있다. (재귀 방식은 함수를 호출하는 비용이 크다)

하지만 결과적으로 시간복잡도 O(n) 이기에, n 이 커질수록 성능이 좋지않다.

시간복잡도를 줄여 개선된 알고리즘을 만들어야한다.

이는 거듭제곱의 성질을 통해 분할정복을 이용하여 개선할 수 있다.

* 분할정복이란 문제를 작은 부분으로 쪼개나가면서 해결하는 방식

개선된 결과는 시간복잡도 O(logn) 의 결과를 낼 수 있다.

확인해보자.

위에서 얻은 일반화된 성질을 통해 코드를 작성하면 다음과 같다.

public static int pow(int a, int b) {
    if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        int n = pow(a, b / 2);
        return n * n;
    } else {
        int n = pow(a, (b - 1) / 2);
        return a * n * n;
    }
}

중복되는 코드가 많고 리팩토링이 가능할 것만 같다.

리팩토링 후의 코드는 다음과 같다.

public static int pow(int a, int b) {
    if (b == 0) {
        return 1;
    }
 
    int n = pow(a, b / 2);
    int temp = n * n;
 
    if (b % 2 == 0) {
        return temp;
    } else {
        return a * temp;
    }
}

결과적으로 시간복잡도가 O(n) => O(logn) 으로 줄여졌다.

백준 알고리즘 문제를 해결할 수 있다.

문제의 핵심은 시간복잡도를 줄이는 것이다.

그렇기에 다룬 알고리즘을 통해 단순히 나머지 연산을 추가해주면 쉽게 해결할 수 있다.

Github 백준 1629번 곱셈 코드 - https://github.com/hotehrud/acmicpc/blob/master/algorithm/divide-conquer/1629.java

private void solve() {
    A = sc.nextInt();
    B = sc.nextInt();
    C = sc.nextInt();
    System.out.println(pow(A, B, C));
}
 
public static long pow(int a, int b, int c) {
    if (b == 0) {
        return 1;
    }
 
    long n = pow(a, b / 2, c);
    long temp = n * n % c;
 
    if (b % 2 == 0) {
        return temp;
    } else {
        return a * temp % c;
    }
}