피보나치, 동적프로그래밍에 관하여

Fibonacci and Dynamic Programming(Memoization)

알고리즘 문제를 풀어나가다가 난관에 부딪혔다. 지금까지는 계속 쉬운 알고리즘을 하다가 문제를 해결하기위해서 슬슬 기본적으로 알아야할 것들이 생긴것이다. 오늘은 간략하게, 피보나치의 수열과 동적프로그래밍에 관하여 작성해보겠다!

재귀 함수를 사용하면 시간복잡도는 2의 n승이 된다. 최악의 시간복잡도인데 이것을 동적 프로그래밍으로 바꿔본다면 다음과같다.

cache라는 객체안에 fib(n)값들을 저장해서 실행루트를 최소화 시키는 방법(memoization)이다 만약 함수안에 console.log(cache) 를 작성하면cache에 저장되는 값들을 볼수있을것이다. 다음과같다.

{
  '2': 1,
  '3': 2,
  '4': 3,
  '5': 5,
  '6': 8,
  '7': 13,
  '8': 21,
  '9': 34,
  '10': 55
}