Disjoint-Set

디스조인트 셋 (Disjoint-Set) 디스조인트 셋은 서로 겹치지 않는(disjoint) 부분 집합들로 나누어진 요소들의 집합을 표현하고 조작하는 데이터 구조이다. 각 부분 집합은 대표 요소(representative)를 가지며, 이를 통해 집합을 식별한다. 특징 동적 집합 관리: 요소들을 동적으로 그룹화하고 관리할 수 있다. 빠른 연산: Union과 Find 연산을 매우 효율적으로 수행한다. 경로 압축과 랭크 최적화: 트리 구조를 최적화하여 성능을 향상시킨다. 장점 효율성: 거의 상수 시간에 가까운 연산 복잡도를 제공한다. 간단한 구현: 기본 개념이 직관적이고 구현이 비교적 간단하다. 메모리 효율성: 추가적인 데이터 구조 없이 요소들의 관계를 표현한다. 단점 제한된 기능: 주로 Union과 Find 연산에 특화되어 있어 다른 복잡한 연산은 지원하지 않는다. 초기 설정 비용: 모든 요소에 대해 초기 집합을 생성해야 한다. 응용 Kruskal의 최소 신장 트리 알고리즘 사이클 검출 알고리즘 네트워크의 연결성 확인 이미지 세그멘테이션 동작 원리 디스조인트 셋은 트리 구조를 사용하여 집합을 표현한다. 각 트리의 루트 노드가 해당 집합의 대표 요소가 된다. ...