알고리즘 7 : power

문제

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

입력

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

 

 

코드

function power(base, exponent) {
  // todo: 여기에 코드를 작성합니다.
  if(exponent===0)return 1

  let half = parseInt(exponent/2)
  
  let ans = power(base,half) // 계산량 줄임
  // return ans*ans보다 return result 하는게 계산량이 줄어든다고 함. 그래서 한 변수에 넣은것
  let result = ans*ans%94906249  
  if(exponent%2===0){
    // return ans*ans 라고 하면 여기서 또 계산해야함. 
    // 근데 result는 위에서 계산된 것이기 때문에 계산없이 그냥 리턴함
    return result 
  }
  else return result*base%94906249 // 마찬가지
    
}

 

 

설명

시간복잡도 O(logN) 은 점점 계산량이 줄어든다.

let half = parseInt(exponent/2)
  
  let ans = power(base,half) // 계산량 줄임

위 과정에서 계산량이 줄어들게 된다. 

원래대로 한다면 power(2,10) 일 때 2*2*2*2*......*2*2 = 1024 , 곱셈을 10번하는데

half를 사용하면 2*2*2*2*2 = 512, ans = 512*512 로 곱셈을 7번한다.

이는 exponent가 커질 수록 계산량 감소도 커질 것이다.

 

  // return ans*ans보다 return result 하는게 계산량이 줄어든다고 함. 그래서 한 변수에 넣은것
 let result = ans*ans%94906249  


if(exponent%2===0){//짝수일 때


  // return ans*ans 라고 하면 여기서 또 계산해야함. 
  // 근데 result는 위에서 계산된 것이기 때문에 계산없이 그냥 리턴함
    return result 

}
 
 
 else return result*base%94906249 // 홀수일 때,

그다음 ans*ans를 result에 넣어주어서 그 뒤에서는 ans*ans라는 계산을 하지 않게 된다.