[Python] 알고리즘 개념14 퀴즈 - 유니온 파인드

 

📌 퀴즈 개요

다음 퀴즈를 통해 유니온 파인드(Disjoint Set) 개념을 정확히 이해하고 있는지 확인해 보세요! 😊

---

 

 

🧩 1. 개념 이해 문제

 

(1) 유니온 파인드(Disjoint Set)의 특징으로 옳지 않은 것은?

1. 여러 개의 집합을 관리하고, 두 원소가 같은 집합에 속해 있는지 확인할 수 있다.
2. Find 연산을 사용하여 특정 원소가 속한 집합의 대표 노드를 찾을 수 있다.
3. Union 연산을 사용하여 서로 다른 두 집합을 합칠 수 있다.
4. 유니온 파인드는 항상 O(1)의 시간복잡도로 동작한다.

 

(2) 경로 압축(Path Compression)에 대한 설명으로 옳지 않은 것은?

1. Find 연산을 수행할 때, 중간에 있는 모든 노드들이 루트 노드를 직접 가리키도록 한다.
2. 경로 압축을 적용하면 트리의 높이가 낮아져 성능이 개선된다.
3. 경로 압축을 적용한 유니온 파인드는 거의 O(1)의 성능을 가지게 된다.
4. 경로 압축을 사용하면 Find 연산이 더 느려진다.

---

 

 

🧩 2. 실전 문제

 

(3) 다음 코드의 실행 결과는?

class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축 적용
        return self.parent[x]

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a

dsu = DisjointSet(5)
dsu.union(1, 2)
dsu.union(2, 3)
print(dsu.find(3))

1. 1
2. 2
3. 3
4. 0

 

(4) 다음 코드가 실행될 경우 출력될 결과는?

class DisjointSet:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size  # 랭크 정보 추가

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축 적용
        return self.parent[x]

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            if self.rank[root_a] > self.rank[root_b]:
                self.parent[root_b] = root_a
            else:
                self.parent[root_a] = root_b
                if self.rank[root_a] == self.rank[root_b]:
                    self.rank[root_b] += 1

dsu = DisjointSet(6)
dsu.union(1, 2)
dsu.union(2, 3)
dsu.union(4, 5)
dsu.union(3, 5)
print(dsu.find(5))

 

1. 1
2. 2
3. 3
4. 4

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

(1) 정답: 4
✅ 유니온 파인드는 기본적으로 O(n) 복잡도를 가질 수 있지만, 경로 압축과 랭크 기반 합치기를 활용하면 O(α(n)) 수준으로 최적화됩니다.

(2) 정답: 4
✅ 경로 압축은 트리의 높이를 줄여서 Find 연산을 더욱 빠르게 만듭니다. 느려지지 않습니다.

(3) 정답: 1
✅ union(1,2) → union(2,3)을 수행한 후, find(3)을 호출하면 1이 출력됩니다.

(4) 정답: 1
✅ union(1,2) → union(2,3) → union(4,5) → union(3,5)을 수행한 후, find(5)을 호출하면 최상위 루트인 1이 출력됩니다.

---