목록집합 (1)

유블로그

[알고리즘] 서로소 집합 - make, union, find 연산

서로소 집합 중복 포함된 원소가 없는 집합. 집합에 속한 하나의 특정 멤버인 '대표자'로 집합 구분 연결리스트 or 트리로 표현 서로소 집합 연산 Make-Set(x) : 유일한 멤버 x 포함하는 새로운 집합 생성 Find-Set(x) : x 포함하는 집합 찾기 Union(x, y) : x와 y 를 포함하는 두 집합을 통합하는 연산. x와 y 중 x를 대표자로 설정한다면 x는 y의 부모가 됨. 하나의 집합 = 하나의 트리 자식 노드가 부모 노드 가리킴. 루트 노드가 대표자 대표자 노드는 자기자신을 가리킴. Rank 사용 : 각 노드는 자신을 루트로 하는 subtree의 높이를 Rank로 저장 Path Compression : Find-Set 할 때 만나는 모든 노드들이 직..
알고리즘 2020. 8. 4. 16:16
이전 Prev 1 Next 다음