[JS]_daily coding #28

[SEB FE] Section3 Daily Coding 07_power

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

입력
인자 1: base
number 타입의 자연수 (base >= 2)
인자 2: exponent
number 타입의 정수 (exponent >= 0)

출력
number 타입을 리턴해야 합니다.
실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 합니다.

주의사항
Math.pow, 거듭제곱 연산자 사용은 금지됩니다.
시간복잡도 O(logN)을 만족해야 합니다.
나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 됩니다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다.

문제 접근

문제의 주의사항에 나온 것처럼 Math.pow(), **, 반복문을 사용하면 쉽게 거듭제곱을 구할 수 있다. 그러나 주어지는 exponent로 엄청 큰 값이 들어올 경우를 생각해보면 거듭제곱하는 연산 횟수도 그만큼 늘어나야 하기 때문에 시간복잡도가 O(N)이다.
일단, 거듭제곱의 성질을 살펴 보면,

지수를 2로 나눠서 결과를 반으로 쪼개면서 답을 구해나갈 수 있다. 지수가 홀수인 경우와 짝수인 경우를 나눠서 처리해주면 된다.

코드

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

  let tmp = power(base, Math.floor(exponent/2))

  let result = tmp * tmp % 94906249 //94,906,249보다 작으면 tmp * tmp가 출력

  if(exponent % 2 === 0) {
    return result  //짝수
  } else {
    return base * result % 94906249 // 홀수
  } 
}

주말에 더 공부할 것

• 분할정복
• 재귀 + 이번주 문제들 다시 풀어보기