Union Find
-
[자료구조 알고리즘] DSU(Disjoint Set Union) / Union Findalgorithm 2020. 6. 21. 22:49
DSU, 흔히 Union Find라고 불리는 Union과 Find의 연산을 제공하는 자료구조 - Disjoint set으로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 - Union/Find 2 가지의 연산을 지원하는 자료구조 - union by rank 와 path compression을 통한 최적화 자세한건 아래 유튜브 영상을 확인 부탁드리며 도움이 되셨다면 구독과 좋아요 부탁드립니다 :)
-
DSU(Disjoint Set Union) 자료구조algorithm 2019. 10. 15. 23:31
Disjoint Set Union or DSU는 Union Find 라고 보통 불려진다. 이 자료구조는 2가지의 union과 find 연산을 매우 빠르게 해준다. 1. union은 2개의 set을 하나의 set으로 합쳐주는 것을 말한다. 2. find는 모든 element는 어떤 집합에 속해져있는데 이때, find는 특정 element가 속해져있는 집합에서 해당 집합을 대표하는 대표원소를 반환해주는것을 말한다. 즉, 트리를 예로들면 어떤 노드를 find를 수행하였을때 반환되는값은 인자 노드의 대표원소(최상위 부모노드)가 반환되게 된다. 경로압축(Path compression optimization) 경로 압축은 find 연산을 수행할때 마다 트리의 구조를 평평하게 만드는 방법이다. 경로를 찾아가는 과정에..