[JS] 다이나믹 프로그래밍

1. 다이나믹 프로그래밍 다이나믹 프로그래밍이란, 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. 이전에 나는 퀵 정렬, 병합 정렬, 이진검색과 같은 자료구조를 포스팅한 적이 있다. 이 셋을 언급한 이유는 분할 기법을 이용하기 때문이다. 퀵 정렬, 병합 정렬, 이진검색은 분할 기법을 이용해서 평균 시간복잡도 O(Nlog₂N)이라는 굉장히 빠른 속도를 장점으로 가질 수 있었다. 하지만 되게 빨라보이는 분할기법도 어떤 상황에서는 단점이 존재하는데, 그것은 바로 동일한 문제를 반복해서 푼다는 것이다. 그 대표적인 예시가 피보나치 수열이다. 피보나치 수열은 제 0항, 제 1항을 1로 제쳐두고 두 번째 항부터는 앞에 두 수를 더한 값을 결과로 두는 수열을 말한다. 피보나치 수열은 보통 프로그래밍 언어에서 재귀..

2020.06.29