Devlog

3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬로 풀기 5 5 4 3 2 1 2 2 4 3 4 처음 순위 [5,4,3,2,1]대로 단방향 그래프를 생성합니다. 5는 (4,3,2,1)보다 높으므로 5->4, 5->3, 5->2, 5->1 간선을 추가합니다. 4는 (3,2,1)보다 높으므로 4->3, 4->2, 4->1을 추가합니다. 3,2,1도 같은 방식으로 간선을 추가하면 5 -> [4,3,2,1] 4 -> [3,2,1] 3 -> [2.1] 2 -> [1] 1 -> [] 여기서 (2, 4)와 ..

개요 위상 정렬은 DAG에서 정점의 순서를 정하는 데 사용하는 알고리즘입니다. 이는 대학교 선수 과목으로 쉽게 비유를 할 수 있습니다. 일부 과목들은 앞의 몇 개의 선수과목을 이수해야 들을 수 있는 경우가 있는데, 이런 경우까지 전부 체크해서 1학년 부터 4학년 까지 들어야 하는 과목의 순서를 나열할 때, 이 알고리즘을 사용하면 해결이 가능합니다. 원리 위상 정렬의 원리는 부모 정점과 이어저 있는 간선의 갯수(차수)를 파악하는 것입니다. 어떤 정점에서 몇 개의 차수가 있다는 것은 해당 정점을 탐색하기 전에 몇 개의 다른 정점을 탐색해야 해당 정점을 탐색할 수 있다는 의미가 됩니다. 즉 만약에 어떤 정점을 탐색을 완료했다면, 해당 정점의 탐색을 완료했기 때문의 해당 정점과 연결되어 있는 다음 정점들은 해당..