DATA101

문제 원본 링크: https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근법 본 문제의 목표는 가격이 높은 보석을 최대한 많이 담되 용량이 적은 가방부터 차례대로 담는 것입니다. 이때 가방의 용량에 따른 탐색 순서를 고려하지 않으면 문제를 제대로 풀 수 없습니다. 예를 들어, 다음과 같이 (무게, 가치) 정보가 담긴 3개의 보석과 가방 2개가 있다고 가정해 보겠습니다. 여기서 가방의 용량..

📚 목차 1. 우선순위 큐(Priority Queue)란? 2. 힙(Heap) 자료구조 2.1. 힙 자료구조란? 2.2. 우선순위 큐 구현 방식: 리스트 vs 힙 3. 힙 기반의 우선순위 큐 구현(Python) 3.1. heapq 라이브러리 소개 3.1.1. 힙 원소 추가(heappush) 3.1.2. 힙 원소 삭제(heappop) 3.1.3. 리스트를 힙으로 변경(heapify) 3.2. 힙 기반의 우선순위 큐 구현 예시 1. 우선순위 큐(Priority Queue)란? 우선순위 큐는 말 그대로 우선순위가 가장 높은 데이터를 가장 먼저 추출하는 자료구조입니다. 일반적으로 큐(Queue) 자료구조는 선입선출 방식으로서 가장 먼저 삽입된 데이터를 가장 먼저 추출합니다. 간단하게 특징이 유사한 자료구조들의 ..