[23.02.21] Daily Coding 22 - fibonacci

동화·2023년 2월 21일

dailyCoding

Daily-Coding

목록 보기

12/15

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]
}