[Lv.2] 피보나치 수 (오버플로우 현상)

프로그래머스 코딩테스트

1. 문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

입출력 예

3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

2. 풀이

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

코드는 쉽다. 다만 문제는..

3. 알아야할 사항

피보나치수 graph

 1) for문 안에서 fiv[i] 에 계산값을 할당해줄 때 고려할 것 :

피보나치 수는 수가 높을수록 매우 빠르게 커지기 때문에, 47번째 피보나치 수는 2,971,215,073로, 이때 부터 32비트 int 변수의 오버플로우를 야기한다. 그러므로 모든 단계에서 1234567을 나눈 나머지값을 미리 계산해서 할당해준다. 

 

 2) 또한, 피보나치수열같은 미리 계산이 가능한 수열일 경우에, 시간복잡도 해결을 위해 실제 코드를 작성할 때에는 미리 계산값을 배열에 저장해두고, 가져다 사용하며, 더 높은 계산이 필요할 경우 배열의 맨 마지막부터 계산할 수 있도록하여 최적화한다.