토이 2번

야 나 개 ·2021년 11월 10일

주간 문제아이돌

목록 보기

7/17

2번 문제

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

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

주의사항
재귀함수를 이용해 구현해야 합니다.
반복문(for, while) 사용은 금지됩니다.
함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

반복문 코드

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