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

재귀로 풀이 시도

 

 

function solution(n) {
    return fibonacci(n);
}

const memoization = {
    0: 0,
    1: 1,
    2: 1
}

function fibonacci(n) {
    if (memoization[n] !== undefined) return memoization[n];
    
    const answer = ((fibonacci(n - 1) % 1234567) + (fibonacci(n - 2) % 1234567)) % 1234567;
    if (memoization[n] === undefined) memoization[n] = answer;
    return answer;
}

 

주어지는 n의 범위가 2 이상 100,000 이하인 자연수이므로 상당히 범위가 넓어서 Memoization 처리가 필요하다. 

 

모듈러 연산의 성질 (A + B) % C = ((A % C) + (B % C)) % C 을 사용하지 않으면 자바스크립트의 정수 범위를 넘어서면서 Overflow가 일어나 제대로된 답을 얻을 수 없다. (참조1)

 

위 성질을 사용해서 처리해도 마지막 테스트 케이스 2개가 실패한다. Memoization을 해줬음에도 100,000 까지를 처리하기엔 재귀로 호출한 call stack이 한도치를 넘어서 그렇다. (참조2)

 

 

배열로 풀이 성공

 

function solution2(n) {
    const fibonacci = [0, 1];

    for (let i = 2; i <= n; i++) {
        fibonacci.push(((fibonacci[i - 1] % 1234567) + (fibonacci[i - 2] % 1234567)) % 1234567);
    }

    return fibonacci[n];
}

 

재귀 대신  배열을 사용하면 간단하게 해결할 수 있다.

 

 

 

참조

참조1 [모듈러 연산의 성질] - https://programmers.co.kr/questions/11969 : (A + B) % C = ((A % C) + (B % C)) % C

참조2 [재귀 호출 깊이 한도]  - https://jireh.tistory.com/14