[프로그래머스] 피보나치 수 - 자바스크립트

문제

코딩테스트 연습 - 피보나치 수

 

풀이

간단한 문제지만 문제 조건을 유의해야 한다.

 

n번째 피보나치 수를 1234567으로 나눈 나머지를 구하는 문제이다.

 

주어진 수 n은 1 <= n <= 100000 의 범위를 가진다.

 

이 문제를 재귀함수로 풀려고 하면
n의 값이 100,000일 때 Maximum call stack size exceeded 에러가 발생한다.

말 그대로 너무 재귀가 많이 호출되어 콜스택의 크기를 초과했다는 것.

 

재귀가 아닌 단순 반복문으로 10만번 정도는 거뜬하다.

반복문을 사용하자.

 

K번째 피보나치 수는 1234567로 나눈 나머지 값을 저장해준다.

주어진 수 N번째 피보나치 수만 1234567로 나눈 나머지 값을 구하는 것이 아니라, 매 스텝마다 나눈 나머지를 값으로 삼아야 한다.
=> 1000번째 피보나치 수만 해도 4.346655768693743e+208으로 매우 큰 값이다.

 

이를 바탕으로 코드를 작성해보자.

 

코드

function solution(n) {
  if (n < 2) return n;
  const fibo = { 0: 0, 1: 1 };
  for (let i = 2; i <= n; i++) fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1234567;
  return fibo[n];
}

조건을 잘 이해하면 간단한 코드로 해결할 수 있다.