GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결
알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub.
github.com
요약
Union-Find는 다음과 같은 집합 연산을 거의 O(1)에 수행할 수 있는 자료 구조이다.
- 두 집합을 병합하는 Union 연산
- 자신이 속한 집합을 찾는 Find 연산
Union-Find를 naive하게 구현할 경우 시간 복잡도는 O(N)이다.
union by size(rank) 및 경로 압축 기법을 적용할 시 시간 복잡도는 거의 O(1)이 된다.
연습 문제
1. Association for Control Over Minds
sum of size == M
2. Ladice
vector<bool>
3. Almost Union-Find
N개의 dummy node
4. People on a Line
가중치 UF
끝
끝
'알고리즘' 카테고리의 다른 글
| Euler's theorem (0) | 2022.10.06 |
|---|---|
| Euler's phi function (0) | 2022.10.05 |
| Order Statistic Tree (0) | 2022.10.01 |
| Fenwick Tree (0) | 2022.09.30 |
| Knuth's Optimization (0) | 2022.09.28 |
