Algorithm
2022. 1. 8.
[Swift] Union-Find 자료구조 구현해보기
Union-Find 자료구조 개념 Union-Find는 서로소 부분집합 구조로 나뉘어진 데이터들을 다루는 자료구조입니다. 여기서 서로소 부분집합이란?? 수학적으로 표현하면, {1,2}, {3,4}, {5,6} 과 같이 서로 다른 원소들을 가진 집합들 사이 관계를 의미합니다. 3가지 집합에서 서로 공통된 원소가 없으면 서로소 부분집합이라고 합니다. 그럼 이를 어떻게 구현할까요? 두가지 함수와 한개의 배열로 구현해볼 수 있습니다. Parent 배열 먼저, 자기 자신을 가리키는 parent 배열 한개를 만들어줍니다. 0 1 2 3 4 5 0 1 2 3 4 5 이 parent 배열은 자신의 부모를 가리킵니다. 처음 시작은 모두 각자 자기자신을 부모로 가지고 있습니다. findParent(A) A원소의 부모가 어..