[23.02.21] Daily Coding 22 - fibonacci

1. fibonacci
   아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.
   (반복문 사용x)

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

7번째 피보나치 수가 나오는 과정 (n=7)을 나열해보면,

0
1
1 = 0 + 1
2 = 1 + 1
3 = 2 + 1
5 = 3 + 2
8 = 5 + 3
13 = 8 + 5

이를 함수로 표현해보면

f(n) = f(n-1) + f(n-2)
n>=2인 자연수, f(0) = 0 , f(1) = 1

즉 f(n)은 숫자를 입력받아서 총 n+1 개를 더하게 되는 함수가 된다.

function fibonacci(n) {
  if ( n <= 1 ) {
    return n;
  }
  
  return fibonacci(n-1) + fibonacci(n-2);
}

이는 재귀함수로 쉽게 정의할 수 있는데, 이렇게 되면 시간 초과가 나온다.

왜냐면 fibonacci(7)을 하면 fibonacci(6), fibonacci(5), fibonacci(4)... 얘들을 전부 계산하고, 또
fibonacci(6)에서 또 fibonacci(5), fibonacci(4), fibonacci(3)... 생각만 해도 골치아프다.
즉 Big O의 의 계수법칙에 의하여 O(2^n)번을 실행한다는 것. (사실상 n-1)
n>2를 넘어가게 되면, 한 함수에서 재귀 호출이 두 번이나 일어나기 때문이다. (시간복잡도)

💫 memoization & 레퍼런스❗️

이미 수행한 계산 결과를 배열로 저장해두고 거기서 값을 꺼내쓰는 방식을 이용해보자. ( memoization 설명은 이 곳에)
반복문을 사용하지 말라고 했기에, 이 부분이 정답이었다.

function fibonacci(n) {
  const memo = [0, 1]

  // 재귀를 위한 보조 함수(auxiliary function -> aux)을 선언)
  const aux = (n) => {
    // 이미 푼 적이 있으면, 메모해 둔 정답을 리턴한다.
    if (memo[n] !== undefined) return memo[n]

    // 새롭게 풀어야하는 경우, 문제를 풀고 메모(memo[n])해둔다.
    memo[n] = aux(n - 1) + aux(n - 2)
    return memo[n]
  };
  return aux(n)
}

💫 sliding window

같이 일정한 범위를 가지는 것을 유지한 채 이동하며 계산되는 방법, 최소한의 데이터만을 활용하는 방법 (가장 작은 경우의 수부터 하나씩 이동하는 느낌으로 계산된 값을 누적해나가는 방법)

function fibonacci(n) {
  let fst = 0, snd = 1

  if(n<=1) return n
  for (let size = 2; size <= n; size++) {
    const next = fst + snd
    fst = snd
    snd = next
  }
return snd
}

💫 tabulation

• 어떤 값을 구하기 위해 순서대로값을 구해 나감으로써 중복된 계산을 하지 않고 다음값을 빠르게 구해나가는 방법
• 테이블을 그려놓고 하나씩 진행하며 저장하는 방식이다. 제일 최소의 단위부터 문제의 값을 테이블에 저장해 나가며, 제시된 문제를 해결할 수 있으면 거기서 해당 값을 리턴(상향식)

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

---

예전에 배웠던 내용이고, 또 기초 중에 기초였는데
머리가 딱딱하게 굳어진 것만 같아 복습하면서 재귀함수를 공부했다.
재귀함수는 역시 그림그려가면서 해야 제 맛..