문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 한 문제, 한 문제씩 풀어나가는 것을 그래프에 대입하여 노드를 탐색하는 과정으로 생각해봅시다. 조건에 의해 모든 노드를 탐색해야 하고, 먼저 푸는것이 좋은 문제를 반드시 먼저 풀어야 하므로 선행 노드를 반드시 탐색해야 합니다. 따라서 위상정렬로 문제를 해결해야 합니다. 그런데 쉬운 문제(번호가 낮은 노드)부터 해결해야 하므로 현재 풀 수 있는 문제(inde..
우선순위 큐
문제 1655번: 가운데를 말해요 (acmicpc.net) 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 간단하게 문제를 푼다면 입력을 받을 때마다 배열을 정렬하고 그 중앙값을 출력하여 해결할 수 있습니다. 하지만 입력을 받을 때마다 정렬을 하게 되고 0.1초의 시간제한 안에 해결할 수 없습니다. 그래서 필요한 방법은 최소 힙, 최대 힙 두 개를 활용하여 관리하는 것입니다. 중앙값을 기준으로 작은 값들은 최대 힙에, 큰 값들은 최소 힙에 넣습니다. 이때 중앙값이 정말 중앙값이기 위해선 ..
