Toy_#2. fibonacci

- 문제:

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

입출력 예시:

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

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

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

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

풀이:

(주의) 재귀함수를 사용해야 하고, 효율적인 알고리즘(O(N))으로 풀어야 한다.

아래처럼 단순 재귀함수를 사용하면 효율적이지 못하다.

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

memoization을 활용하자.

function fibonacci(n) {
  const memo = [0, 1];
  const aux = (n) => {
    if (memo[n] !== undefined) {
      return memo[n]
      // memo라는 배열에 답이 있는 경우 해당 값을 리턴한다.
    } else {
      // 답이 없는 경우 재귀를 사용하고, 동시에 기록되는 답을 이용하여 풀 수 있다.
      memo[n] = aux(n - 1) + aux(n - 2);
      return memo[n];
    }
  }
  return aux(n);
}