728x90 서로소집합1 유니온 파인드 (Union Find, Disjoint set) 유니온 파인드 (Union Find, Disjoint set) 정의 유니온 파인드(Union Find) 는 서로소 집합(Disjoint-set) 이라고도 불린다. 이는 집합 혹은 그룹 관리를 효율적으로 할 수 있는 알고리즘 이다. 그룹은 트리의 구조로 관리가 된다. 한 트리에 여러 그룹이 있는 것이 아니라 그룹의 개수만큼 트리가 생성이 되는 것 이다. 설명 위 예시의 경우는 두 가지 트리가 존재한다. 그룹이 두 개 존재하는 경우인 것 이다. 두 노드끼리 같은 그룹인지 아닌지 판단하는 기준은 해당 노드의 루트 노드가 같은지 판단하면 된다. 위 예시에서 2, 4번째 노드는 둘 다 루트노드가 1로 동일하다. 따라서 같은 그룹이다. 하지만 3, 6번째 노드는 각각 루트노드가 1, 5번째 노드이다. 따라서 이 두.. 2021. 8. 6. 이전 1 다음 728x90
