Toy02.fibonacci

Judo·2020년 12월 14일

알고리즘

문제

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

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

입력

인자 1 : n

number 타입의 n(n은 0 이상의 정수)

출력

number 타입을 리턴한다.

주의사항

재귀함수를 이용해 구현해야 합니다.
반복문(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

Advanced

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

내가 구현한 코드

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  /**
   * 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.
   * (n - 1) + (n - 2) === n번째 항의 수 
   * 
   */
  if(n === 0) return 0;
  if(n === 1) return 1;  

  return fibonacci(n - 1) + fibonacci(n - 2);
}

레퍼런스 코드

//dynamic with meoization
//이미 해결한 문제의 정답을 따로 기록해두고,
//다시 해결하지 않는 기법 
function fibonacci(n) {
  const memo = [0, 1]; // 피보나치 수열에 0, 1번째 수는 알고 있으므로 메모해둔다.
  
  const aux = n => {
    if (memo[n] !== undefined) return memo[n];//메모장에 n번째 수가 존재한다면 그 수 리턴
    memo[n] = aux(n - 1) + aux(n - 2); 
    //메모장에 n번째 수가 존재하지 않는다면 aux 함수를 재귀 호출 
    //base조건은 메모장에 n번째 수가 존재하는 경우. 즉, aux(1) === 1 , aux(0) === 0이 된다.
    return memo[n];
  }
  
  return aux(n);//결국 aux(n)을 한다면 메모장에 n번째 수가 계산되어 리턴된다.
  
}