목록알고리즘/알고리즘 이론 (1)
study blog
[알고리즘] 유니온 파인드 (Union-Find)
유니온 파인드란? 대표적 그래프 알고리즘으로 서로소 집합 ( Disjoint - set ) 를 찾는 알고리즘 Disjoint - set : 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 자료구조 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 서로 같은 그래프에 속하는지 판별하는 알고리즘 3가지의 연산으로 이루어져 있다. make : 가장 작은 단위의 단위 집합을 만드는 연산 (초기화 연산) Find : 해당 노드가 속한 집합을 찾는 연산 ( 해당 노드가 속한 집합의 대표자를 찾는 연산 ) Union : x가 속한 집합과 y가 속한 집합을 합치는 연산 보통 연결리스트 혹은 트리로 구현하는데 연결리스트로 구현하기보다 자신의 집합에 속해있는 부모의 관계를 이용해 배열로 구현..
알고리즘/알고리즘 이론
2022. 6. 7. 15:17