python dp (1) 썸네일형 리스트형 동적계획법(Dynamic Programming) Python 동적 계획법 (Dynamic Programming) 하나의 큰 문제를 중복(반복)된 하위 문제들로 분해하여 계산한다. 하위 문제들의 계산 결과를 저장 후, 상위 문제의 계산에 재사용한다. 하위 문제들의 결과를 저장하는 테이블을 사용하며 메모리 사용량이 증가할 수 있다. Memoization 기법을 사용한다. 반복문이나 재귀를 통해 구현할 수 있다. 배낭 문제 (Knapsack Problem) 동적 계획법 알고리즘의 이해를 돕는 기본 문제. 물건을 W 무게까지 담을 수 있는 배낭이 있고, N개 종류의 물건들이 각각 무게(g)와 가치(v)를 가지고 있다. W 무게를 넘지 않으며 '최대 가치'가 될 수 있도록 물건을 배낭에 담는 .. 이전 1 다음