개발/이코테
서로소 집합 알고리즘
이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다. 서로소 집합 이란 서로소 집합 공통 원소가 없는 두 집합을 의미. {1,2} {3,4}는 서로소 관계 {1,2} {2,3}은 서로소 관계가 아님. 서로소 집합 자료구조 '서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조' 이다. 서로소 집합 자료구조는 두 종류의 연산을 지원함. 합집합 : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산. 찾기 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산. => 서로소 집합 자료구조는 '합치기 찾기 자료구조'로 불리기도 함. 여러 개의 합치기 연산이 주어졌을 때, 서로소 집합 자료구조의 동작 과정은 다음과 같다. 1. 합집합 연사을 확인하여, 서로 연결된 두 ..
2022. 4. 22.