Toy#2 fibonacci

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

let output = fibonacci(0);
console.log(output); // --> 0

output = fibonacci(1);
console.log(output); // --> 1

output = fibonacci(9);
console.log(output); // --> 34

Advanced
피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

풀이

1. fibonacci 재귀 함수로 시도

function fibonacci(n) {
  if(n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

➡️ 아래와 같은 오류 발생. Advanced의 내용을 고려해 보자

---

2. 피보나치 수열을 구하는 효율적인 알고리즘(O(N))

동적계획법
간단한 하위 문제를 해결하면서
좀 더 복잡한 상위 문제로 나아가는 방식 (상향식)

O(N): dynamic with meoization
이미 해결한 문제의 정답을 따로 기록해두고
다시 해결하지 않는 기법

• 1번에서 사용한 fibonacci 재귀 함수의 성능은 O(2^n)
• 동적 계획법을 사용하면 성능이 O(N)으로 향상

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

  const fibo = (n) => {
    if(arr.includes(arr[n])){
      return arr[n];
    }
    arr[n] = fibo(n-1) + fibo(n-2);
    return arr[n];
  }

  return fibo(n);
}

/*
n = 5 

1. fibo(5) 실행, arr = [0, 1]
arr[5] = fibo(4) + fibo(3)

2. fibo(4) 와 fibo(3) 실행
fibo(4) = fibo(3) + fibo(2)
fibo(3) = fibo(2) + fibo(1)

2-1. fibo(3) 
= fibo(2) + fibo(1) 

fibo(2)의 경우,
arr[2] = fibo(1) + fibo(0) = 1
=> arr = [0, 1, 1]

2-1-1. fibo(3) 
= fibo(2) + fibo(1) 
= 1 + 1 = 2
=> arr = [0, 1, 1, 2]

2-2. fibo(4) 
= fibo(3) + fibo(2)
= 2 + 1
= 3
=> arr = [0, 1, 1, 2, 3]

3. arr[5] = fibo(4) + fibo(3) = 5
=> arr = [0, 1, 1, 2, 3, 5]

*/