JavaScript Algorithm - power, 거듭제곱

 

 

문제 설명

두 수를 입력받아 거듭제곱을 리턴해야 합니다. base, exponent라고 되어있습니다. 

base는 밑이고exponent는 지수라고 생각하면 된다. 

종합적으로 물제를 풀려면 Math.pow와 거듭제곱 연산자 사용을 하면 안되고 최종 결과값에서 94,906,249을 나누는 식으로도 문제를 풀면 해결할 수 없다. 연산 중간 중간에 94,906,249을 나누어야 해결할 수 있다.

입력

인자 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

 

풀이1 : 나는 위의 문제 사항을 제대로 이해하지 못했고 반복문이 떠올라서  바로 코딩을 해서 제출했다.

결과는 7개 테스트 중 6개 통과.  통과하지 못한 테스트 로그에서는 효율적이지 않은 알고리즘이라는 로그가 출력됐다.

function power(base, exponent) {
    // todo: 여기에 코드를 작성합니다.
     //let answer = base ** exponent;
     let answer = 1;
     for (let i = 1; i < exponent + 1; i++) {
       answer = answer * base;
     }
     console.log(answer);
     let answer2 = answer % 94906249;
     console.log(answer2);
     return answer2;
   }

 

풀이2 : 반복문보다 재귀가 더 효율적이지 않을까 하고 풀었으나 이것도 효율적인 알고리즘이 아니었다.

결과는 7개 테스트 중 6개 통과.  통과하지 못한 테스트 로그에서는 효율적이지 않은 알고리즘이라는 로그가 출력됐다.

function power(base, exponent) {
  let answer = recur(base, exponent);
  let answer2 = answer % 94906249;
  return answer2;
}

let recur = function (number, exponent) {
  if (exponent > 0) {
    return number * recur(number, exponent - 1);
  } else {
    return 1;
  }
};

 

 

발생한 에러와 테스트 코드를 보면 다음과 같다. 

효율적이지 않은 알고리즘이 원인이다.

//Test Result
AssertionError: expected NaN to be 53237722
    at Assertion.fail (/node_modules/should/cjs/should.js:275:17)
    at Assertion.value (/node_modules/should/cjs/should.js:356:19)
    at /submission/index.test.js:82:38
    at Array.forEach (<anonymous>)
    at Context.<anonymous> (/submission/index.test.js:81:17)
    at processImmediate (internal/timers.js:464:21) ...
    
    
//Test Code
function () {
    for(let i = 0; i <25; i++){
      testcases.forEach(({ base, exponent, answer }) => {
        power(base, exponent).should.equal(answer);
      });
    }
  }

 

 

그럼 모든 테스트를 통과한 코드는?

풀이3: 다음과 같이 40이라는 지수를 계속 숫자를 줄인다음에 연산처리를 하는 방식으로 하여 컴퓨터가 나타낼 수 있는 숫자로 연산할 수 있게 알고리즘을 변경해서 테스트가 통과했다.  이 알고리즘이 O(logN)을 만족한 알고리즘이다.

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

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

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

 

실행 로그 

~/work/C-Cpp_Algo/Javascript/toy$ node 09_power.js 
half 20
half 10
half 5
half 2
half 1
half 0
temp 1
result 1
temp 3
result 9
temp 9
result 81
temp 243
result 59049
temp 59049
result 70159437
temp 70159437
result 19334827
19334827