Disjoint set1 Disjoint-Set / Union-Find (디스조인트 셋, 유니온 파인드) 저는 예전에 디스조인트 셋이 유니온 파인드인지 몰라서 엥? 디스조인트 셋? 이건 뭐랭 했었는데 알고보니 같은 말이었네요ㅋㅋㅋ 그래서 말이죠, 오늘은 크루스칼에서도 사용되는 Disjoint Set을 알아볼게요. Disjoint Set의 원리는 서로소 집합과 연관되어 생각하면 됩니다. 새로운 집합을 추가하거나, 기존의 집합과 합치거나, 집합에 어떤 원소가 들어있는지 찾는 연산을 거의 선형시간에 가깝게 수행하는 자료구조라고 할 수 있죠. Disjoint Set이 Union-Find라고도 불리는 이유는, Disjoint Set을 구성하는데에 union과 find라는 함수? 개념? 을 사용하기 때문입니다. find를 통해서 a라는 요소가 b라는 요소와 같은 집합인지(연결되어 있는지) 를 확인 할 수 있고, uni.. 2021. 3. 3. 이전 1 다음
