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

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

10월 26일 13:36에 게시됨

트리 DP와 비트마스크 DP 문제 풀이

P1352 상사 없는 파티 트리에서 인접한 노드를 동시에 선택할 수 없는 상황에서 최대 가중치 합을 구하는 문제입니다. 상태 정의: val[node][0/1] - 현재 노드를 포함하지 않는 경우(0) 또는 포함하는 경우(1)의 하위 트리 최대값 점화식: val[node][1] = weight[node] + Σ val[child][0] (현재 노드를 선택하면 자식들은 선택 불가) val[node][0] = Σ max(val[child][0], ...

7월 3일 21:12에 게시됨