피보나치 알고리즘 정리

- 잘못된 예시

function wrongFib (n){
  if(n <=2){
    return 1;
  } 

  return fib(n-1) + fib(n-2)
}

피보나치를 구현할때, 이런식으로 코드를 작성하면 DP 방식이 아닌 그저 재귀함수에 해당해서 시간복잡도가 상당히 높아진다.

이럴때 DP의 memoization 을 도입해서, 값을 재사용함으로써 시간복잡도를 줄일 수 있다.

- 예시

function fib (n, memo =[]){
  if(memo[n] !==undefined){
    return memo[n];
  }

  if(n <= 2){
    return 1;
  }

  let res = fib(n-1, memo) + fib(n-2, memo);

  memo[n] = res;

  return res;
}

memo 배열을 사용함으로써 memo 배열안에 호출한 n값 이전의 수열 값들이 저장 되어 있다.