코딩못하는사람

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

유니온 파인드 말 그대로 집합,공동체를 찾는다는 것이다. 집합으로 묶어서 풀면 좋은 문제를 풀 때 효율적으로 풀기좋다. 특히 집합끼리 묶는것을 쉽게 만들어 준다. 모든 원소들을 자기 자신을 부모노드로 초기화 한다. 집합을 합치는 것은 부모노드를 같게 만들어줌으로써 집합을 만들 수 있다. 같은집합에 속해있는것은 find를 통해 부모노드를 찾는 함수를 활용하여 같은 부모노드를 가르키면 같은 집합,아니면 다른 집합에 포함되있는 것이다. 유니온 파인드에는 3가지 과정이 있다. 1.각자 자신으로 부모노드를 초기화한다. 2.find(부모노드 찾기) def find(v): if parent[v]==v: return v else: parent[v]=find(parent[v]) return parent[v] 사실 els..