union-find

[백준(BOJ)] #1717- 집합의 표현 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 풀이 이 문제는 다른 거 할 거 없이 Union-Find 알고리즘만 적용하면 되는 문제입니다. 2022.07.24 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] Union-Find 알고리즘 [파이썬으로 배우는 알고리즘] Union-Find 알고리즘 Union-Find의 개념 Union-Find 알고리즘을 알기 위해서는 Disjoint S..

[파이썬으로 배우는 알고리즘] Union-Find 알고리즘

Union-Find의 개념 Union-Find 알고리즘을 알기 위해서는 Disjoint Set의 개념부터 알고 가야 합니다. Disjoint Set이란? Disjoint Set이란 상호배타적인 집합으로 서로 중복되지 않는 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조입니다. 그렇다면 이런 자료구조는 왜 필요할까요? 만약 어떤 그래프에서 한 노드와 또 다른 노드의 연결 여부를 파악한다고 해보겠습니다. 이럴 경우 완전 탐색 알고리즘인 DFS와 BFS 알고리즘으로 파악할 수 있겠죠? 하지만 할 때마다 이런 탐색을 한다고 하면 한 번의 탐색당 O(N)라는 시간 복잡도를 갖게 되고, 이는 매우 비효율적인 탐색이 될 수 있습니다. 이를 해결하기 위해서 Disjoint Set을 사용해 연결된 노드끼리..