코딩테스트 문제 2

문제

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

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

주의사항

재귀함수를 이용해 구현해야 합니다.
반복문(for, while) 사용은 금지됩니다.
함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

입출력 예시

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

작성 코드

function fibonacci(n) {
  let fibonacciValues = [0, 1] // 0,1 번째 index값은 고정이다.

  function fibonacciRecursion (i, n){
    if (i > n){ // 재귀 탈출 조건이다.
      return fibonacciValues[fibonacciValues.length -1]
    }else{ 
      let fibonacciIndexValues = fibonacciValues[i-2] + fibonacciValues[i -1]
      fibonacciValues[i] = fibonacciIndexValues  //
      fibonacciRecursion(i+1, n) // i라는 파라미터에 1씩 더해서, n을 넘어서는 순간 탈출을 한다.
    } 
  }

  if(n <= 1){
    return fibonacciValues[n]
  }
  else{
    fibonacciRecursion(2,n) // let fibonacciValues = [0, 1]  이렇게 선언되어있기때문에  0,1번째 인덱스는 첫번째 조건문에서 리턴이 된다. 
    return fibonacciValues[fibonacciValues.length -1]
  }
}

레퍼런스 코드 (시간복잡도를 계산)

// 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);
};