유니온 파인드

[Algorithm] 유니온 파인드

[Algorithm] 유니온 파인드 (글쓴날 : 2020.05.16) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 유니온 파인드 1) 유니온 파인드란? 유니온 파인드란 집합을 관리하는 트리 형태의 자료구조로 Disjoint-set(서로소 집합, 분리 집합)이라고도 하며, 보통 배열에서 인덱스를 노드로 나타내어 각 인덱스의 값에 해당 인덱스의 부모 노드를 저장합니다. 유니온 파인드는 주로 그래프 문제에 적용할 수 있으며, 다른 그래프 알고리즘인 Dijkstra algorithm, Bellman-Ford algorithm 등과 달리, 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용됩니다. 핵심 연산으로는 2가지가 있으며, 유니온 파인드라는 이름과 걸맞게 다음과 같습니다. 1) uni..