개발새발 로그

위상정렬 순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정하기 위해 사용하는 알고리즘 위상정렬을 통해 여러개의 순서를 조건에 부합하는 일직선의 순서로 만든다. 배고픔 -> 돈벌기-> 배달 앱 설치하기 -> 배달시킬 음식 고르기 -> 주문서 작성하기 -> 결제하기 -> 배달 완료 위상정렬은 다른 수서의 답 또한 존재할 수 있다. 위상정렬은 사이클이 존재하지않는 그래프(DAG)에만 적용가능하다. 위상정렬은 현재 그래프가 위상정렬이 가능한지 판별가능 위상정렬이 가능하다면 그 결과는 무엇인지 와 같은 두가지의 해결책을 낸다. 위상정렬은 스택과 큐를 이용한 두가지의 방식이 존재한다. 큐를 이용한 방식 1. 진입차수가 0인 정점을 큐에 삽입한다. -> 특정한 노드로 들어오는 노드의 개수 = 진입 차수 ..