[프로그래머스] 피보나치 수 - 해설

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

피보나치는 당연히 재귀함수로 풀어야된다고 생각했지만, 해당 문제는 시간 초과가 나서 풀 수가 없다.

조금 더 빠르게 풀 수 있는 방법으로, 2부터 계산하며 답을 채워가는 것이다.

function solution(n) {
    const devide = 1234567
    const arr = [0,1]
    for(let i=2;i<=n;i++) arr.push((arr[i-1]+arr[i-2])%devide)
    return arr[n]
}

이렇게 할 경우 피보나치 수에 대한 계산을 매번 반복할 필요가 없다. (한번 계산 후, 배열에서 가져다 쓰기 때문)

0과 1의 피보나치 수를 배열에 넣어 놓은 후, 차례대로 피보나치 수를 채워나간다.

여기서 또 조심해야할 것이, 수가 너무 커져서 오버플로우가 난다.

BigInt를 이용하거나, 위 코드처럼 피보나치 수를 push전에 나눈다.