Computer Science/Algorithm
[Algorithm] 서로소 집합(Disjoint Set)과 유니온 파인드(Union-Find) 정리
[Algorithm] 서로소 집합(Disjoint Set)과 유니온 파인드(Union-Find) 정리
1. 서로소 집합(Disjoint Set)이란?서로소 집합(Disjoint Set)은 겹치는 원소가 없는 집합들의 모임을 의미한다.서로소 집합의 핵심 연산서로소 집합을 다룰 때 핵심적으로 사용하는 연산은 다음과 같다.makeSet(x): 각각의 원소를 독립적인 집합으로 초기화findSet(x): 특정 원소 x가 속한 집합의 대표(루트) 찾기union(x, y): 두 개의 집합을 합치기서로소 집합의 활용서로소 집합은 유니온-파인드(Union-Find) 알고리즘을 사용하여 효율적으로 집합 연산을 수행할 수 있다.대표적인 활용 예시는 다음과 같다.네트워크 연결 확인 (컴퓨터 네트워크, 친구 관계)최소 신장 트리(MST, Kruskal's Algorithm)동일 집합 여부 확인 (서로소 판별)경로 압축(Path..
