유니온 파인드(UNION-FIND) 파이썬 / 자바 구현

유니온 파인드(Union-Find)는 트리형태를 갖는 자료구조이다. 합집합 찾기 및 상호 배타적 집합(Disjoint-set)이라고도 한다. 이름 그대로 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용된다. 유니온 파인드(Union-Find)의 기능에 대해서 설명해보겠다. 1) Union : 두 집합을 하나의 집합으로 합치는 연산 2) Find : 어떤 원소 x가 주어졌을 때 이 원소가 속한 집합을 반환 위와 같이 두 가지 연산을 해주는 자료구조라고 할 수 있다. 정의를 알았다면 구현을 해보자 ! 구현 1. 초기화 parent 배열을 만들어준다. 파이썬 parent[a] = b #배열은 a 원소의 부모는 b이다. 라는 뜻으로 해석하면 된다. #초기화 시작 parent[i] = i ..
Coding - Algo/알고리즘&자료구조 2021. 3. 31. 13:42
1