Algorithm 18 : power

설명

두 수를 입력받아 거듭제곱을 리턴해야 한다.

예시

let output = power(3, 40);
console.log(output); // --> 19334827

생각

exponent가 0과 1인 경우를 제외하고 나머지는
exponent의 수 만큼 base를 곱해주면 되겠다.

풀이

function power(base, exponent) {
  // todo: 여기에 코드를 작성합니다.
  let num = base
  if (exponent === 0) {
    return 1
  }
  if (exponent === 1) {
    return base
  }
  //exponent 개수만큼 base를 곱해나가기.
  for (let i = 0; i < exponent - 1; i++) {
    num = num * base
  }
  return num
}

문제점

주의사항에서는 시간복잡도 O(logN)을 만족해야하고,
연산 중간마다 94,906,249로 나눠주라고 하는데 이게 무슨의미인지 몰랐다.

레퍼런스 풀이

function power(base, exponent) {
 if (exponent === 0) return 1;

 const half = parseInt(exponent / 2);
 const temp = power(base, half);
 const result = (temp * temp) % 94906249;

 if (exponent % 2 === 1) return (base * result) % 94906249;
 else return result;
}

깨달은 점

temp temp를 하는 이유는 거듭제곱 알고리즘의 효율성을 위해서다. 2^1,2^2,2^3,...해서 원하는 거듭제곱인 2^8(예시)을 구하는 것이 아니라, 2^4 2^4 = 2^8이 더욱 효율적이기 때문에 temp끼리 곱해주는 것이다.