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

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))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

---

 

피보나치 수열이란?

피보나치 수열(Fibonacci Sequence)은 이전 두 항의 합으로 이루어지는 수열로, 0과 1로 시작하여 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657 등으로 이어진다.  이탈리아의 수학자 피보나치(Leonardo Fibonacci)의 이름에서 유래했다. 피보나치는 13세기에 'Liber Abaci' 라는 책에서 이 수열을 소개하면서, 이 수열이 토끼 번식 문제와 관련이 있다는 것을 설명하였다.

피보나치 수열은 상당히 단순한 단조 증가(monotonically increasing) 수열로 0번째 항은 0, 1번째 항은 1, 그 외 항은 전번, 전전번 항의 합으로 표현된다.

피보나치수열 방식

 

피보나치 수열을 구하는 방법

(1) 재귀 함수를 사용하여 피보나치 수열 구하기

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(10)); // 55

(2) 반복문을 사용하여 피보나치 수열 구하기

function fibonacci(n) {
  let a = 0, b = 1, c;
  if (n === 0) return a;
  for (let i = 2; i <= n; i++) {
    c = a + b;
    a = b;
    b = c;
  }
  return b;
}
console.log(fibonacci(10)); // 55

(3) 메모이제이션(memoization)을 사용하여 피보나치 수열 구하기

function fibonacci(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}
console.log(fibonacci(10)); // 55

위 예시 코드들은 각각 재귀함수, 반복문, 메모이제이션을 이용한 방법! 각 방법마다 시간 복잡도가 다르므로, 문제의 요구사항에 맞게 적절한 방법을 선택하여 사용해야한다.

1. 재귀 함수를 사용한 방법
   재귀 함수를 사용한 경우, 각 항마다 2개의 하위 항을 호출하므로 O(2^n)의 시간 복잡도를 갖는다. 걸리는 시간이 제일 길다..
2. 반복문을 사용한 방법
   반복문을 사용한 경우, n번의 반복이 이루어지므로 O(n)의 시간 복잡도를 갖는다.
3. 메모이제이션을 사용한 방법
   메모이제이션을 사용한 경우, 이미 구한 항은 배열이나 객체에 저장해두고, 해당 항이 필요할 때마다 참조하여 계산한다. 따라서, 각 항마다 1번의 연산만 수행하므로 O(n)의 시간 복잡도를 갖는다.

따라서, 시간 복잡도를 고려할 때는 재귀 함수보다는 반복문이나 메모이제이션을 사용하는 것이 효율적이다!

---

문제풀이 

기존 피보나치 코드를 작성해서 실행을 돌리면 시간을 초과한다고 나왔다. n값이 낮을때는 정상적으로 보이지만 높아질 수록 정상작동을 하지 않는걸 볼 수 있었다.

O(2^n)의 시간 복잡도를 갖는 기존 식은 중복호출이 많을 경우 런타임이 길어진다.. O(n)의 시간복잡도를 갖는것으로 고려하기.

어떠한 문제를 풀 때, 작성한 소스가 입력된 값에 대해 문제를 해결하는 데 필요한 시간을 시간복잡도라고 하며, 위의 문제와 같이 풀 경우 이 시간복잡도가 가파르게 증가하게 된다.

n번째 피보나치 항을 여러 번 계산한다고 해서 그 값이 달라지지 않는다. 즉, 한번 구한 항을 기록(memoization) 해 둔 다음, 그 값이 필요할 때 꺼내쓸 수 있다면 굉장히 효율적으로 작동 할 것이다.

동적계획법 알고리즘은 아래와 같이 새워보기!
1. 문제를 부분 문제로 나눈다.
2. 가장 작은 문제를 해를 구한 뒤, 테이블에 저장한다.
3. 테이블에 저장되어있는 데이터로 전체의 문제의 해를 구한다.

function fibonacci(n) {
  // 피보나치수열 재귀함수 사용해서 풀 수 있지만 시간복잡도를 생각해봐야함
  // 시간복잡도는 한번 연산했던값은 연산으로 구분하지 않음으로 O(N)이 됨

  // if (n <= 1) return n;
  // return fibonacci(n - 1) + fibonacci(n - 2);
  // 기존코드는 런타임이 오래걸려 에러남.

  //일단 초기 배열이 [0, 1]에서 시작하여 배열의 요소를 누적해 나가는 방법
  //그리고 이미 구해놓은 것은 배열의 요소로 저장해놓기. 그래야 런타임이 초과되지 않는다
  const cache = [0, 1]; // 내부 메모이제이션 함수 정의
  const memoFib = (n) => {
    if (cache[n] !== undefined) { 
      return cache[n]; // 캐시에 값이 존재하면 바로 반환
    }
    cache[n] = memoFib(n - 1) + memoFib(n - 2); // 캐시에 값이 없으면 재귀적으로 호출하여 계산하고 캐시에 저장
    return cache[n]; // 계산된 값을 반환
  };
  return memoFib(n); // 메모이제이션 함수를 호출하여 n번째 피보나치 수열 값을 반환
}

위에 작성 코드에서는 cache 배열을 선언하여 메모이제이션에 사용한 것.
풀어보자면 이전에 계산한 값은 cache 배열에 저장되며, 계산하기 전에 먼저 cache 배열에 해당 값이 있는지 확인한다. 만약 cache 배열에 이미 계산한 값이 있다면, 해당 값을 반환하고, 없으면 계산한 후 cache 배열에 저장한다.

먼저 cache 배열을 초기화하기 위해 0번째와 1번째 요소를 할당해준다. 그리고 재귀 함수인 memoFib를 선언. 이 함수는 매개변수로 피보나치 수열의 인덱스 n을 받는다.

진행시 cache 배열에 저장된 값이 있는지 확인합니다. 만약 있다면 해당 값을 반환하고, 없다면 memoFib(n - 1)과 memoFib(n - 2)를 호출하여 이전 두 항을 더한 값을 구해준다. 그리고 구한 값을 cache 배열에 저장하고, 반환시킨다. 마지막으로 memoFib(n)을 호출하여 피보나치 수열의 n번째 값을 반환한다.

이 방법은 재귀적인 구조를 사용하여 구현한것이고 메모이제이션을 사용해서 중복 계산을 피할수 있게된다. 그래서 함수 호출 시간 복잡도는 O(N)이며, 재귀함수를 쓴것보다 메모이제이션을 사용하여 스택 쌓여서 에러도 안나고 빠른 속도로 계산할 수 있게된다! 

레퍼런스코드

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

 

 

참조 :
https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95

https://velog.io/@shitaikoto/Algorithm-fibonacci-on