개요동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 중복된 하위 문제로 나누고, 이들을 한 번만 계산하여 결과를 저장해 재사용함으로써 전체 문제를 효율적으로 해결하는 알고리즘 설계 전략이다. 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack), 경로 탐색 등 다양한 최적화 문제에 활용되며, **탑다운(메모이제이션)**과 바텀업(테이블화) 방식이 있다.1. 핵심 개념 및 정의동적 계획법의 핵심은 다음 두 가지 조건을 만족하는 문제에서 적용 가능하다:중복 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 반복적으로 등장함최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 하위 문제의 최적해로 구..
