이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 자료구조 — 효율적인 데이터 관리의 핵심 → 자료구조 — 효율적인 데이터 관리의 핵심 → 고급 자료구조
Disjoint sets with path compression, segment tree, Fenwick tree, lazy propagation.
초기: {1} {2} {3} {4} {5} (각각 독립)Union(1,2): 2→1 (1이 루트)오늘은 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 최소 신장 트리에서 사이클 판정에 핵심적으로 쓰여요.
네트워크 연결 확인, 그래프의 연결 요소 세기에도 필수적이에요.
지금부터 최적화 기법을 하나씩 자세히 알아보겠습니다.
선생님: Union-Find에서 Find 연산의 역할이 뭔지 설명해볼래요?
학생: 주어진 원소가 어떤 집합에 속하는지 알기 위해 루트를 찾아가는 거예요.
선생님: 맞아요. 그렇다면 두 원소가 같은 집합인지 어떻게 판단하나요?
학생: 두 원소에 각각 Find를 해서 루트가 같으면 같은 집합이에요!
선생님: 정확해요. 루트가 집합의 대표 역할을 하는 거죠. 이 단순한 원리가 그래프 알고리즘의 핵심이 됩니다.