
위상정렬위상 정렬이란 방향그래프(Directed Graph)에서 순서가 정해져 있는 작업을 수행할 경우, 순서를 결정하기 위해 사용하는 정렬 알고리즘입니다. O(V+E)의 시간복잡도를 가집니다. 우리가 등교를 위해 옷을 입는 과정을 생각해 봅시다. 셔츠를 먼저 입을 수도, 양말을 먼저 신을 수도, 속옷을 먼저 입을 수도 있지만,신발을 신고 양말을 신거나 바지를 입고 속옷을 입을 수는 없습니다. 이처럼 순서가 정해져 있는 작업을 수행할 경우 올바른 순서를 도출해 내기 위해 위상정렬을 사용합니다. 위상정렬을 사용하기 위한 조건- 그래프가 비순환 방향 그래프(DAG: Directed Acyclic Graph)여야 합니다. DAG는 모든 노드에 대해 어떤 노드로부터 다른 노드로의 경로가 유일하며, 다시 출발점..