Union-Find
- 자료구조중 하나
- n개의 set를 가지고있음
- 각각은공집합이 없음
- 초기에는 set이 모두 원소가 1개인 집합임
- union과 find연산을 제공
- 각 set에서는 parent로가는 방향만 존재함
- root에서는 자기자신에게 감
- root가 각 set의 대표이고 각 set은 트리로 표현
- 위 트리를 배열로 표현할떄 각 노드는 자신의 parent인덱스를 가지고 있으면 됨
- 기능
- find -> 노드의 루트찾기
- same_set -> 루트가 같아야 같은 set
- union -> union(1,2)이면 1의 루트를 2의 루트로 바꾸는 것
- n개의 싱글톤 셋 만들기
- union과정에서 트리의 높이가 계속 높아지는 문제가 생길 수 있음(이러면 find에 시간이 오래걸림)
- 이때 키가 작은 트리가 높은 트리에 붙게 해주면서 해결(개선1)
- size를 추가해서 코딩
- worst
- 노드의 개수가 2배 늘어날떄마다 높이가 1증가(logn)
- 연산시간 종합
- 처음 루트를 찾았을때 parent를 루트로 변경시키는 방법으로 find의 연산시간을 줄일 수 있음(개선2), Path Compression
- Path Compression2
- parents를 grand parents로 만들어주는 과정의 반복으로 할 수도 있음(한번 할때마다 반씩 줄어듬)
- log*n : 로그를 몇번 취해야 1보다 작아지는지
- 최종 정리
- m번의 union/find를 할때의 시간
KMU SW