위상 정렬 파이썬1 [Algorithm] 위상 정렬 (Topology Sort) 위상 정렬이란? 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 즉, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 위상 정렬의 예시로는 '선수과목을 고려한 학습 순서 결정'이 있다. 어떤 학부의 커리큘럼 상 'A' 과목을 들어야 'B' 과목을 들을 수 있고 'B' 과목을 들어야 'C' 과목을 들을 수 있다고 가정해보자. 이 경우, 'A' -> 'B' -> 'C'와 같이 표현할 수 있다. 즉, 'C' 과목을 수강하기 위해서는 'A' 과목을 먼저 수강하고 다음으로 'B' 과목을 수강해야 하는 것이다. 위상 정렬을 하기 위한 조건은 다음과 같다. 간선이 방향성을 가진 그래프여야 한다. 그래프 내부에 순환(Cycle)이 .. 2022. 4. 11. 이전 1 다음
