[Javascript] 파보나치 수 (12945)

문제링크

 

접근방법

두가지 방법이 있다.

1. 재귀적으로 탐색
종료 조건 : num === 0 일때 0, num === 1 일때 1을 return하고
재귀 조건으로 return fibo(num-1) + fibo(num-2) 를 계속해서 호출하면 된다.

const fibo = (num) => {
    if(num === 1) return 1;
    else if(num === 0) return 0;
    let result = (fibo(num-1) + fibo(num-2)) % 1234567
    return result
}​

작은 수에서는 정상 작동 하지만 (%1234567)을 어디에 넣어야 프로그래머스에서 통과하는지 모르겠다..

2. dynamic Programing 방식으로 탐색
n 크기의 dp 배열을 만들고 초기값 dp[0], dp[1]을 할당 해준 뒤,
 
dp[n] = dp[n-1] + dp[n-2]라는 피보나치 공식을 그대로 사용하여 결과값을 구한다.

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

 

 

// dp 방법

function solution(n) {
    let dp = Array.from({length : n}, () => 0);
    
    dp[0] = 0;
    dp[1] = 1;
    for(let num = 2; num <= n; num++){
        dp[num] = (dp[num-1] + dp[num-2]) % 1234567
    }
    
    return dp[n];
}

// 재귀 방법

function solution(n) {
    
    const fibo = (num) => {
        if(num === 1) return 1;
        else if(num === 0) return 0;
        let result = (fibo(num-1) + fibo(num-2)) % 1234567
        return result
    }
    
    return fibo(n);
}