0/1 배낭: 선택하거나 포기하기
무게 한도 안에서 가치를 최대로 만듭니다
0/1 배낭: 선택하거나 포기하기은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
배낭 문제 이야기
무게 제한이 있는 가방과 여러 물건이 있습니다. 0/1 배낭 문제는 가방을 넘치게 하지 않으면서 어떤 물건들을 골라 가치를 최대로 만들지 묻습니다. 🎒
선택하거나 포기하기
0/1은 각 물건을 전부 선택하거나 전부 건너뛴다는 뜻입니다. 물건의 일부만 가져갈 수 없으므로 모든 선택은 예 또는 아니오입니다.
탐욕법이 실패하는 이유
가장 저렴하거나 가치가 높은 물건부터 고르면 용량을 낭비할 수 있습니다. 여기서는 탐욕법이라는 지름길이 통하지 않으므로 실제 조합을 고려해야 합니다.
두 입력
각 물건에 대한 무게와 값이 나란히 담긴 두 목록, 그리고 하나의 용량이 주어집니다. 물건 i의 무게는 wt[i], 값은 val[i]입니다.
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7상태 정의
dp[i][w]를 처음 i개 물건만 사용하고 용량이 w일 때 얻을 수 있는 최선의 값이라고 합시다. 상태를 정확히 이름 붙이는 것이 문제 해결의 핵심입니다.
건너뛰기 선택
물건 i를 건너뛰면 값은 지금까지 얻은 값인 dp[i-1][w]와 같습니다. 이후에도 용량은 그대로 남습니다.
선택하기
물건 i를 선택하면 그 값을 더하고 용량을 줄입니다: val[i] + dp[i-1][w - wt[i]]. 단, w가 wt[i] 이상일 때만 가능합니다.
더 나은 분기 선택
점화식에서는 간단히 max를 사용해 두 선택지 중 더 큰 값을 남깁니다. 각 칸은 이미 아래에서 계산된 정답을 활용합니다.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])기저 행
물건이 0개라면 어떤 용량에서도 담을 수 있는 값은 0입니다. 이 기저 사례가 첫 번째 행을 모두 0으로 채워 다음 계산의 바탕이 됩니다.
dp = [[0] * (cap + 1) for _ in range(n + 1)]표 채우기
바깥쪽 반복문에서 물건을 순회하고 안쪽 반복문에서 용량을 순회합니다. 각 칸은 바로 위 행만 읽으므로 한 번 훑으면 모든 칸을 채울 수 있습니다.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]정답 읽기
오른쪽 아래 칸인 dp[n][cap]에 모든 물건과 전체 용량을 고려한 최댓값이 저장됩니다. 이 한 칸이 최종 정답입니다.
빠른 확인
0/1 배낭 문제의 핵심 점화식을 확인해 보세요.
복습
0/1 배낭 문제를 배웠습니다. 각 물건은 선택하거나 포기하고, dp[i][w]에는 건너뛰기와 선택하기 중 더 나은 값이 저장되며, dp[n][cap]이 정답입니다. 🎉
자주 묻는 질문
“0/1 배낭: 선택하거나 포기하기” 강의는 무료인가요?
네 — “0/1 배낭: 선택하거나 포기하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“0/1 배낭: 선택하거나 포기하기”에서 뭘 배우나요?
무게 한도 안에서 가치를 최대로 만듭니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“0/1 배낭: 선택하거나 포기하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 0/1 배낭: 선택하거나 포기하기
- 공간을 최적화한 배낭
- 무제한 배낭과 동전 교환 DP
- 부분집합 합과 분할