다이나믹 프로그래밍(DP)은 다음 두 가지 특성을 만족하는 문제에 적용할 수 있습니다: 1. 중복되는 하위 문제 (Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 하위 문제가 여러 번 등장합니다. 2. 최적 부분 구조 (Optimal Substructure): 문제의 최적 해결 방법이 하위 문제의 최적 해결 방법으로부터 구성될 수 있습니다. DP는 이러한 특성을 이용하여 하위 문제의 결과를 저장하고, 이를 재사용함으로써 전체 문제를 효율적으로 해결합니다. DP의 접근 방식 • 메모이제이션 (Memoization): 재귀적으로 문제를 해결하면서, 이미 계산된 결과를 저장하여 다시 계산하지 않도록 하는 방법입니다. • 타뷸레이션 (Tabulation): 작은 하위 문제부터 ..