코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
자료구조 — 효율적인 데이터 관리의 핵심 → 고급 자료구조
초기: {1} {2} {3} {4} {5} (각각 독립)
Union(1,2): {1,2} {3} {4} {5}
Union(3,4): {1,2} {3,4} {5}
Union(1,3): {1,2,3,4} {5}
Find(4) → 1 (대표 원소)
Find(5) → 5 (자기 자신)
Find(2) == Find(3)? → true (같은 집합!)
트리로 표현:
Union(1,2): 2→1 (1이 루트)
Union(3,4): 4→3 (3이 루트)
Union(1,3): 3→1 (1이 전체 루트)
1
/ \
2 3
|
4
용도: Kruskal MST, 연결 요소, 동치 관계, 네트워크 연결 판정오늘은 Union-Find, 즉 서로소 집합 자료구조를 배워볼게요.
Union-Find는 여러 원소를 겹치지 않는 집합으로 관리하는 자료구조예요.
영어로는 Disjoint Set Union, 줄여서 DSU라고도 불러요.
그림 왼쪽을 보세요, 처음에는 각 원소가 자기 자신이 대표예요.
parent 배열이 0, 1, 2, 3, 4로 자기 자신을 가리키고 있죠.
이건 마치 5명이 각각 1인 팀을 이루고 있는 것과 같아요.
가운데 상자를 보시면 Union 연산의 결과가 보여요.
Union 1, 3을 하면 1번과 3번이 같은 집합이 되고요.
Union 2, 4를 하면 2번과 4번이 같은 집합이 됩니다.
한 원소의 parent를 다른 원소로 바꾸는 게 Union의 핵심이에요.
오른쪽 상자를 보면 Find 연산이 나와요.
Find 3을 하면 3의 parent인 1에 도달하고, 1이 루트예요.
루트란 parent가 자기 자신인 원소를 말해요.
두 원소의 Find 결과가 같으면 같은 집합에 속한 거예요.
이것이 바로 연결 판정의 핵심 원리입니다.
하단의 비교 테이블을 보세요.
Find는 루트를 찾고, Union은 두 집합을 합쳐요.
최적화를 적용하면 두 연산 모두 거의 O 1이에요.
알파 n은 역 아커만 함수로, 현실에서 5를 넘지 않아요.
Kruskal 최소 신장 트리에서 사이클 판정에 핵심적으로 쓰여요.
네트워크 연결 확인, 그래프의 연결 요소 세기에도 필수적이에요.
지금부터 최적화 기법을 하나씩 자세히 알아보겠습니다.