[LeetCode] Fibonacci Number

문제링크

Fibonacci Number - LeetCode

 

 

주어진 수의 피보나치 수를 구하는 문제

접근 방법

3가지 방법으로 풀이하였다.

1. 단순 for문 사용

let output = 0;
let num1 = 1;
let num2 = 0;

if(n === 0) return 0;
if(n === 1) return 1;

for(let num = 2; num <= n; num++){
    output = num1 + num2;
    [num1, num2] = [output, num1];
}​

num1과 num2를 그 다음수로 업데이트 해주는 것이 핵심이다. (구조분해할당)

 가장 빠르고 가장 적은 공간을 사용한다. (변수밖에 사용하지 않기 때문에)

2. dp 사용

const dp = new Array(n).fill(0);
dp[0] = 0;
dp[1] = 1;

for(let num = 2; num <= n; num++){
    dp[num] = dp[num-1] + dp[num-2];
}

dp[num] = dp[num-1] + dp[num-2] 라는 피보나치 공식을 그대로 사용하면 된다.

가장 이해하기 쉽지만 n 크기의 배열을 하나 만들기 때문에 메모리 효율이 상대적으로 떨어진다.

3. 재귀함수 사용

const fibo = (n) => {
    if(n === 1) return 1;
    if(n === 0) return 0;

    return fibo(n-1) + fibo(n-2);
}​

가장 코드가 짧고 비교적 간단한 재귀라서 이해하기 편하다.

하지만 가장 느리고 재귀마다 함수가 call stack에 쌓이기 때문에 메모리 효율도 낮다.

 

// 단순 for문 (구조분해할당)

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let output = 0;
    let num1 = 1;
    let num2 = 0;
    
    if(n === 0) return 0;
    if(n === 1) return 1;
    
    for(let num = 2; num <= n; num++){
        output = num1 + num2;
        [num1, num2] = [output, num1];
    }
    
    return output
};

 

// dp

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

 

// 재귀

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    const fibo = (n) => {
        if(n === 1) return 1;
        if(n === 0) return 0;
        
        return fibo(n-1) + fibo(n-2);
    }
    
    return fibo(n)
};