Dynamic Programing이란? 동적 프로그래밍은 딱히 프로그래밍 방법론은 아니다. 이름이 '프로그래밍'이라서 헷갈리는데, 그냥 알고리즘 방식의 하나라고 생각하면 된다. 동적 프로그래밍 방법에서는 입력 크기가 작은 문제들을 먼저 해결해서 그 결과값(해)들을 저장해두고 (=memorization) 이것을 이용해 크기가 큰 문제들을 해결한다. 작은 문제의 결과들을 저장해두었기 때문에 큰 문제의 결과를 구할 때 다시 계산할 필요가 없어 속도가 빠르다. 분할 정복 알고리즘과의 차이 동적 프로그래밍은 분할 정복(Divide and Conquer) 알고리즘과 비슷한데 분할 정복이 하향식(top-down) 접근을 하는 것이라면 동적 프로그래밍은 상향식(bottom-up) 접근을 한다. 무슨말이냐면 분할 정복 ..