프로그래머스 | 피보나치 수열

📌 문제

피보나치 수는 첫째와 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로, Fn = Fn-1 + Fn-2라는 공식으로 표현할 수 있습니다.
처음 두 항은 1이고, 그다음 항들은 2 (=1+1), 3 (=1+2), 5 (=2+3)이므로 전체 수열은 1, 1, 2, 3, 5 , 8, 13, 21 ... 형태를 띱니다.
피보나치 수열에서 n번째 항의 값을 구하세요.

💔 solution 1

피보나치 수열은 재귀를 사용해 구현할 수 있습니다.

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
  // 1보다 작을 경우 n을 반환하고, 그렇지 않을 경우 fib(n-1) + fib(n-2)를 재실행
}

하지만 위와 같은 식은, 같은 fib(n)을 여러 번 호출하기 때문에 큰 수가 올 경우 시간이 많이 걸리게 됩니다.

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(1) = fib(0) = 1 

이처럼 fib(5)를 계산할 때 같은 값이 두 번 이상 평가되게 됩니다. 따라서 추천되지 않습니다.

이런 방식의 해결 방법은 이미 평가된 값을 어딘가에 저장해놓는 식으로 최적화하거나, 재귀가 아닌 반복문을 사용하는 것입니다.

💻 solution 2

function solution(n) {
    var answer = 0;

    let a = 1;
    let b = 1;
    for (let i = 3; i <= n; i++){
        let c = a + b;
        a = b;
        b = c;
    }

    if ( n === 1 || n === 2 ){
        answer = 1;
    } else {
        answer = b;
    }
    
    return answer;
}

위의 식은 1번째, 2번째 항의 경우 결과 값이 1, 그 이후의 3번째 항부터는 c에 a+b를 저장하고, a에 현재의 b값을, b에 현재의 c값을 저장하여 다음 턴에서 그 두 값을 다시 c에 저장하는 방식으로 반복하고 있습니다.

---

👍 다른 해결식

function solution(n) {
    let fibo = [0,1,1];
    for (let i = 3; i <=n; i++){
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
  
    if ( n === 1 || n === 2 ){
        answer = 1;
    } else {
        answer = fibo[n];
    }
    
    return answer;
}