문제설명

설계 과정

설계도 그렇고, 초기 코드도 그렇고 문제에서 일단 하라는대로 재귀를 이용하여 만들긴 했다. 하지만 계속 시간 초과가 뜰 것이라고 예상했다..... 과연

초기 코드

function fivo(n){
    if(n===0||n===1) return n;
    else{
        return fivo(n-1)+fivo(n-2);
    }
}

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

결과

결과는 역시나 시간초과와 런타임 에러 가 떴다. 이는 나타낼 수 있는 숫자의 범위를 넘어서, 이를 표현 못하기 때문에 이러한 결과가 나오는 것이다. 흔히 말해서 오버 플로우가 걸린 것이다. 그래서 문제에서도 이를 방지하기 위해 1234567 을 나눈 값을 나타내라고 하는 것이다.
이를 해결하기 위해선 모듈러 산술 이라는 것이 사용된다. 모듈러 연산중에 아래와 같은 공식을 활용하여 문제 접근이 가능하다.

(A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C

개선 코드

function solution(n) {
    
    var fivoArr= [0,1];
    if(n>2){
        for(var i =2;i<n+1;i++){
            fivoArr[i] = (fivoArr[i-1] + fivoArr[i-2])%1234567;
        }
    }
    return fivoArr[n];
}

위의 모듈러 공식을 통해서 이러한 접근이 가능하며, 이는 피보나치 수열이 숫자의 범위를 넘어가지 않게 단계별로 체크하는 기능을 하며 오버 플로우가 걸리지 않게 해준다.