[Algorithm] Union-Find

알고리즘 개념유니온 파인드(Union-Find) 알고리즘은 분리 집합을 관리하는 알고리즘으로그래프 형태의 자료들의 연결 정보를 알고 싶을 때 사용된다.이 알고리즘의 핵심 목표는 합치기(Union)와 찾기(Find) 작업을 효율적으로 수행하는 것이다.주로 그래프에서 연결된 컴포넌트 관리 나 사이클 검출에 활용된다.    - 집합 소속 여부 판단 & 사이클 검출 : 임의의 두 노드의 연결 여부(집합 소속 여부) 확인        - 단, 무방향 그래프에서만 적용 가    - 경로 압축 : 그래프 내 노드 간의 경로 최적화  위의 경우 3과 5가 같은 그룹인지 알려면왼쪽의 경우 자신의 부모만 기록되어 있으므로 연결여부 확인이 따로 필요하다.이때 재귀 호출을 통해 루트 노드를 찾을 때 탐색 시간이 소요된다.un..

2024.11.12