비율을 이용한 분할 배낭
무게당 가치가 가장 높은 항목부터 선택합니다
비율을 이용한 분할 배낭은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
배낭 문제 설정
각 물건에 값과 무게가 있고, 용량이 제한된 가방이 있습니다. 목표는 가능한 한 큰 총가치를 담는 것입니다. 🎒
분할 가능하다는 뜻
분할 가능한 버전에서는 곡물 자루의 절반처럼 물건의 일부만 가져갈 수 있습니다. 이 자유가 바로 이 문제에서 탐욕 알고리즘이 성공하는 이유입니다.
무게당 가치
핵심 지표는 각 물건의 가치와 무게의 비율입니다. 비율이 높다는 것은 아주 적은 공간에 많은 가치가 들어 있다는 뜻입니다.
ratio = value / weight최고 비율로 sort하기
물건을 무게당 가치가 높은 순서로 sort하십시오. 탐욕적 계획은 현재 가능한 물건 중 가치 밀도가 가장 높은 것을 계속 선택하는 것입니다.
items.sort(key=lambda i: i[0] / i[1], reverse=True)들어가는 동안에는 통째로 담기
정렬된 리스트를 훑으면서 남은 용량에 들어가는 각 물건을 전부 담으십시오. 총합에 물건의 전체 가치를 더하십시오.
if weight <= cap:
total += value
cap -= weight마지막 빈 공간 채우기
물건이 너무 크면 남은 공간을 정확히 채우는 일부만 가져가십시오. 그러면 가방이 가득 차고 작업을 멈추면 됩니다.
total += value * (cap / weight)비율 순서가 작동하는 이유
용량의 각 단위에는 가능한 한 큰 가치를 담아야 하므로 밀도가 가장 높은 물건을 먼저 넣어야 합니다. 밀도가 낮은 물건으로 바꾸면 가치가 줄어들 뿐입니다.
0/1 배낭은 다릅니다
항목을 나눌 수 없다면 비율을 기준으로 한 그리디 방식은 무너집니다. 0/1 버전에는 이 간단한 정렬이 아니라 동적 계획법이 필요합니다.
실행 시간
비율에 따른 정렬에는 O(n log n) 시간이 들고, 채우기 반복문은 선형 시간에 실행됩니다. 일반적인 대회 제한에서는 충분히 빠릅니다.
마지막 분수를 주의하세요
일부 항목을 담을 때는 부동소수점이나 정확한 유리수를 사용하세요. 너무 일찍 버림하면 가치를 잃어 오답이 될 수 있습니다.
어디에 활용되나요
화물 적재, 연료 혼합, 자원 분할을 생각해 보세요. 조각으로 나눌 수 있는 대상이라면 비율 그리디 방식이 도구가 됩니다.
빠른 확인
분할 가능 배낭 문제에서 배낭을 채우고 있습니다.
복습
무게당 가치를 기준으로 항목을 정렬하고, 들어가는 동안에는 항목 전체를 담은 다음 배낭을 가득 채우기 위해 일부를 담으세요. 이 그리디 방식은 항목을 나눌 수 있을 때만 최적입니다. 🚀
자주 묻는 질문
“비율을 이용한 분할 배낭” 강의는 무료인가요?
네 — “비율을 이용한 분할 배낭” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“비율을 이용한 분할 배낭”에서 뭘 배우나요?
무게당 가치가 가장 높은 항목부터 선택합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“비율을 이용한 분할 배낭” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 탐욕적 사고방식
- 가장 이른 종료 시간으로 활동 선택하기
- 비율을 이용한 분할 배낭
- 탐욕법이 실패하는 순간 포착하기