Union-FInd 알고리즘 (1) 썸네일형 리스트형 Union-find 알고리즘 (Disjoint Set), 서로소 집합 Disjoint Set이란? 서로 중복되지 않은 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조라고 생각하면 된다. 흔히 서로소 집합 자료구조 라고도 한다. Union-Find 란? Union-Find는 서로소 집합을 표현할 때 사용하는 알고리즘이다. 집합을 표현하는 방법으로는 배열, 연결리스트 등을 이용할 수 있다. 그 중 가장 효율적인 트리 구조를 이용하여 구현한다. 보통 MST의 크루스칼 알고리즘에서 사용된다. 트리를 이용한 집합의 처리 - 같은 집합의 원소들은 하나의 트리로 관리한다. (자식 노드가 부모 노드를 가리킴) - 트리의 루트를 집합의 대표 원소로 삼는다. Union-Find 연산 Make-Set(x).. 이전 1 다음
