CS17 [알고리즘] Union-Find 서로소 집합 Disjoint Set 공통 원소가 없는 부분집합들로 이뤄진 자료구조 1) 구현 집합 구현시 배열, 연결 리스트 등 여러가지 형태가 있지만 트리를 이용하여 주로 구현한다. ex) {1,2,5,6,8} {3,4} {7}의 표현 최상단 노드인 1과 3, 7이 각 부분집합의 id라고 생각하면 된다. Union-Find disjoint set을 표현할 때 사용되는 알고리즘 Union-Find 연산 1. find 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 집합을 반환하기는 힘드니까 주로 집합을 대표하는 원소를 반환한다. 각 대표 원소들간의 파인드 결과를 비교하여 같은 집합 여부를 판단한다. 2. union 두 개의 집합을 하나의 집합으로 합친다. 3. make set 특정 한 원소만을.. 2020. 3. 13. 이전 1 2 3 4 5 다음