Level2️⃣ - 피보나치 수

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

피보나치 수는 흔히 재귀함수로 구현할 수 있다.

function fibo(n){
    if(n<=1) return n;
    else return fibo(n-1) + fibo(n-2);
}


function solution(n) {
   return fibo(n) % 1234567;
}

하지만 이 문제에서는 두 가지 상황을 고려해야한다.

n이 10만 이하의 자연수이기 때문에 재귀함수로 구현하면 호출에 제한이 있기 때문에 콜스택이 초과된다.

그렇기 때문에 for 문을 사용해서 피보나치를 구현해야한다. DP라고 부르기도 하는데 아직 이 부분에 대해서는 연습이 필요하다.

 

function fibonacci(n) {
  let k = 1234567;
  const dp = new Array(n + 1);
  
  dp[0] = 0;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n] % k;
}

피보나치 수를 메모이제이션 할 배열을 만들고 점화식을 활용해 for문을 돌면서 피보나치 수를 완성한다.

하지만 이 코드도 오류가 발생한다.

이유는 n이 큰 경우 n번째 피보나치 수를 표현할 수 있는 자료형의 범위를 넘겨 오버플로우가 발생하기 때문이다.

이럴 때는 모듈러 연산을 고려해야한다.

(A+B) % K = (A%K + B%K) % K

(A*B) % K = (A%K * B%K) % K

즉, 한번에 나누는 것이 아니라 개별적인 요소들로 먼저 나누고 마지막에 나누어도 값은 동일하다는 것이다.

dp[n] = dp[n-1] + dp[n-2] 이므로 모듈러 연산을 적용하면,

dp[n] % k = (dp[n-1] + dp[n-2]) % k = (dp[n-1]%k + dp[n-2]%k) % k 이다.

function solution(n) {
  const k = 1234567;  
  const dp = new Array(n + 1);

  dp[0] = 0;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = (dp[i - 1] % k + dp[i - 2] % k) % k;
  }

  return dp[n] % k;
}

따라서 다음과 같이 모듈러 연산을 통해 오버플로우를 막아야한다.