toy problem 09

문제 : power

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

 

• Math.pow 사용 금지
• O(logN)을 만족해야 한다.
• 나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문이다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 된다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가야 한다.

 

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

문제의 접근

시간 복잡도 O(logN)을 만족해야한다. 먼저 O(logN)의 복잡도를 가지는 알고리즘은 무엇일까? 라는 질문에서 접근을 해야한다. 이 복잡도를 가진 다는 말은 연산을 거듭할 수록 데이터의 양이 줄어든다는 뜻이다.

 

function power(base, exponent) {
  // todo: 여기에 코드를 작성합니다.
  if(exponent === 0){
    return 1
  }
  const half = power(base, parseInt(exponent/2))
  const result = (half * half) % 94906249;
  if(exponent%2 === 0){
    return result
  }else{
    return (result * base) % 94906249
  }
}

 

parseInt() 함수는 문자열 인자를 구문분석하여 특정 진수(수의 진법 체계에 기준이 되는 값)의 정수를 반환합니다.

나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문