Tree

서로소 집합(Disjoint-sets)

1. 서로소 집합의 개념 및 이해 🛺 1. 개념 서로소 집합이란 서로 중복 포함된 원소가 없는 집합을 말한다. 교집합이 없는(null) 집합이다. 2. 대표자 집합에 속한 하나의 특정 멤버를 대표자라고 한다. 이는 집합을 구분하기 위해 사용된다. 3. 예시 빠른 이해를 위해 간단한 예시를 살펴보자. 5명의 학생(A, B, C, D, E)이 있다고 하자. {A}, {B}, {C}, {D}, {E} 아래와 같은 친구 관계가 있다고 하자. A - B B - C D - E 친구 관계를 통해서 2개의 집합을 만들 수 있다. G1 = {A, B, C} G2 = {D, E} 서로 중복 포함된 원소가 없으므로 이는 서로소 집합이다. (한 사람이 분신술을 써서 양쪽 집합에 포함될 수 없으므로 당연한 결과이다.) 2. 표..