동적 계획법(DP)의 핵심 유형 정리: 배낭 문제부터 트리 DP까지

1. 01 배낭 문제 (01 Knapsack Problem) 01 배낭 문제는 DP의 가장 기초적인 형태 중 하나입니다. 주어진 물건들이 각각 무게와 가치를 가지고 있을 때, 배낭의 용량을 초과하지 않으면서 가치의 합을 최대화하는 것이 목표입니다. 각 물건은 단 하나씩만 존재하므로 '선택한다(1)' 또는 '선택하지 않는다(0)'의 두 가지 상태만 가집니다. 일반적으로 2차원 배열로 표현할 ...

10월 26일 13:36에 게시됨