문제 링크 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 요새 취업 시장에서 그리디 문제가 많이 나온다기에 열심히 관련 문제들을 풀고 있습니다! 👨💻 그리디 문제들을 풀다 보면 정렬을 사용하는 그리디와 정렬을 사용하지 않는 그리디가 있고, 여러 자료 구조 중 하나를 선택하여 푸는 그리디가 있는데, 그 중 대표적인 것이 우선순위 큐였습니다. 우선순위 큐를 이용하는 그리디 문제 중에 좋은 문제가 있어서, 하나 포스팅을 해보려고 합니다. 😊 풀이 정렬과 우선순위..
우선순위큐
문제 링크 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 요즘 위상정렬에 관한 문제들을 풀고 있는데, 간단한 문제 하나를 소개해드리려고 합니다. 풀이 위상정렬 + 우선순위큐(최소힙)로 풀이하면 됩니다. 일반적인 위상정렬(`indegree` 배열 활용)을 만듭니다. 보통 위상정렬은 `queue` 를 사용하지만, 이 문제에서는 최소 힙 우선순위큐를 사용합니다. 문제에서 주어진대로, "가능하면 쉬운 문제(1번부터)"와 "먼저 푸는 것이 좋은 문제"를 풀어야하기 때문에 최소 힙을 사용..
