랭크에 따른 합치기와 구성 요소
트리를 평평하게 유지하고 그룹을 셉니다
랭크에 따른 합치기와 구성 요소은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
union은 느슨하게 합칠 수 있습니다
일반적인 union은 한 루트를 다른 루트 아래에 연결하기만 합니다. 부주의하게 처리하면 키가 크고 느린 트리가 만들어지므로, 루트를 더 똑똑하게 합치는 방법이 필요합니다.
핵심 아이디어
순위에 따른 union은 항상 더 짧은 트리를 더 긴 트리 아래에 붙입니다. 트리를 얕게 유지하면 이후의 모든 find가 더 빨라집니다. 📏
순위의 의미
순위는 트리 높이의 추정치입니다. 단일 노드는 아래쪽 깊이가 없으므로 각 원소의 순위는 0에서 시작합니다.
rank = [0] * n짧은 트리를 긴 트리 아래에 붙이기
두 루트의 순위를 비교하세요. 순위가 더 작은 루트가 자식이 되므로, 합쳐진 트리가 최대한 평평하게 유지됩니다.
if rank[ra] < rank[rb]:
parent[ra] = rb동률이면 순위 증가
두 루트의 순위가 같으면 어느 한쪽을 새 루트로 선택하고 순위를 1 증가시키세요. 트리가 한 단계 더 높아졌기 때문입니다.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1크기에 따른 union 변형
널리 쓰이는 다른 방법은 크기에 따른 union입니다. 더 작은 집합을 더 큰 집합 아래에 붙입니다. 효과는 똑같이 좋고 그룹의 크기도 추가 비용 없이 얻을 수 있습니다.
구성 요소 개수 세기
모든 원소가 각자의 그룹이므로 개수를 n으로 시작하세요. union이 성공할 때마다 두 그룹이 하나로 합쳐지므로 개수를 줄입니다.
components = n아무 작업도 하지 않는 union 건너뛰기
두 원소가 이미 같은 루트를 공유한다면 union은 아무 작업도 하지 않습니다. 루트가 실제로 다를 때만 개수를 줄이세요.
if find(a) != find(b):
union(a, b)
components -= 1순위와 경로 압축 함께 사용하기
순위에 따른 union과 경로 압축을 함께 사용하면 DSU가 역 아커만 시간에 실행됩니다. 실제 입력에서는 사실상 상수 시간입니다. ⚡
필요할 때 그룹 크기 확인하기
크기에 따른 union을 사용하면 어떤 그룹의 크기든 즉시 확인할 수 있습니다. 해당 원소의 루트에 저장된 크기를 읽기만 하면 됩니다.
group = size[find(x)]이것이 유용한 곳
컴포넌트 개수 세기는 합치기 호출이 연속해서 이루어진 뒤 친구 모임 수나 연결된 영역 수와 같은 고전적인 질문에 답합니다. 🌐
빠른 확인
컴포넌트 카운터가 어떻게 변하는지 추론해 보십시오.
복습
트리를 평평하게 유지하는 랭크에 따른 합치기와 컴포넌트 개수 및 그룹 크기를 추적하는 방법을 배웠습니다. 이제 DSU는 매우 빠르게 동작합니다! 🎉
자주 묻는 질문
“랭크에 따른 합치기와 구성 요소” 강의는 무료인가요?
네 — “랭크에 따른 합치기와 구성 요소” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“랭크에 따른 합치기와 구성 요소”에서 뭘 배우나요?
트리를 평평하게 유지하고 그룹을 셉니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“랭크에 따른 합치기와 구성 요소” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 경로 압축을 적용한 DSU
- 랭크에 따른 합치기와 구성 요소
- 크루스칼의 최소 신장 트리
- 힙을 이용한 프림의 MST