연결트리1 [자료구조] ep8) 분리집합(Disjoint Set) ㅇ분리집합 ADT: 교집합이 없는 집합들서로소집합이라고도 불리며 Union-Find라고도 한다 소속 관계가 분명해야 하는 데이터를 다룰 때 유용하다목적: 원소가 어느 집합에 귀속되어 있는지 (find 함수) 직접 응용: 동치관계(e.g. 그래프), 최소신장트리간접 응용: 알고리즘 구현, 저료구조 구현 - set find(e): 원소 e가 속한 집합을 반환- union(x, y): 집합 x, y를 통합- int size(S): 집합 S 원소의 수를 반환 [구현 방법 2가지]1. 리스트(or 배열)에 기초한 구현 find는 빠르고 union은 느리다2. 트리에 기초한 구현find는 느리고 union은 빠르다 1-1 리스트에 기초한 구현: 분리집합 집단을 레코드의 배열로 표현 1-2 배열에 기초한 구현.. 2024. 6. 11. 이전 1 다음
