하수하따 록기장

📍문제 링크https://www.acmicpc.net/problem/1202 📍알고리즘 분류그리디, 우선순위 큐 📍 풀이 방법최대한 많은 보석을 훔치기 위해서는 최대한 비싼 보석을, 많이 담아야 한다.따라서 비싼 보석부터 담아야 하는데, 최대로 용량을 채울 수 있는 가방에 넣어야 한다.반복문을 통해 가방을 하나씩 그리디하게 보면서 넣을 보석을 정해준다.우선순위 큐를 이용해서 하나의 가방 안에 들어갈 수 있는 무게의 보석들 중 가격이 가장 비싼 것을 담으면 된다. 어떤 가방부터 보아야할까?용량이 큰 가방부터 본다면, 비싼데 크기가 작은 보석이 용량이 큰 가방에 담길 것이다. 더 보석을 가져갈 수 있을텐데 용량이 낭비될 것이다.따라서 용량이 작은 가방부터 탐색한다. 작은 가방에 담기는 무게 중에서 비싼..

더보기목차1. Greedy 알고리즘이란2. MST란3. Kruskal 알고리즘- 이론, 구현4. Prim 알고리즘- 이론, 구현1. Greedy 알고리즘이란Greedy 알고리즘이란 욕심장이 기법으로 당장 이 순간에서 최적이 되는 해를 구하는 것에, 즉 현재에 집중하는 알고리즘입니다. 과거와 미래는 전혀 신경쓰지 않습니다. Greedy 알고리즘의 핵심 단계는 다음과 같습니다.  1) Selection Procedure (선택)현재를 기준으로 가장 최적이 되는 해를 선택하는 단계입니다. 최적 해를 선택하여 집합에 추가합니다. 이 과정을 위해 선행되는 핵심은 어떤 값을 먼저 볼 것인지에 대한 우선순위 결정입니다. 2) Feasibility Check (유효성 검사)앞에서 선택한 해를 포함한 집합이 문제를 해결..