mondegreen

위상정렬의 개념 위상정렬이란 순서가 있는(즉, 방향이 있는) 작업을 차례로 진행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프(Directed Acyclic Graph)의 모든 노드를 주어진 "선행순서를 위반하지 않으면서" 나열하는 것이다. 예시: 대학교 선수과목, 공장의 작업 순서, 요리 순서... 특정 정점을 진행하기 위해 거쳐야 하는 정점의 수(간선으로 연결된)를 진입차수라 하고 특정 정점에서 넘어가야 할 다음 정점의 수를 진출차수라고 한다. 그 중 선행 조건이 되는 진입차수가 중요하다. 위상정렬의 특징 1) 하나의 방향그래프에서는 여러 위상 정렬이 가능하다. 2) 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라 한다. 3) 위상 정렬의 과정에서 그래프..