[23.02.21] Daily Coding 22 - fibonacci

동화·2023년 2월 21일
0

Daily-Coding

목록 보기
12/15
post-thumbnail
  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]
}






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

6개의 댓글

comment-user-thumbnail
2023년 2월 21일

재귀는 정말 좀만 안보면 머리 속에서 리셋이 되어버리는군요. 동화 님 덕분에 재귀 다시 차근차근 공부하고 갑니다! 근데 글이 가독성이 너무 좋아요! 굿!!

답글 달기
comment-user-thumbnail
2023년 2월 22일

다양한 풀이방법 덕에 재귀 공부하고 가욤 ㅎㅎ 볼때마다 새로운 느낌은 기분탓이겠죠 ,,ㅎ

답글 달기
comment-user-thumbnail
2023년 2월 23일

slicing window 까먹고 있었는데 다시 배워갑니다 ~~! 저도 오늘 메모이제이션 블로깅했습니다 ^.^

답글 달기
comment-user-thumbnail
2023년 2월 23일

재귀 어렵죠.. ㅠㅠ 다시 기억하고 가게되서 좋네용 ㅎㅎ

답글 달기
comment-user-thumbnail
2023년 2월 26일

메모이제이션 오랜만에 보니 감회가 새롭네요,, 대단히 감사합니다. 상당히 고맙습니다. 제 뇌를 일깨워주셔서^^

답글 달기
comment-user-thumbnail
2023년 2월 26일

피보나치 수열 memoization 방법만 알고있었는데 다른 풀이 방법도 있었네요! 동화님 덕분에 공부하고 갑니다 😆

답글 달기