서로소 집합

서로소 집합이란? 서로소 집합(분리 집합; Disjoints Sets)이란 공통 원소가 없는 집합들을 의미한다. 주로 트리 형태로 구현하며, 원소가 어떤 집합에 속해 있는 지 찾는 Find 연산과 두 집합을 합치는 Union 연산을 사용해 Union-Find라고도 불린다. 서로소 집합은 그 자체로도 자주 사용되지만 다른 자료 구조나 알고리즘에 적용되는 경우도 많다. (크루스칼 알고리즘, 그래프 사이클 판별, 동적 연결성 판정 등) 구현해보기 (코드) 서로소 집합은 트리 구조를 이용해 구현할 수 있는데, 같은 루트 노드를 가진 원소들은 같은 집합에 속해 있는 것이라고 보면 된다. 초기 단계 초기 단계에서는 각 원소들이 서로 다른 집합에 속해있다. 따라서 각 원소들은 자기 자신을 부모로 가진다. 각 원소들의..

문제 1부터 N까지의 번호를 가진 N명의 사람이 있다. 각 사람들은 1부터 N 사이의 임의의 수 Ci가 쓰여있는 카드를 한 장씩 가지고 있다. 사람들 간에는 총 M쌍의 친구 관계가 있다. 모든 친구 관계는 양방향이라서, a번 사람과 b번 사람이 친구라면 b번 사람과 a번 사람도 친구이다. 서로 친구 관계에 있는 두 사람끼리는 서로 들고 있는 카드를 원하는 만큼 교환할 수 있다. 모든 사람들은 각자가 들고 있는 카드에 적힌 수가 자신의 번호와 최대한 비슷하기를 원한다. 어떤 한 사람의 불만족도를 그 사람이 들고 있는 카드에 적힌 수와 그 사람의 번호와의 차이로 정의하고, 전체 불만족도는 모든 사람의 불만족도의 합으로 정의한다. 카드 교환이 적절하게 이루어졌을 때, 가능한 전체 불만족도의 최솟값을 구하라. ..