유니온-파인드(Union-Find, Disjoint Set)의 주된 용도는?

어려움 freeCodeCamp

보기 및 정답

A 서로소 집합(겹치지 않는 그룹)의 합치기(union)와 어떤 그룹에 속하는지 찾기(find)를 효율적으로 수행한다

B 정렬된 배열에서 두 개의 포인터를 사용하여 특정 조건을 만족하는 원소 쌍을 찾는 알고리즘이다

C 두 개의 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 찾는 알고리즘이다

D 이진 탐색 트리에서 새로운 노드를 삽입하거나 기존 노드를 삭제하고 균형을 유지하는 트리 기반의 자료구조 관리 알고리즘이다

유니온-파인드는 원소들을 그룹으로 묶고(union), 특정 원소가 어떤 그룹에 속하는지(find) 빠르게 확인하는 자료구조입니다. 경로 압축과 랭크 합치기로 거의 O(1)에 수행됩니다. 크루스칼 MST, 네트워크 연결 판단 등에 사용됩니다.

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

로그인