동적 프로그래밍(Dynamic Programming)이란? 동적 프로그래밍은 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 디자인 기법 중 하나입니다. 분할 정복(Divide and Conquer)과 유사하며, 분할 정복과의 차이점은 동적 프로그래밍은 중복되는 부분 문제가 발생할 때, 그것을 한 번만 계산하고 그 결과를 메모이제이션(Memoization)하여 다른 비슷한 부분 문제들이 다시 발생할 때, 메모이제이션된 결과를 가져와 재활용한다는 것입니다. 동적 프로그래밍을 적용하기 위해서는 다음의 두 가지 조건을 만족해야 합니다. 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제의 최적해로부터 구해질 수 있어야 합니다. 중복되는 부분 문제(Overlappin..