Power
다이나믹 프로그래밍을 이용한 거듭제곱 구하기
Problem
두 수를 입력받아 거듭제곱을 리턴해야 합니다.
입력
인자 1: base
- number 타입의 자연수 (base >= 2)
인자 2: exponent
- number 타입의 정수 (exponent >= 0)
출력
number 타입을 리턴해야 합니다. 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 합니다.
주의사항
Math.pow, 거듭제곱 연산자 사용은 금지됩니다.
시간복잡도 O(logN)을 만족해야 합니다.
나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 됩니다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다.
입출력 예시
let output = power(3, 40);
console.log(output); // --> 19334827
Solution
단순히 반복문으로 거듭제곱을 구하는 문제가 아니라, 시간복잡도O(logN) 충족을 위해 반복횟수를 줄일 아이디어가 필요하다.
\(2^{10}\)을 구하는 과정을 예로들어 아이디어를 떠올리면,
\(2^{10} = 2^5 * 2^5\)
\(2^5 = 2^2 * 2^2 * 2\)
\(2^2 = 2^1 * 2^1\)
단순히 지수만큼 곱하는 시간복잡도O(N)보다 적은 반복횟수로 계산하므로 시간복잡도 O(logN)이 충족된다.
이를 점화식으로 표현하면 다음과 같다.
지수가 짝수일 때,
\(base^{exponent} = base^{exponent/2} * base^{exponent/2}\)
지수가 홀수일 때,
\(base^{exponent} = base^{exponent/2의 몫} * base^{exponent/2의 몫} *base\)
또한, 이는 다이나믹 프로그래밍의 두가지 요건
1. 최적 부분구조 : 큰 문제는 작은문제로 나뉠수있으며 작은문제의 해답을 모으면 큰문제를 해결할 수 있다.
2. 중복 부분문제 : 구했던 작은문제의 해답을 또 구해야한다.
을 충족한다.
따라서 메모이제이션을 활용한 탑다운 방식으로 구현할 수 있다.
// file:'Power.js'
// 결과 테이블 초기화
const d = [];
for (i=0; i<100; i++){
d.push(0)
}
function power(base, exponent) {
// console.log(`exponent = ${exponent}`)
// 종료 조건
if (exponent === 0) return 1; // base의 0승은 1이다.
if (exponent === 1) return base; // base의 1승은 base이다.
// 결과 테이블에 값이 있다면 이미 계산된 것이므로 출력한다.
if (d[exponent] != 0) return d[exponent];
// 지수가 짝수일 때, 계산한 결과를 점화식에 따라 결과 테이블에 메모한다.
if (exponent % 2 == 0) {
d[exponent] = (power(base, exponent/2) * power(base, exponent/2)) % 94906249
}
// 지수가 홀수일 때, 계산한 결과를 점화식에 따라 결과 테이블에 메모한다.
else {
d[exponent] = (power(base, Math.floor(exponent/2)) * power(base, Math.floor(exponent/2)) * base) % 94906249
}
// console.log(`d[${exponent}] = ${d[exponent]}`)
// 결과 테이블의 값을 출력한다.
return d[exponent]
}
또한 문제에 명시된 것 처럼, 컴퓨터가 나타낼 수 있는 수의 범위를 넘을 수 있기 때문에 계산 시마다 94906249의 나머지를 반환해주어야한다.
3의 40승을 구할 때, 다음과 같이 호출되고 결과 테이블에 값이 저장되는 것을 확인할 수 있다.
let output = power(3,40)
// console.log
exponent = 40
exponent = 20
exponent = 10
exponent = 5
exponent = 2
exponent = 1
exponent = 1
d[2] = 9
exponent = 2
d[5] = 243
exponent = 5
d[10] = 59049
exponent = 10
d[20] = 70159437
exponent = 20
d[40] = 19334827