22_fibonacci

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.
0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

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

/*function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  if(n===0) return 0;
  if(n===1) return 1;
  return fibonacci(n-1)+fibonacci(n-2);
} 처음 코드 : 중복으로 피보나치 함수가 불러와지므로 재귀함수 호출의 횟수가 많아진다.
*/

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); //memo배열의 인덱스에 값을 불러와준다.
};