피보나치수열의 고찰

야 나 개 ·2021년 12월 13일

다이나믹프로그래밍

알고있지만..리즘

목록 보기

2/9

피보나치 수열 구현하기

알고리즘에 대해 첫 시작은
피보나치 다이나믹프로그래밍으로 시작 합니다!!!

무작정 피보나치 수열 구현하기

반복문 코드

function fibonacci(num) {
  // TODO: 여기에 코드를 작성합니다.
  let fibArr = [];

  for(let i = 0; i <= num; i++){
    if( i < 2 ){
      fibArr.push(i)  
    }else {
      fibArr.push(fibArr[i-2] + fibArr[i-1])
    }
  }return fibArr;
}

재귀함수 코드

//naive solution: O(2^N)
function fib(n) {
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}

여기까진 그 전 내용들 확인하면 내용을 설명해 놓음
재귀함수로 해결하면 시간 복잡도가
O(n^2)...너무 오래걸린다.

콘솔창에 n=100 넣고 해봐라
../ 글을 쓰고 있는 이 순간에도 계산중이다.

크롬 V8엔진 화이팅이다.

다이내믹 프로그래밍

하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 뜻함

Memoization의 정의는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

재귀 함수에 적용가능하다.

생각하자
패턴을 하나 외우자

1.결과를 저장할 빈 배열을 선언한다.
=> 이미 결과값을 아는건 저장을 해둔다.
=> 그럼 필요할때 그걸 꺼내본다.

2.재귀 함수와 동일하게 작성
=> 최소의 경우를 설정하고
=> 계속해서 최소의 경우을 향해 간다.

3.중요한 패턴

if (memo[n] !== undefined) return memo[n];

값이 있다면.. 그 값을 리턴하자 !!
이 생각을 해내면 나머진 쓱쓱 풀린다.

Top-down 방식

function fibonacci(n, memo = []) {
  // TODO: 여기에 코드를 작성합니다.
  if(memo[n] !== undefined) return memo[n];
  if(n === 0) return 0;
  if(n <= 2) return 1;
  let result = fibonacci(n-1, memo) + fibonacci(n-2, memo);
  memo[n] = result;
  return result;

}

다른풀이

내장함수를 선언해서 만들어보기

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

Bottom-up 방식

위에 방식을 작성하다보니...............
n=100이면
100 -> 99 -> 98 -> 97 ...
이런식으로 top-down 식으로 계산을 하게 되는데

미리 계산하지도 않은 100을 어떻게 빨리 알아낸다는것인가?????????????????????????????????????

바닥에서 위로 올라가는 방법은
반복문을 사용한다.

 function fibTab(n) {
    if(n <= 2) return 1;
    let fibNum = [0, 1, 1];
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
    }
    return fibNum[n];
}

두 방식을 비교해서 속도를 구하면
첫번째 (Bottom-Up 방식) 결과 : 0.30000007152557373ms

var t0 = performance.now();
fibTab(50); 
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')
VM103:4 runtime: 0.30000007152557373ms

두번째 (Top-Down 방식) 결과 : 0.20000004768371582ms

 var t0 = performance.now();
fibonacci(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')
VM125:4 runtime: 0.20000004768371582ms

top-down 방식이 휠씬 빠르다 !!

(한국 회사들의 결정 방식인데...짜증)

피보나치 끝판왕

피보나치 수열을 순차적으로 출력하는 클로저 형태의 함수를 작성해야 합니다

주의사항
호출될 때마다 다음 피보나치 수를 리턴하는 함수를 리턴해야 합니다.
피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 됩니다.
예시) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 리턴되는 클로저 내부 함수(inner function)의 구현은 recursive 혹은 iterative한 방법 중 어떤 것이어도 괜찮습니다.

생각하자

문제의 요구사항

특 1 : 피보나치를 리턴하는 함수를 출력하자
특 2 : 클로져 형태의 함수를 만들어야 함

정답코드

function fibo() {
  // TODO: 여기에 코드를 작성하세요.
  // 함수를 실행하면 카운터를 올려준다. 
  // 피보나치 수열을 실행시키는 함수를 만든다. 
  let count = 0; 
  
  // 피보나치 만드는 함수를 만든다.
  const fibonaci = (n) => {
    if(n < 2){
      return n;
    } else {
      return fibonaci(n - 2) + fibonaci(n - 1);
    }
  } 
  // 함수를 호출 해야하니 익명함수만듬 
  // 함수가 호출되면 카운터는 하나씩 올라가고 
  // 피보나치 내부함수(클로저 함수에 전달된다.)
  // 전달인자는 카운터 보다 하나씩 작게해서 전달
  // 피보나치는 0 / 1 / 1 / 2 / 3 / 5 / 8 / 13
  return function(){
    count++
    return fibonaci(count-1)
  }
}