위상정렬
-
위상정렬(Topological Sorting)알고리즘/알고리즘 공부 정리 2021. 12. 14. 23:46
이번 시간에는 위상 정렬에 대한 개념과 동작 과정을 알아본다. 이후 위상 정렬을 Python으로 구현해 본다. 1. 위상 정렬(Topological Sorting) 💡 정렬 알고리즘의 일종으로, 순서가 정해진 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. ⇒ 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 1-1. 예시 - 선수과목을 고려한 학습 순서 설정 그림과 같이 총 3개의 과목이 있다고 가정하자. 세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 순서로 과목을 들어야 한다. 만약 알고리즘 -> 자료구조 -> 고급 알고리즘 (X) 순서로 과목을 듣는다고 가정하자. 해당 순서는 올바른 학습 순서가 아니다..