위상 정렬이란?위상 정렬은 그래프 알고리즘 중 DAG(Directed Acyclic Graph), 즉 방향성이 있으면서 싸이클이 없는 그래프에서 정점들을 순서대로 정렬하는 방법이다. 위상 정렬은 다음과 같은 상황에서 유용하다.- 작업 스케쥴링- 선수 과목에 대한 문제- 데이터 처리 파이프라인 위상 정렬의 조건위상 정렬을 사용하기 위해선 위에서 언급한 것처럼1. edge(간선) 에 방향이 있어야 한다.2. 비순환 그래프 즉, 싸이클이 없어야 한다. 이 두가지 조건을 만족해야 한다. 위상 정렬은 큐 기반 위상 정렬과 dfs 기반 위상 정렬로 나뉜다.두 방식에 대해 각각 알아보자.큐 기반 위상정렬큐 기반 위상정렬은 다음과 같은 단계를 따른다.1.각 정점의 진입 차수(inDegree)를 계산한다.2.진입 차수..
