Union-Find(Disjoint Set) 알고리즘: 동적 연결성 문제와 최적화
동적 연결성
동적 연결성(Dynamic Connectivity) 문제는 객체들 사이의 연결 관계가 순차적으로 입력으로 주어질 때, 임의의 두 객체가 서로 같은 집합에 속하는지를 빠르게 판단하는 문제다. 이 때 "연결됨"은 다음 세 가지 조건을 만족하는 동치 관계(Equivalence Relation)로 볼 수 있다.
반사성: 모든 객체는 자기 자신과 연결된다.
대칭성: p가 q와 연결되 ...
9월 2일 01:24에 게시됨