목록topological sort (1)
Hippo's data
위상 정렬(Topological Sort)
오늘은 위상정렬(Topological Sort)에 대해 알아보겠습니다! 위상정렬은 방향그래프, 사이클이 없는 그래프(DAG, Directed Acyclic Graph) 에서 노드의 순서를 정하는 알고리즘입니다!(사이클이 있다면 시작점을 정할 수 없으므로 순서를 파악할 수 없음) 일반화 한다면, 순서가 정해져 있는 작업에서 조건에 맞게 순서를 결정해주는 것을 말합니다!대표적인 예시로 선수과목 순서에 따라 수강과목을 정하기, 작업 스케줄링에 따라 작업순서 선정 등이 있습니다특히 결과로 여러 답이 존재합니다! (유니크한 결과 X) # 동작과정 위상정렬은 2가지 방식으로 구현가능한데욥1) 스택(stack)이용 - DFS2) 큐(queue)이용 - BFS일반적으로 큐를 이용한 방식이 주로 사용되므로 해당 방식을 ..
Algorithm/알고리즘 이론(Algorithm theory)
2024. 11. 27. 01:35