동적 계획법(Dynamic Programming) : 시간 초과 OR 런타임 에러 해결하기

재귀 호출 시 n 이 50 이상일 때,

• 시간 초과가 나거나
• Python이나 JavaScript 등 일부 언어에서는 런타임 에러가 난다.
  • 런타임 에러가 나는 이유: 일부 언어는 재귀 호출을 할 수 있는 횟수가 정해져 있고, 횟수를 넘어 재귀 호출을 하면 런타임 에러를 내도록 설계되어 있음.

해결 방법 : 재귀 호출 대신 for문 사용하자.

 

예제) n번째 피보나치 수를 1234567으로 나눈 나머지를 구하라.

 

// 재귀 호출 풀이
// 이 경우 n의 값이 50이상 일 때, Maximum call stack size exceeded 에러 발생.
function fibo(n) {
  if (n < 2) return n;
  
  return fibo(n-2) + fibo(n-1);
}

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

// for문 풀이
function solution(n) {
  if (n < 2) return n;
  
  const fibo = [0, 1];
  
  for (let i = 2; i <= n; i++) {
    fibo.push((fibo[i-2]+ fibo[i-1]) % 1234567);
  }
    
  return fibo[n];
}

💡 n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가, 오버플로우가 발생할 수 있음.

   ==> 모든 단계에서 % 연산을 사용하여, 모든 연산에서 오버플로우가 일어나지 않게 만들어 주자.

---

출처 : 프로그래머스) 코딩테스트 연습 힌트 모음집 - 파트1. 피보나치 수

- https://school.programmers.co.kr/learn/courses/14743/lessons/116433

- https://school.programmers.co.kr/learn/courses/14743/lessons/116435