우선순위 큐

문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 2170: 선 긋기 문제 풀이 정렬, 스위핑 문제이다. 현재 긋고 있는 선의 시작을 start, 끝을 end라고 하자. 선을 긋고 있을 때, 어떤 상황에서 다음 선을 한번에 그을 수 있을까? 만약 다음으로 그을 선의 시작이 end kantatatam.tistory.com 위의 문제가 생각나는 문제이다. A강의와 B강의가 서로 같은 강의실을 사용하려면 A강의가 B강의의 시작하는 시간보다 빨리 끝나야 한다. 오름차순 우선순위 큐를 만든다. priority_queue..

문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 그리디, 자료 구조, 우선순위 큐 2가지 방법으로 문제를 풀 수 있다. 1. 가방을 오름차순으로 정렬하고, 현재 가방에 넣을 수 있는 가격이 최대인 보석을 찾는 방법 보석과 가방을 오름차순으로 정렬한다. 용량이 적은 가방부터 현재 가방에 들어갈 수 있는 보석을 모두 우선순위 큐에 넣는다. 그렇게 되면, 우선순위 큐의 top에는 현재 가방에 들어갈 수 있으면서 가격이 최대인 보석이 위치하게 된..

문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 그리디, 우선순위 큐 카드 수가 가장 적은 2개의 묶음을 합치는 방식으로 해결할 수 있다. 이 때, 2개의 묶음을 선택하기 위해, 우선순위 큐를 사용한다. 카드 수가 가장 적은 2개의 묶음을 합친다. 합쳐진 묶음을 다시 우선순위 큐에 넣는다. 모든 카드 묶음이 합쳐질 때까지 반복 코드 #include #include using namespace std; // 오름차순 우선순위 큐 priority_queue pq; int main() { ..

문제 1854번: K번째 최단경로 찾기 첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이 www.acmicpc.net 풀이 다익스트라, 우선순위 큐 문제이다. 처음에는 특정 노드에 도착할 때마다 벡터에 현재 비용을 추가하는 방식으로 접근했다. 하지만 이렇게 하면, 특정 노드에는 k번 도달하지 않고 다익스트라가 종료될 수 있다. 그렇다고, 노드에 도착할 때마다 다익스트라를 돌리는 우선순위 큐에 값을 추가하면 다익스트라가 끝나지 않는다. 다익스트라에 추가적으로 우선순위 큐(내림차순)를 추가하여 풀 ..