서로소 집합
-
💡파이썬 Disjoint-Set(Union-Find) 이론 및 예제| 자료구조 & 알고리즘/알고리즘 2023. 11. 29. 01:49
알고리즘 코딩 테스트를 준비하다 보면 다양한 자료구조와 알고리즘을 만나게 됩니다. 그 중에서도 Disjoint-Set(서로소 집합)을 활용한 Union-Find는 중상난이도 문제에서 자주 출제되는 유형 중 하나입니다. 이번 글에서는 Disjoint-Set, Union-Find의 개념과 파이썬으로 구현하는 방법에 대해 알아보겠습니다. Disjoint-Set(Union-Find)이란? 단순히 disjoint-set은 서로 다른 두 집합(서로소 집합)을 뜻함 서로 다른 집합을 모아 하나의 집합으로 만드는 Union-find 알고리즘에 사용됨 사용되는 case 그래프에서 서로 다른 정점을 연결하는 최소 신장 트리를 구하는 문제 서로 다른 집합을 합치는 문제 등 수행 연산 Union: 두 개의 집합을 하나로 합치..