[JavaScript] toy 02 fibonacci

문제

아래와 같이 정의된 피보나치 수열 중 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))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.
  
  

풀이

로직

이 문제는 내가 3월 20일에 적은 이 글과 유사한 문제처럼 보이지만, 다른 점이 있다.

1. 이전과 똑같은 풀이를 내면 테스트 케이스에서 ‘시간 초과’가 뜬다.
2. 입력 인자 n이 이전 문제(0 이상 15 이하)와 달리 ‘0 이상’이라는 말만 있다. 즉 입력 숫자 크기에 따라 푸는 데에 엄청난 시간이 걸릴 수도 있다는 뜻이 된다.

그렇기에 더 효율적인 피보나치 수열 함수를 만들고자 한다.
이전엔 재귀함수 자체의 의미를 생각해서 ‘큰 것을 풀기 위해 작은 것을 다시 푼다’라는 방법으로 풀었었다.
이것을 조금 다르게 생각해보자.

작은 것을 푼 다음엔 저장하자. 그리고 큰 것을 풀 때 그 값을 불러오기만 하자.

1. 피보나치 수열을 적어둘 배열을 만든다. 이미 정해진 0번째와 1번째는 미리 적어 둔다. (let arr = [0, 1];)
2. 이미 계산한 것을 다시 계산하지 않기 위해 처음 계산된 것을 저장하기 위한 피보나치 함수(fibo)를 만든다.
   • 이전의 재귀함수로 푼 것과 동일한 형식이다.
3. fibo 함수에 저장된 값은 바로 불러낼 수 있도록 리턴값도 미리 if문으로 지정해 둔다. (해답코드의 6~7번째 줄)

해답 코드

function fibonacci(n) {

  let arr = [0, 1];
  
  let fibo = (n) => {
    if (arr[n] !== undefined){ 
      return arr[n];
    }
    arr[n] = fibo(n - 1) + fibo(n - 2);
    return arr[n];
  };
  
  return fibo(n);
}

기타 - 한마디

이전 피보나치 문제는 O(2^N) 복잡도로 풀었다면 이번 문제 풀이는 O(N)복잡도이다.
왜 그런지 잘 생각해 보고, 앞으로도 이런 효율적인 방법으로 문제를 풀 수 있게끔 훈련하자!

카카오페이로 커피사기 ❤️ 토스 계좌로 커피사기 ❤️