문제 설명
매개 변수인 n,k을 받아 거듭제곱을 실행하고, 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 한다.
power(3, 40) // 19334827Number 타입 유효 범위
Number 타입은 정수, 실수, 양수, 음수, 지수 등 모든 숫자 값을 나타낼 수 있고, 64비트 형식의 IEEE-754 표준을 따르기 때문에 유효 범위는 일반적으로 -9007199254740991 ~ 9007199254740991까지이다. 이 범위를 벗어나면 정확도 문제가 발생하기 때문에, 보통 큰 숫자를 계산 계산 할 때는 위와 같이 큰 숫자로 나눈 나머지로 계산한다.
분할 계산
- 시간복잡도: 0(log N)
- 거듭제곱을 할 때 고속으로 거듭제곱할 수 있는 방법 중 하나는 분할제곱 방법이다. 예를 들어 2^11을 구할 때 일반적인 계산 법으로는 11번의 연산을 반복해야 되지만, 분할 계산의 경우 3번이면 답을 구할 수가 있다.
코드
function power(base, exponent) {
if (exponent === 0) return 1
if(exponent % 2 === 0){
let half = power(base ,(exponent / 2)) % 94906249
return (half * half) % 94906249
}
else{
let half = power (base , (exponent-1)/2)% 94906249
return (((half * half) % 94906249 )* base) % 94906249
}
}
코드 설명
- 지수가 0인 경우 모든 제곱 수가 1이 되니 1을 리턴해 준다.
- 지수가 홀수인 경우 위의 분할 계산법 처럼
N^((k-1)/2) * N^((k-1)/2)의 공식을 적용하여 재귀를 돌아준다. - 지수가 짝수인 경우도 마찬가지로 분할 계산법을 이용해준다.
N^(k/2) * N^((k/2)
참조
