분리 집합(Disjoint Set)
서로 중복되지 않는 집합들로 나눠진 원소들에 대한 정보를 저장 및 조작하는 자료구조. 서로소 집합이라고도 불리움
[분리집합 규칙]
전체 집합 U
- A, B는 U의 분리 집합
- A, B는 공통 원소를 가지지 않음
- A, B의 합집합이 곧 전체 집합 U
=> 분리 집합의 개수가 N개 일때도 동일하게 적용되는 규칙
=> 이미 존재하는 집합 U에 대해 겹치는 부분이 발생하지 않도록 모든 원소들을 분리한 부분집합.
교집합이 존재하지 않는 둘 이상의 집합.
데이터 집합을 다룰 때 유용하게 쓰임.
형태 : 자식 노드가 부모 노드를 가리키는 형태.
교집합이 없으므로 차집합 연산 또한 없음
=> Union - Find로 구현함
출처 :
https://4legs-study.tistory.com/94
https://go-coding.tistory.com/28
도전! 데이터 엔지니어