[TIL] 2022..3.2. (백준 1629번,백준 11444번 풀어보기)

코플릿 (21_power)

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

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

<내가 짠 코드>

 

Math.pow나 거듭제곱 연산자가 금지돼서... for문 말고 다른 방법은 떠오르지 않았다. 저 방법은 시간복잡도가 O(n)(아마...ㅎㅎ.?)일텐데,

O(logN)은 어떻게 해야할지 감이 안잡혔다. 레퍼런스보고도 한참 고민함.

이 문제는 분할정복으로 해결할수 있다.

 

분할정복이란? 문제를 작은 부분으로 쪼개 나가면서 해결해가는 장식이다.

 

2^10=2^5*2^5

2^5=2^2*2^2*2^1

2^2=2^2

 

2^10은 하나하나 곱하자면, 10번을 곱해야겠지만

이런식으로 단 네번만에 문제를 해결할 수 있다.

 

수도코드를 작성해보면,

1. exponent를 절반으로 나누고, 소숫점은 버린다.

2. 이 exponent를 재귀함수에 넣고,

3. 그 결과값을 곱해준다.

4. 근데 앞에서 소숫점은 버려줬으므로, exponent가 홀수값이라면 base를 한번더 곱해줘야함.

5. exponent가 1이 되면 멈춘다.

 

function power(base, exponent) {
  if(exponent===0) return 1
  const half = parseInt(exponent/2);
  const temp = power(base,half)
  const answer =(temp*temp)%94906249;
  if(exponent%2===1) return (answer*base)%94906249;
  else return answer
}

 

그럼 이런 결과가 나온다.

 

근데 저 temp를 변수를 선언하지않고 그냥 괄호에 넣어서 해버리면 런타임에러가 뜨던데, 아마 시간이 저렇게 변수할당해서 하는거랑은 다른가보다.

(다시 생각해보니 너무 당연한...! 저렇게 변수할당해서 하면, power를 한번만 하지만 할당하지 않고 그냥 괄호에 넣어버리면 power를 두배 해버리고... 그 두배가 모이고... 그럼 이렇게 분할정복하는 의미가 없다 😨)

 

피보나치수열도 이렇게 분할정복으로 풀 수 있다.

행렬의 거듭제곱으로 풀수 있다고 한다. 근데 이거는 너무어려워서, 일단 나중에 보기로 하고 저번에 이해가 안됐던 피보나치수열의 DP알고리즘을 이해하게 되었다.

 

코플릿 피보나치

let fibonacci = function (n) {
  if(n===0) return 0
  if(n===1) return 1
  return fibonacci(n-1)+fibonacci(n-2)
};

이게 내가 생각했던(사실 이렇게도 풀지못했던...^^)코드이다.

재귀하면서 점점 더해가는방식!

시간복잡도는 O(n^2)이다.

하지만 이렇게하면 중복되는 수가 생긴다.

그것도 계속계속 중복되고 엄청많이 중복된다.

그래서 이 중복되는 부분을 기억하여 사용하면 시간이 줄어든다.(DP알고리즘)

let fibonacci = function (n) {
  let cache = [0,1];
  function fib(num){
    if(cache[num]!==undefined) return cache[num]
    cache[num] =fib(num-1)+fib(num-2)
    return cache[num]
  }
  return fib(n)
};

이 코드에서 if(cache[num]!==undefined)와 if(cache[num])인 경우가 답이 달랐는데,

if(cache[num])으로 하게되면 0에서 조건문 실행이 안되기 때문이다!(falsy한 값)