[Algorithm] power

사실 1차원 적으로 거듭제곱을 구하는 식은 Math.pow()이다.

Math.pow(base, exponent);

일단 문제에서는 거듭제곱 연산자 사용하지 않아야하고
시간복잡도 O(logN)을 만족해야한다는 점이다.

시간복잡도 O(logN)은 up&down게임을 생각해보면 된다고 블로그를 정리했었다.
https://velog.io/@iooi75/TIL-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84

그리고 이와 함께 재귀적인 특성도 적용해야한다..

아직 재귀를 내가 원하는 대로 쓰지 못해서 효율적인 알고리즘을 구현하지 못했다.

Reference를 보면서 적용해보고 이해해보도록 하겠다.

function power(base, exponent) {
  // base가 밑이고 exponent가 제곱이다.
  if (exponent === 0){ 
    //밑 변의 뭐가 와도 0제곱을하면 1이다. 이건 고등학교 수학 ㅇㅈ? 
    return 1;
  }

  const half = parseInt(exponent / 2); 
  //parseInt는 소숫점을 없애준다. O(logN)을 구할 때 항상
  //나누기 2를 하면서 탐색하기 때문에 소숫점 처리를 반드시 해줘야한다.
  const temp = power(base, half);
  //재귀에 들어갈때 인자값을, 밑변은 그대로 다시 들어가고, 제곱을 2로나눈 값으로 넣어준다.
  
  const result = (temp * temp) % 94906249;
  // %연산에 의해서 (temp * temp)의 나머지를 구하더라도 9406249보다 작으면 다시 (temp * temp)가 출력된다. 
  //(작으니까) 1 % 100 = 1 , 50 % 100 = 50

  if (exponent % 2 === 1){
    //2로 항상 나누고 소수점을 띠어버리기 때문에 나머지가 1이 계속나온다.
    return (base * result) % 94906249;
    // 밑을 (temp * temp) % 94906249;의 결과로 곱 해준다.
    // 여기서 중요한데 이것이 power()의 return이 된다는 것.
    // 다시 temp의 return이 전달되고 반복 된다.
  }
  
  else{
    return result;
  }
}

따로 for문을 돌리지 않고 재귀를 이용해서 구했다.
O(logN)을 만족하기 위해 계속 2로 나눠서 재귀로 들어간 것이 포인트