유니온 파인드(Disjoint-set) 이란?
2020.01.06
유니온 파인드(Union Find)란? 서로소 집합 자료구조(Disjoint-set)이라는 알고리즘으로도 불리며, 서로 다른 부분집합 간의 병합(Union) 과정을 의미한다. 유니온 파인드는 서로 다른 집합을 합치거나, 한 집합이 다른 집합에 속해있는지를 확인하는 연산 두 가지로 이루어져있는데, 전자를 Union 이라하며, 후자를 Find라고 한다. 참고로 유니온 파인드는 집합이지만 트리로 생각하여 푸는 건데, 아래에서 설명하겠다. 1. 초기화 : 유니온 파인드는 우선 처음에 자기 자신을 루트라고 정하고 시작한다. 1 2 3 for (int i = 0; i 현재 부분집합 = {1,2}, {3,4,5} 그렇다면 2개 이상의 부분집합끼리도 붙일 수 있을까? 4)Union(2,5) 어라? 분명 {3,4,5}를..