아주 큰 수가 제곱수 안에 있을 경우 94,906,249를 나눠 나머지를 다시 제곱해 줘서 컴퓨터가 표현할 수 있는 수 안에서 결과를 구해야 한다.
Math.pow()는 사용 금지한다.
2. 시도 1
function efficientPow(baseNum, exponent) {
let result = 1;
for(let i = 0; i < exponent; i++) {
result = result * baseNum;
if(result > 94906249) {
result = result % 94906249;
}
}
return result;
}
답은 맞았다.
하지만 효율적이지 못했다. 시간 복잡도를 통화하지 못했다.
반복문이 아닌 재귀 함수 등을 이용하는 것도 또 다른 방법이 될 수 있지만, 똑같은 방식으로 반복문을 재귀 함수로 고친다고 해도, 시간 복잡도를 줄이지 못할 것이라고 생각했다.
그래서 거듭제곱의 특징을 알아보고 시간 복잡도를 줄일 수 있지 않을까?라고 생각했다.
3. 지수법칙
'고등학교' 에서 배운 지수법칙(나무위키에서 캡쳐했다)
위의 식을 이용하면 내가 곱해야 할 지수를 절반으로 줄일 수 있다고 생각했다. 즉 2의 5승 곱하기 2의 5승은 2의 10승과 같다면, 2의 5승까지만 알게 되면 더 이상 2의 6승 등을 알 필요가 없어진다.
4. 시도 2
function efficientPow(baseNum, exponent) {
if(exponent === 0){
return 1;
}
// 재귀의 탈출 조건이 된다.
let halfExponent = efficientPow(baseNum, Math.floor(exponent/2));
// 제곱의 지수의 절반인경우를 구한다.
let result = (halfExponent * halfExponent) % 94906249;
// 만약, 표현할 수 있는 최대 수를 넘기면 나눠서 나머지에 다시 절반인 제곱수를 곱한다.
if(exponent % 2 === 0){
return result;
}else{
return (result * baseNum) % 94906249;
}
// 이후, 지수가 짝수이면 그대로 리턴, 아니라면 다시 곱해서 최대수가 넘으면 사눠서 나머지를 리턴한다.
}
성공!
정말 절반만 계산해서 시간 복잡도를 크게 떨어뜨릴 수 있었다.
나는 중1 시절 수학을 놨다. 사실 저 지수법칙과도 초면이었다... 역시 또 수학공식을 모르니 생각이 넓게 미치지 못하는 것 같다. 코드를 쓰는 문법에 익숙해지면 알고리듬 공부를 할 때는 수학에 대해 공부하는 것도 나쁘지 않은 전략이 될 것 같다.
