목록disjoint set #분리집합 # 분리집합 c++ #상호배타적집합 #알고리즘공부 #c++ (1)

조던을좋아하는코린이

Union Find = 서로소 집합(Disjoint-Set),분리집합

분리 집합은 서로소 집합이라고도 부른다. 분리 집합의 특징으로 - 전체 집합 U에 대해, U의 분리집합은 A, B는 다음을 만족한다. 1) A,B 는 U의 부분집합이다. 2) 집합 A,B는 같은 원소를 가지지 않는다. 3) A,B의 합집합이 곧 전체집합(U)이다. ( A,B에 속하지 않는 원소는 U에도 속하지 않는다 ) - 그림 (1)과 같은 경우를 제외한 나머지 (2) (3) 번의 경우는 될 수없다. - 집합이 3개 이상의 경우에도 똑같이 적용된다. - Union Find 알고리즘 - 분리 집합을 구현하는 알고리즘으로써, 트리의 형태로 표현이 된다. 배열을 이용하여 보통 구현이 된다. 다음과 같은 집합들이 존재할 때 연결정보를 입력할 때 값이 작은값을 기준으로 갱신을 한다. 따라서 그림 은 ..
알고리즘 학습 ( C++ ) 2022. 8. 11. 12:27
이전 Prev 1 Next 다음