[JS 알고리즘] Toy 2 - fibonacci ( O(n) )

노션에서 마이그레이션 중이며, 순서는 랜덤하게 업로드하고 있습니다.

 

해당 문제는 코드스테이츠의 Toy problem을 출처로 합니다.
2022.03.30

 

 

문제

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

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

 

작성 코드 (Javascript)

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  const fibo = (n, r) => {
    if (n <= 0)
      return 0;
    if (n === 1)
      return r[n] = 1;
    else if (r[n] > 0)
      return r[n];
    return r[n] = fibo(n-2, r) + fibo(n-1, r);
  }

  return fibo(n, []);
}

 

Reference Code (Javascript)

// naive solution: O(2^N)
// let fibonacci = function (n) {
//   if (n <= 1) return n;
//   return fibonacci(n - 1) + fibonacci(n - 2);
// };

// dynamic with meoization: O(N)
// 이미 해결한 문제의 정답을 따로 기록해두고,
// 다시 해결하지 않는 기법
// fibo(10)
// = fibo(9) + fibo(8)
// = fibo(8) + fibo(7) + fibo(7) + fibo(6)
// 여기까지만 보아도 동일한 문제가 중복으로 계산되는 것을 알 수 있다.
let fibonacci = function (n) {
  const memo = [0, 1];
  const aux = (n) => {
    // 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.
    if (memo[n] !== undefined) return memo[n];
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
    memo[n] = aux(n - 1) + aux(n - 2);
    return memo[n];
  };
  return aux(n);
};

 

 

---

• 참고한 블로그
• 관련 강의: 피보나치수열의 시간복잡도