문제 : power

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

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

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

문제의 접근

단순한 문제이다 물론 시간 복잡도를 고려하지 않는다면 말이다.

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

말 그대로 exponent의 값 만큼 곱셈을 실시하고 일정 숫자가 되면 나눠준다.
하지만 이는 시간복잡도 O(logN)을 만족하지 못한다 그렇다면 이를 만족하기 위해서는 어떻게 해야할까.
먼저 O(logN)의 복잡도를 가지는 알고리즘은 무엇일까? 라는 질문에서 접근을 해야한다. 이 복잡도를 가진 다는 말은 연산을 거듭할 수록 데이터의 양이 줄어든다는 뜻이다. 그렇다면 연산의 실행할 때마다 데이터의 양도 줄어드는 알고리즘으로 계산을 해보자

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

코드가 조금 복잡해 졌지만 거듭제곱의 특징을 이용한 알고리즘이다. 최대치의 절반값을 구해서 서로 곱해준다면 원하는 결과가 도출된다. 이 점을 이용해서 데이터의 절반에 적용하고 또 그걸 위해서 절반에 적용하기를 반복한다. 결과는 물론 이상없이 도출되고 있다 하지만... 여전히 효율적인 알고리즘이라고는 하지 않는다. 왜죠...?😕

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

이유는 모르겠지만 위와 같이 수정하니깐 된다...? 진짜 뭐지.......? 알 수 없는 알고리즘의 세계다🥲

문제를 통해 생각해 볼 것

문제는 솔직히 매우 좋은 접근이었다고 생각한다. 하지만 2% 가량 부족한 접근이었다. 시작은 좋았으나 마무리가 허술해서 구글링을 조금해서 완성할 수 있었던 코드다. 먼저 어차피 같은 값을 내는데 있어 처음에는 한수를 두번씩 계속 실행하게 두었는데

이는 구글링을 통해 한변수에 선언해 줌으로서 stack을 절반정도 줄일 수 있었다. 그리고 마지막 부분의 수정사항은 도데체 어떤 차이가 있는지 잘 모르겠다...