• 거듭제곱 알고리즘 :: 마이구미
    알고리즘 2018. 6. 6. 06:24

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

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

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

    백준 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);
        }
    }
    cs


    반복문 거듭제곱


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


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

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

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

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

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


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

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

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


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

    확인해보자.


    거듭제곱 알고리즘


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


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


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

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


    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 % == 0) {
            return temp;
        } else {
            return a * temp;
        }
    }
    cs


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


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

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

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


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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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 % == 0) {
            return temp;
        } else {
            return a * temp % c;
        }
    }
    cs


    댓글 0

Designed by Tistory.