다이나믹 프로그래밍 기초: 배낭 문제의 핵심 전략
배낭 문제의 기본 구조와 최적화 원리
다이나믹 프로그래밍에서 배낭 문제는 상태 전이를 이해하는 데 중요한 예시입니다. 주요 유형은 0/1 배낭, 무한 배낭, 다중 배낭, 분할 배낭 등으로 나뉩니다. 각각의 차이는 선택 가능한 횟수와 제약 조건에 따라 달라집니다.
기본적인 상태 정의
dp[i][j]는 처음 i개의 아이템 중에서 총 용량이 j 이하인 조건에서 얻을 수 있는 ...
7월 25일 19:32에 게시됨
COTS 2025 문제 풀이 및 코드 모음
개요
COTS 2025 대회에서 출제된 6개 문제(A~F)의 풀이와 구현 코드를 정리합니다. 각 문제는 서로 다른 알고리즘 기법을 요구하며, 복잡도와 구현 세부사항에 중점을 둡니다.
[COTS 2025] A - 상 배분 / Hijerarhija
트리 DP와 배낭 문제를 결합한 문제입니다. 각 노드에서 자식 노드들의 상태를 합치며 최적해를 구합니다.
const int MAXN = 5e3 + 5;
const int INF = 1 ...
5월 22일 14:15에 게시됨