경로 압축을 적용한 DSU
거의 상수 시간에 찾기와 합치기를 수행합니다
경로 압축을 적용한 DSU은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
DSU가 추적하는 것
서로소 집합 결합은 항목들을 서로 겹치지 않는 집합으로 묶어 관리하므로, 두 항목이 이미 같은 집합에 속하는지 확인할 수 있습니다. 🤝
트리로 표현하는 집합
DSU는 각 집합을 트리로 저장합니다. 모든 원소는 부모를 가리키며, 가장 위에 있는 노드인 루트가 전체 그룹의 고유한 이름이 됩니다.
부모 배열
이 모든 연결을 하나의 배열에 저장합니다. 각 원소를 자신의 부모로 시작하게 하면 모든 항목이 처음에는 각자 하나의 집합을 이룹니다.
parent = list(range(n))루트 찾기
find 연산은 어떤 원소가 자기 자신을 가리킬 때까지 부모 연결을 따라 위로 올라갑니다. 자기 자신을 가리키는 노드가 집합을 식별하는 루트입니다.
while parent[x] != x:
x = parent[x]긴 연결은 느립니다
주의하지 않으면 집합이 길고 가느다란 연결을 이룰 수 있습니다. 그러면 find가 노드를 하나씩 따라가야 하므로 한 번의 질의에 O(n)이 걸릴 수 있어 너무 느립니다.
경로 압축 도입하기
경로 압축이 이 문제를 해결합니다. 루트를 찾는 동안 방문한 모든 노드가 루트를 직접 가리키도록 바꾸어 다음번을 위해 트리를 평평하게 만듭니다. ⚡
재귀로 압축하기
가장 깔끔한 방법은 재귀입니다. 루트를 찾은 다음 반환하기 전에 parent[x]에 그 루트를 다시 저장하면 연결이 영구적으로 짧아집니다.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]두 항목이 같은 집합일까요
두 원소가 연결되었는지 확인하려면 루트를 비교하세요. find(a) = find(b)이면 같은 그룹에 속하고, 그렇지 않으면 아직 서로 떨어져 있습니다.
if find(a) == find(b):
print("connected")두 집합 합치기
union 연산은 한 루트가 다른 루트를 가리키게 하여 그룹을 합칩니다. 한 줄로 두 전체 트리를 하나의 집합으로 연결할 수 있습니다.
def union(a, b):
parent[find(a)] = find(b)이토록 빠른 이유
경로 압축만 사용해도 연산은 대략 O(log n)의 분할 상환 시간에 실행되며, 순위 관리와 함께 사용하면 질의 하나당 거의 상수 시간이 됩니다.
DSU가 빛나는 곳
DSU는 연결성에 관한 문제를 해결합니다. 친구 관계, 네트워크 구성 요소, 크루스칼의 신장 트리 모두 빠른 find와 union에 의존합니다. 🌐
빠른 확인
경로 압축이 실제로 무엇을 바꾸는지 생각해 보세요.
복습
DSU를 구현했습니다. 부모 배열, 루트를 찾는 find, 집합을 합치는 union을 사용합니다. 경로 압축 덕분에 매우 빠르게 동작합니다. 잘하셨습니다! 🎉
자주 묻는 질문
“경로 압축을 적용한 DSU” 강의는 무료인가요?
네 — “경로 압축을 적용한 DSU” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“경로 압축을 적용한 DSU”에서 뭘 배우나요?
거의 상수 시간에 찾기와 합치기를 수행합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“경로 압축을 적용한 DSU” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 경로 압축을 적용한 DSU
- 랭크에 따른 합치기와 구성 요소
- 크루스칼의 최소 신장 트리
- 힙을 이용한 프림의 MST