20.12.15 (Algorithms)fibonacci

fibonacci

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

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
• 재귀함수를 이용해 구현해야 합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.
• 피보나치 수열을 구하는 효율적인 알고리즘(O(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

의사코드

이번 fibonacci 문제는 메모이제이션(메모해서 동일한 반복수행을 제거)을 통해 최적화하는 방법에 대해 물어본다.
1. 먼저 수를 저장할 메모를 [0,1] 로 저장한다.(0과 1일 경우 그냥 리턴할 수 있도록)
2. 그 다음 피보나치 함수 스코프 안으로 들어가서
3. (0과 1일 경우 그냥 리턴할 수 있도록) 만약, memo의 n번째 인덱스가 undefined 가 아니면 memo[n]을 리턴.
4. (0과 1이 아닐 경우) memo[n]은 재귀함수로 n에서 1을 뺀것과 2를 뺀것을 더해서(피보나치)
5. memo[n]을 리턴

코드

const memo = [0, 1];
let fibonacci = function (n) {
  if (memo[n] !== undefined) {
  	return memo[n];
  }
  memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return memo[n];
};