위상정렬 검색 결과
1 개의 검색 결과가 있습니다.
알고리즘

위상정렬 Topological Sort 개념 + 시간복잡도

Topological sort 위상정렬 알고리즘에 대해서 살펴보고 시간복잡도를 분석해보도록 하자. 위상정렬 알고리즘이란 순서가 있는 알고리즘인데 쉽게 말해서, 만약 i와 j 사이에 간선이 있다면 i가 j보다 정렬 순서에서 먼저 와야 한다는 뜻이다. 일상 생활에서도 위상정렬이 필요한 경우를 쉽게 생각해볼 수 있다. 예를 들어, 일상생활에서 다음과 같이 5개 행동을 한다고 생각해보자. [물 끓이기, 요리하기, 음식먹기, TV 켜기, TV 보기] 그럴 때 물을 먼저 끓여야 요리를 할 수 있고 그래야 음식을 먹을 수 있다. 하지만 음식을 먹으면서 동시에 TV를 켜는 것은 가능하기 때문에 요리와 TV 사이의 순서는 정해져 있는 것이 없다. 하지만 TV를 켠 다음에야 TV를 볼 수 있으므로 아래와 같이 그래프가 만..

2021. 5. 9. 21:32