공부하는 블로그

위상 정렬(Topological Sort) ? 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것이다. 위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조이다. 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프는 여러 위상 정렬이 가능하다. 위상 정렬 구현(in JAVA) import java.util.ArrayDeque; import java.util.ArrayList; public clas..

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 우선순위가 정해진 문제를 푸는 순서를 찾아내는 문제이다. 문제를 푸는 순서에 대한 조건은 두 가지가 있다. 1. 순서가 정해진 문제는 순서에 맞춰 풀어야 한다. ---- 위상정렬 2. 가능한 쉬운 문제(문제 번호가 낮은 문제) 먼저 풀어야 한다. ---- 우선순위 큐 import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public ..