728x90
Union-Find 알고리즘
- Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘
- 노드들 중에 연결된 노드를 찾거나 노드들을 서로 연결할 때(합칠 때)사용
- Disjoint Set은?
- 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
- 공통 원소가 없는(서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조
- Disjoint Set = 서로소 집합 자료구조
1. 초기화
- n개의 원소가 개별 집합으로 이뤄지도록 초기화
A | B | C | D | E | F |
2. Union
- 두 개별 집합을 하나의 집합으로 합침(두 트리를 하나의 트리로 만듦)
3. Find
- 여러 노드가 존재할 때 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 각 그룹의 최상단 루트 노드를 확인
Union-Find 알고리즘의 고려할 점
- Union 순서에 따라서 최악의 경우 링크드 리스트와 같은 형태가 될 수 있음
- Find/Union시 계산량이 O(N)이 될 수 있으므로 해당 문제를 해결하기 위해 union-by-rank, path compression 기법을 사용함
'IT개발 > 알고리즘, 우리 친해지자!' 카테고리의 다른 글
기초 알고리즘 문제 : 백준 1001번 Java (0) | 2021.10.16 |
---|---|
기초 알고리즘 문제 : 백준 1000번 Java (0) | 2021.10.13 |
알고리즘 : 최소 신장 트리1 (0) | 2021.10.02 |
알고리즘 : 최단 경로 (0) | 2021.09.30 |
알고리즘 : 탐욕 알고리즘 (0) | 2021.09.27 |