파이썬 개발
[Python] 분리 집합, Union-Find에 대해서 알아보자!
분리집합(Union-Find)은 그래프 알고리즘 중 하나로 코딩 테스트 킬러 문제로 주로 나오는 알고리즘입니다. 서로소 집합 일단 유니온 파인드 알고리즘을 알기 전 disjoint sets을 먼저 이해해야 하는데요, 쉽게 설명하면 공통 원소가 없는 두 집합을 뜻합니다. 아래 그림을 보시면 왼쪽은 서로소 집합을 나타내고 오른쪽은 공통된 7이라는 원소 때문에 서로소 관계가 깨지게 됩니다. 따라서 왼쪽은 서로소 집합, 오른쪽은 서로소 집합이 아니게 되는 것이죠. Union-Find는 서로소 집합 자료구조를 만들 수 있습니다. 집합에서 노드들을 합치고(Union), 부모를 찾아(Find) 서로소 집합을 찾아내는 알고리즘인 것이죠. 한마디로 DSU(Disjoint Sets Union) 자료구조를 만들어 내는 과정..
