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

-다이나믹 프로그래밍이란? 솔직히 여러 블로그나 강의를 봤을 때 드는 예시가 대표적으로 피보나치 수열이라 개념의 이해자체는 쉬웠다. 분할 정복 방식과는 다른 형태로 어떤 큰 문제가 작은 문제로 나눠질 때 또 이 큰 문제가 더 큰 문제의 작은 문제일 때, 동시에 해당 값들에 변화가 없을 때 사용한다고 한다. 즉 피보나치 수열에서 f(3) = f(2) + f(1) 이고, f(4) = f(3) + f(2)이므로 f(3)에서의 f(2)와 f(4)에서의 f(2)는 값이 변하지 않는 중복되는 연산이다. 이러한 중복 연산들을 메모이제이션 기법으로 별도로 기록해두고 (캐시같은 개념) 필요할 때 마다 가져다 사용하면 되는 것이다. 즉, f(3)의 결과를 최초로 실행할 때 저장해 둔 후, f(4)를 구할 때 f(3)을 구..