04 - nthFibonacci

문제설명

n번째 피보나치의 수를 구하는 문제이다. (0, 1, 1, 2, 3...)

입출력 예)

nthFibonacci(2); // => 1
nthFibonacci(3); // => 2
nthFibonacci(4); // => 3

문제접근

문제 조건중 하나는 리커젼으로 먼저 풀이한 후에 반복문으로도 다시 풀라는 조건이있다.

해결방안

recursion 방식

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

일반 반복문

function fibo(n){
  var pre = 0;
  var cur = 1;
  var last = 0;
  for(let i = 0; i<n; i++){
    last = pre+cur;
    pre = cur;
    cur = last;
  }
  return last;
}

메모이제이션

function fibo(){
    let fib0 = 0;
    let fib1 = 0;
    
    return function(){
    	if(fib1 === 0){
            fib1 = 1;
            return 0;
        }
        let prefib0 = fib0;
        let prefib1 = fib1;
        
        fib0 = prefib1;
        fib1 = prefib0 + prefib1;
        
        return fib0;
     }
}
let fib = fibo();

관련내용

회고

수 관련 개념이 나오면 알고리즘 문제를 풀어내기에 어려움을 겪는다.
그래서 조금이라도 수학적지식만을 습득하는 시간을 따로 갖기로 했다.