집합
-
[알고리즘] 집합 찾기(Union Find)프로그래밍/알고리즘 2019. 6. 5. 20:17
List 1. 연결 리스트를 이용한 집합 찾기 2. 배열을 이용한 집합 찾기 3. 트리를 이용한 집합 찾기 4. 연산의 효율을 높이는 법 ※ 코드구현은 생략 연결 리스트를 이용한 집합 찾기 연결리스트를 이용한 표현에서 집합의 원소는 노드로 표현이 됩니다. 각 노드에는 원소를 저장하는 필드, 다음 원소와 대표 원소를 기리키는 두 개의 포인터가 있습니다. 다음 원소를 가리키는 포인터를 통해 집합의 모든 원소들이 연결됩니다. 여기서 대표 원소는 각 집합의 가장 앞에 있는 원소를 의미합니다. 그리고 각 집합에는 마지막 원소를 가리키는 tail 변수 라는것이 존재합니다. 이 변수는 두 집합을 합칠 때 이용됩니다. 하나의 원소 x 만을 갖고 있는 집합이 있다고 가정해봅시다. 연결 리스트의 한 노드의 구성은 오른쪽 ..