[LeetCode] Fibonacci Number - 자바스크립트 풀이

문제 링크

 

1. 접근 방법

 

(1) 이전에 계산해 둔 결과를 활용하여 지금 연산을 하는 메모이제이션 방식이다.

 

(2) cache 객체를 만들어 놓고, 함수를 재귀적으로 실행할 때 cache에 해당 값이 이미 존재하면 그 값을 리턴한다. 

        if (Object.keys(cache).includes(n)) {
            return cache.n;
        }

 

(3) cache에 해당 값이 없으면, 값을 리턴한다. 피보나치 배열에서는 인덱스 0, 1은 각각 값이 0과 1이고, 그 다음 인덱스부터는 이전 인덱스에 해당하는 값과 이이전 인덱스에 해당하는 값을 더한 값이 할당된다. 

        if (n < 2) {
            result = n;
        } else {
            result = recur(n - 2) + recur(n - 1);
        }

 

(4) cache에 인덱스 n에 대한 값을 저장한다.

        cache.n = result;

 

2. 전체 해답

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let cache = {};
    const recur = (n) => {
        let result;
        if (Object.keys(cache).includes(n)) {
            return cache.n;
        }
        
        if (n < 2) {
            result = n;
        } else {
            result = recur(n - 2) + recur(n - 1);
        }
        cache.n = result;
        return result;
    }
    return recur(n)
};

 

다른풀이

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let array = new Array(n).fill(0);
    array[0] = 0;
    array[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        array[i] = array[i - 2] + array[i - 1];
    }
    
    return array[n];
};