코딩못하는사람

Chess Tournament www.acmicpc.net/problem/13344 1.접근 문제를 보고 동점인 경우에는 같은 차수의 집합이 생길거라고 생각해서 disjoint set을 바로 생각했다. 일관성이 있는지 없는지를 판단하려면 위상정렬을 시켜서 순서대로 진행했을때 위상정렬이 정상적으로 수행되면 일관성이 있는 것이고 차수가 0인게 존재하지않아서 큐에서 뽑을게없으면 사이클이 생겨 일관성이 없다고 판단했다. 2.풀이 중요한 것은 집합을 모두 만들고 > 연산을 수행하는 것이다. 처음에는 =,> 연산을 들어올때마다 했는데 바뀌는 것이 매번 많아서 코드가 복잡했다. 그래서 '='이 나왔을 때 유니온을 합치는 작업부터 모두 수행하고 그다음 '>' 작업을 했다. 모든 병합이 완료되면 경로 압축을 통해 부모노..

위상정렬 (Topological Sort) 위상정렬은 순서가 정해져있는 작업을 수행할 때 그 순서를 결정해주기 위해서 사용되는 알고리즘이다. 순서가 정해져있다는 말은 조건이 걸린다고 생각하면 편하다. 어떠한 작업은 어떠한 이전작업들이 수행되야 수행된다라는 순서가 정해져있는 것이다. 그림을 생각해야 이해가 편하므로 그림을 보자. 각 정점들은 자신을 가르키고 있는 모든 정점들이 수행된 후에 실행될 수 있다. 가르켜 지고있는 수를 차수(degree)라고 하자. 예를들어 정점2는 정점1 하나가 가르키고 있으므로 차수는 1이다.6번은 4,5로 인해 2이고 1번은 0이 될 것이다. 그렇다면 가능한 순서를 임의로 정해보자 1->2->3->4->5->6->7도 가능할 것이고 1->2->3->5->4->6->7 등등 순..