-
거듭제곱 알고리즘 :: 마이구미알고리즘 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 % 2 == 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 % 2 == 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
123456789101112131415161718192021private 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;}}cs 반응형'알고리즘' 카테고리의 다른 글
비트마스크(BitMask) 는 무엇인가? :: 마이구미 (16) 2019.10.20 [자료구조] 스택, 큐는 무엇인가? :: 마이구미 (2) 2019.09.07 힙정렬(Heap Sort) 알고리즘 :: 마이구미 (3) 2018.04.17 합병정렬 알고리즘 :: 마이구미 (0) 2018.04.14 퀵소트 알고리즘 :: 마이구미 (12) 2018.04.10