Processing of Disjoint Sets using Union-Find Algorithms (9th weeks)
유니온파인드 알고리즘을 이용한 상호 배타적 집합의 처리
Contents
1️⃣ 유니온 파인드의 개요 (Overview of Union Find)
2️⃣ 연결 리스트 구현 (Implementation of Linked List)
3️⃣ 트리 구현 (Implementation of Tree)
4️⃣ 파이썬의 1차원 리스트 구현 (Implementation of 1-Dimensional List in Python)
Summary
유니온 파인드 개요 (Overview of Union FInd)
유니온 파인드는 집합 간의 연결과 대표 노드 탐색을 빠르게 수행하기 위한 알고리즘이다.
응용 분야: 네트워크 연결, 그룹화 문제, 상호 배타적 집합 관리 등에서 활용된다.
주요 연산(Basic Operation)
☑️ Make_Set(x) 원소 x가 독립된 집합을 생성하도록 한다.
☑️ Find_Set(x) 원소 x가 속한 집합의 대표 노드를 반환한다.
☑️ Union(x, y) 원소 x와 y가 속한 두 집합을 하나로 합친다.
구현 방식(Implementation)
☑️ 연결 리스트 (Linked List)
각 노드가 자신의 다음 노드를 가리키며 연결되는 방식이다.
Union 연산 시 대표 노드를 변경하는 과정에서 많은 연산이 필요할 수 있다.
☑️ 트리 (Tree)
트리 구조를 사용하여 각 집합의 대표 노드를 트리의 루트로 설정하는 방식이다.
경로 압축(Path Compression)과 랭크(Rank)를 사용해 탐색 및 결합을 최적화한다.
☑️ 1차원 리스트 (1-Dimensional Array)
인덱스를 사용하여 각 노드의 부모 정보를 저장한다.
빠르고 직관적인 접근 방식으로, 배열을 통해 간편하게 관리할 수 있다.
최적화 기법(Optimization Methods)
☑️경로 압축 (Path Compression): Find 연산 시 트리의 깊이를 줄여 탐색 속도를 개선한다.
☑️랭크 기반 유니온 (Union by Rank): 트리의 균형을 유지하여 트리의 높이를 최소화한다.
상호 배타적 집합이란? (What is Disjoin Sets)?
상호 배타적 집합(Disjoint Sets)은 서로 겹치는 원소가 없는 집합들을 의미한다. 즉, 각 원소는 하나의 집합에만 속할 수 있고, 다른 집합과는 공유되지 않는 구조이다.
유니온 파인드 알고리즘에서 이 개념이 중요한 이유는, 특정 원소가 어느 집합에 속하는지를 효율적으로 관리하고, 두 집합을 합칠 때 겹치지 않도록 하기 위함이다.
상호 배타적 집합의 예시 (Example of Disjoint Sets)
💡요약: 그래프의 연결 성분 (Connected Components of a Graph)은 서로 연결된 노드들의 집합이다. 각 성분은 독립적으로 존재하며, 다른 성분과 연결되어 있지 않다.
그래프에서 연결 성분은 서로 연결된 노드(점)들의 그룹을 의미하며, 이들 사이에는 경로가 존재한다. 연결되지 않은 다른 성분들과는 어떠한 연결도 이루어져 있지 않아서, 하나의 독립적인 서브그래프 (Subgraph)로 볼 수 있다.
이미지에는 총 세 개의 독립적인 그래프 성분이 회색 배경으로 나뉘어 표현되어 있다. 각 성분은 다음과 같은 형태를 띄고 있다.
첫 번째 성분: 상단에 하나의 중심 노드가 있고, 그 아래 두 개의 노드가 연결된 형태로 이루어져 있다.
두 번째 성분: 네 개의 노드가 있으며, 이 노드들은 다양한 방식으로 서로 연결되어 있다.
세 번째 성분: 두 개의 노드가 단순하게 한 줄로 연결된 형태를 보여주고 있다.
1️⃣ 유니온 파인드의 개요
(Overview of Union Find)
유니온 파인드의 개념 (Concept of Union Find)
💡요약: 유니온 파인드는 그래프에서 상호 배타적 집합 (Disjoint Sets)을 효율적으로 처리하기 위해 고안된 자료구조로, 기본 연산으로는 Make_Set (Create a Set), Find_Set (Find the Set), Union (Combine Sets)이 있으며, 이를 통해 연결된 그래프 구조를 형성한다.
유니온 파인드의 개념 (Concept of Union-Find):
유니온 파인드는 상호 배타적인 집합을 다루며, 각 집합의 연관성과 포함 관계를 효율적으로 관리할 수 있도록 돕는다.유니온 파인드의 기본적인 연산 (Basic Operations of Union-Find):
유니온 파인드 자료구조에서 사용하는 주요 연산은 다음과 같다.Make_Set(x): 원소 x로만 구성된 새로운 집합을 생성한다.
Find_Set(x): 원소 x가 포함된 집합을 찾는다.
Union(x, y): 원소 x가 포함된 집합과 y가 포함된 집합을 합친다.
유니온 파인드의 구현 방식(Implementation of Union-Find)
💡요약: 유니온 파인드의 대표적인 3가지 구현 방식으로는 연결 리스트 (Linked List), 트리 (Tree), 그리고 1차원 리스트(배열) (1D Array)가 있다. 이 중에서 대표 노드 (Representative Node)를 이용해서 각 집합을 구분하는데, 대표 노드는 해당 집합의 주요 원소로, 각 원소가 어느 집합에 속하는지를 나타내는 기준이 된다. 각 구현 방식은 대표 노드를 찾거나 지정하는 방식이 다르다.
☑️ 연결 리스트 구현 (Linked List Implementation):
포인터를 이용하여 대표 노드를 지정한다. 각 원소가 리스트 형태로 연결되어 있으며, 리스트의 첫 번째 원소가 대표 노드가 된다.
☑️ 트리 구현 (Tree Implementation):
트리 구조를 활용하여 각 집합의 대표 노드를 찾아간다. 트리의 루트 노드가 대표 노드가 되며, 효율적인 연산을 위해 경로 압축(path compression)과 같은 기법을 사용한다.
☑️ 1차원 리스트(배열) 구현 (1D Array Implementation):
각 원소가 리스트의 값으로 대표 노드를 가리킨다. 배열의 인덱스를 원소로 보고, 그 인덱스에 해당하는 값이 해당 집합의 대표 노드이다.
2️⃣ 연결 리스트 구현
(Implementation of Linked List)
유니온 파인드의 구현 방식 #1 - 연결 리스트의 노드 구조 (Implementation of Union-Find 1# - Node Structure in a Linked List)
💡요약: 연결 리스트는 각 노드 (Node)가 서로 연결되어 있는 자료구조로, 각 노드는 대표 노드 포인터 (Pointer to Representative Node), 필드 값 (Field Value), 다음 노드 포인터 (Pointer to Next Node)로 구성된다. 이를 통해 각 노드는 자신이 속한 집합의 대표 노드를 가리키며, 리스트 형태로 연결되어 있다.
대표 노드 포인터 (Pointer to the Representative Node):
각 노드에는 해당 노드가 속한 집합의 대표 노드를 가리키는 포인터가 있다. 예를 들어, 노드 b는 노드 a를 대표 노드로 가리키고 있다.필드 값 (Field Value):
노드는 데이터를 저장하는 필드를 가지고 있다. 여기서는 각 노드가 a와 b로 표현되어 있다.다음 노드 포인터 (Pointer to the Next Node):
각 노드는 리스트 내에서 다음 노드를 가리키는 포인터를 포함하고 있다. 이를 통해 리스트가 연결된 구조를 유지할 수 있게된다.
연결리스트에서 사용되는 유니온 파인드의 기본적인 연산 (Basic Operations of Union Find from Linked List): Make_Set(x) & Find_Set(x)
💡요약: Make_Set(x)는 새로운 집합을 생성하고, Find_Set(x)는 해당 집합의 대표 노드 (Representative Node)를 반환하는 역할을 한다.
Make_Set(x)의 구현 (Implementation of Make_Set(x)):
Make_Set(x) 연산은 원소 x로만 구성된 새로운 집합을 생성한다. 이는 x를 하나의 독립적인 집합으로 만들어, 다른 집합과 분리된 상태로 유지하게 한다.
예시에서 x는 하나의 노드로서 자신을 대표하고 있다. 이때, x는 집합의 꼬리(tail)로도 표시된다.
Find_Set(x)의 구현 (Implementation of Find_Set(x)):
Find_Set(x) 연산은 주어진 노드 x가 속한 집합의 대표 노드를 반환한다. 이 연산을 통해 x가 어느 집합에 속해 있는지를 알 수 있다.
이 예시에서는 x가 이미 대표 노드이므로, Find_Set(x) 연산의 결과는 x자신이 된다.
💡예시
Make_Set(5)를 수행하면
{5}라는 집합이 생성되고,5가 이 집합의 대표 노드이자 꼬리(tail)가 된다.Make_Set(5)를 먼저 수행한 후 Find_Set(5)를 실행하면,
5가 집합의 유일한 원소이므로5가 대표 노드로 반환되게 된다.
연결리스트에서 사용되는 유니온 파인드의 기본적인 연산 (Basic Operations of Union Find from Linked List): Union(x, y)
💡요약: Union 연산은 두 개의 집합을 하나로 합치는 과정으로, 이를 통해 상호 배타적 집합을 통합할 수 있게 하여 하나의 대표 노드를 공하는 집합으로 만든다.
x, y의 대표 노드 찾기 (Finding Representative Nodes of x and y):
- 첫 번째 단계에서는 Find_Set(x)와 Find_Set(y)를 수행하여 각각 x와 y의 대표 노드 (Representative Node)를 찾는다. 이는 각각의 집합이 시작되는 노드를 의미한다.
tail 노드 변경 (Changing the Tail Node):
- 두 번째 단계에서는 부집합 (Smaller Set)의 대표 노드를 주집합 (Larger Set)의 tail 노드 (Tail Node)로 설정하여 연결한다. 이는 두 집합을 하나로 합치기 위한 준비 과정이다.
대표 노드 변경 (Changing the Representative Node):
- 마지막 단계에서는 부집합의 모든 원소들이 주집합의 대표 노드를 가리키도록 대표 노드를 변경한다. 이를 통해 두 집합이 하나의 집합으로 합쳐지며, 모든 원소는 주집합의 대표 노드를 공유하게 된다.
💡예시: 두 개의 집합 A와 B가 있다고 가정해 보자
집합 A: {1, 2, 3} (대표 노드: 1)
집합 B: {4, 5} (대표 노드: 4)
여기서 Union(1, 4)를 수행한다고 가정하면 다음과 같은 단계가 진행된다.
대표 노드 찾기 (Find_Set): 각각의 대표 노드인 1과 4를 찾는다.
tail 노드 연결: 두 집합의 크기를 비교하여 작은 집합의 대표 노드를 큰 집합의 tail에 연결한다. 여기서 B가 더 작기 때문에, B의 대표 노드 4를 A의 tail (3)에 연결한다.
대표 노드 설정: B의 모든 원소가 A의 대표 노드인 1을 가리키도록 변경한다.
결과적으로, A와 B는 {1, 2, 3, 4, 5}로 합쳐지며, 모든 원소가 대표 노드 1을 공유하게 된다.
Union(x, y) 추가설명: 두 개의 집합 (Sets)을 하나로 합치는 과정 (Union Process)
💡요약: 두 집합을 부집합 (Smaller Set)을 주집합 (Larger Set)으로 나누어, 더 작은 부집합을 큰 주집합에 연결하는 방식으로 합치게 된다.
☑️부집합 (Subordinate Set):
- 부집합은 노드 a, b, c로 구성되어 있으며, 마지막 노드 c가 tail 노드 (Tail Node)로 표시된다. 이 집합은 주집합에 합쳐질 예정이다.
☑️ 주집합 (Main Set):
- 주집합은 노드 d, e, f, g, h로 구성되어 있으며, 마지막 노드 h가 tail 노드로 표시된다. 이 주집합에 부집합을 연결함으로써 전체 집합이 하나로 합쳐지게 된다.
☑️ 합치는 과정 (Union Process):
먼저, 부집합의 tail 노드인 c를 주집합의 tail 노드인 h에 연결합니다.
그 결과, 부집합의 모든 원소는 주집합의 대표 노드 (Representative Node)인 d를 공유하게 된다. 이로써 두 집합이 하나의 큰 집합으로 합쳐지게 되었다.
Union(x, y) 추가설명: 대표 노드 (Representative Node)와 tail 포인터 (Tail Pointer)를 변경하는 과정
💡요약: 중요한 점은 포인터 갱신 작업을 최소화하기 위해 큰 집합을 주집합으로, 작은 집합을 부집합으로 삼아 합치는 것이다.
☑️대표 노드를 변경 (Change Representative Node):
- 두 집합이 합쳐질 때, 작은 집합의 모든 노드가 큰 집합의 대표 노드를 가리키도록 변경한다. 이렇게 하면 모든 노드가 동일한 대표 노드를 가지게 되어 하나의 집합으로 인식된다.
☑️ tail 포인터 변경 (Change Tail Pointer):
- 큰 집합의 마지막 노드(tail)를 작은 집합의 첫 번째 노드와 연결하여 두 집합을 하나의 연속된 리스트로 만든다. 이 과정에서 작은 집합의 tail 포인터가 전체 합쳐진 집합의 마지막 노드를 가리키도록 설정된다.
☑️ 최적화 포인트 (Key Point):
- 대표 노드를 가리키는 포인터를 갱신하는 작업을 최소화하기 위해, 항상 더 큰 집합을 주집합으로 삼고 작은 집합을 부집합으로 설정하여 합치게 된다. 이렇게 하면 포인터 변경 횟수가 줄어들어 효율성이 높아진다.
각 연산의 수행 시간 (Execution Time of Operations in Linked List Union-Find)
💡요약: Make_Set(x)와 Find_Set(x)는 각각 O(1)의 상수 시간 (Constant Time)이 소요되며, Union(x, y)는 포인터 갱신 작업으로 인해 O(n \log n)의 수행 시간이 걸린다. 유니온 파인드 자료구조가 왜 집합 연산을 빠르고 효율적으로 처리할 수 있는 이유를 소개한다.
Make_Set(x): O(1)- 새로운 집합을 만드는 Make_Set(x) 연산은 상수 시간 (Constant Time), 즉 O(1)의 시간이 소요된다. 이는 항상 일정한 시간 안에 수행다.
Find_Set(x): O(1)- 특정 원소가 속한 집합의 대표 노드를 찾는 Find_Set(x) 연산 역시 상수 시간 O(1)이 걸린다.
Union(x, y): 대표 노드를 갱신하는 작업이 전체 시간 결정
두 집합을 합치는 Union(x, y) 연산에서는 대표 노드를 갱신해야 하는 작업이 포함되며, 이는 전체 수행 시간에 영향을 미치게 된다. 특히, 매번 작은 집합이 큰 집합에 합쳐지면서 대표 노드를 가리키는 포인터 갱신이 최소화된다.
작은 집합이 합쳐지면서 집합의 크기는 1 → 2 → 2² → 2³ → … 식으로 늘어나게 된다. 이 과정에서 최대 갱신 횟수는 log_2 n 만큼 반복되며, 모든 원소에 대해 계산하면 포인터 갱신 계산으로 인해 O(n log n) 이 된다.
각 연산들의 수행 시간 예
(Example of Execution Time of Union-Find)
💡요약: Make_Set, Union, Find_Set 연산들이 주어진 입력 크기에서 얼마나 빠르게 동작하는지에 대한 시간 복잡도를 설명하고 있다.
총 수행 시간 계산
- 유니온 파인드의 연산이 m번 일어나고, 새로운 집합을 만드는 Make_Set이 n번 발생할 때, 전체 수행 시간은 O ( m + n log n)이다.
각 연산의 시간 복잡도
Make_Set과 Find_Set은 각각 최대 O(m)시간이 소요된다.
Union 연산은 O (n log2 n) 시간이 걸린다.
💡예시: 노드들이 서로 다른 집합에 포함되어 있다고 가정하고, 다음과 같은 연산을 수행한다고 가정 하자
Make_Set 연산:
노드 1, 2, 3, 4를 각각 독립된 집합으로 초기화한다.
이 경우, Make_Set은 각 노드마다 𝑂(1)의 시간이 걸리므로 4개의 노드를 초기화하는 데 𝑂(4) 시간이 소요된다.
Union 연산:
노드 1과 노드 2를 Union 연산으로 하나의 집합으로 합친다.
이어서 노드 3과 노드 4를 Union으로 합친다.
마지막으로 노드 1과 노드 3의 집합을 합친다.
각 Union 연산은 연결 리스트의 끝에 노드를 추가하는 방식으로, 최악의 경우 𝑂(log n)의 시간이 걸리므로 총 𝑂(3 log n) 시간이 소요되었다.
Find_Set 연산:
최종적으로 노드 4가 속한 집합의 대표 노드를 찾는다. Find_Set은 대표 노드를 찾을 때 연결 리스트를 따라가야 하므로, 연결 리스트의 길이에 비례하여 시간이 걸립니다. 최악의 경우 𝑂(log n)의 시간이 필요하다.
이 예제에서는 Make_Set 연산이 𝑂(4)이고, Union과 Find_Set 연산이 합쳐서 𝑂(3 log n) 시간이 걸린다. 따라서, 전체 수행 시간은 유니온 파인드의 시간 복잡도인 𝑂(m + n log n)에 근사하다.
3️⃣ 트리 구현 (Implementation of Tree)
유니온 파인드의 구현 방식 #2 - 트리 구조 (Implementation of Union-Find 2# - Tree Structure)
💡요약: 유니온 파인드에서 트리 구조는 같은 집합의 원소들을 하나의 대표 원소로 관리하기 위해 사용된다. 각 원소는 부모 노드를 가리키며, 최상단 루트 노드가 전체 집합의 대표가 된다.
☑️ 트리 구조와 대표 원소
- 모든 원소는 하나의 트리로 연결되며, 트리의 최상단에 있는 루트 노드가 집합의 대표 원소가 된다. 예를 들어, 트리의 루트 노드인 c가 전체 집합의 대표 원소다 된다.
☑️부모 노드를 가리킴
- 일반적인 트리 구조와 다르게, 유니온 파인드 트리에서는 자식 노드가 자신의 부모 노드를 가리킨다. 예를 들어, a는 b를, b는 c를 가리키고 있다.
☑️ 대표 원소로 집합 관리
- 트리의 루트를 통해 해당 집합의 모든 원소가 어떤 집합에 속해 있는지 쉽게 확인할 수 있다.
트리구조에서 사용되는 유니온 파인드의 기본적인 연산 (Basic Operations of Union Find from Tree Structure):
Make_Set(x)
💡요약: Make_Set(x)는 원소 x를 유일한 원소로 가지는 집합을 생성하고, x의 부모 포인터를 자기 자신으로 설정하여 루트와 대표 원소가 되도록 한다.
원소 x로 집합 생성
- Make_Set(x)는 원소 x를 유일한 원소로 가지는 집합을 생성한다. 이 집합은 하나의 트리로 구성되며, 루트 노드는 x가 된다.
부모 포인터가 자기 자신을 가리킴
- 초기화된 노드 x의 부모 포인터 (Parent Pointer)는 자기 자신을 가리키도록 설정된다. 이는 트리에서 x가 그 자체로 독립적이라는 것을 의미한다.
트리의 루트가 대표 원소
- 트리의 루트인 x는 집합의 대표 원소 (Representative Element) 역할을 한다. x가 포함된 집합의 대표가 x 자신이라는 뜻이다.
트리구조에서 사용되는 유니온 파인드의 기본적인 연산 (Basic Operations of Union Find from Tree Structure):
Find_Set(x)
💡요약: Find_Set(x) 연산은 노드 x에서 시작해 부모 노드를 따라가며 루트 노드에 도달할 때까지 이동하며, 루트 노드를 대표 원소로 반환한다.
☑️부모 노드를 따라가기
- Find_Set(x)는 원소 x의 부모 노드 (Parent Node)를 따라간다. 부모 노드의 포인터를 반복적으로 따라가면서 루트에 도달할 때까지 계속 이동한다.
☑️루트 노드까지 이동
- 부모 노드를 계속해서 따라가다 보면, 언젠가 자기 자신을 가리키는 노드(루트 노드)에 도달하게 된다. 이 루트 노드가 해당 집합의 대표 원소이다. 예를 들어, 노드 x에서 출발하여 e, h를 거쳐 대표 노드 c에 도달한다.
☑️ 대표 원소 반환
- 최종적으로 루트 노드에 도달하면 그 노드를 대표 원소로 반환한다. 루트 노드 c는 노드 x가 속한 집합의 대표 원소이다.
💡예제: 여러 팀이 하나의 리더 아래 그룹으로 묶여 있다고 가정해보자. x가 어떤 팀의 일원인지 알고 싶다면 x의 리더(대표 원소)를 찾아가면서 리더를 찾을 때까지 상위 계층을 따라가면 된다.
트리구조에서 사용되는 유니온 파인드의 기본적인 연산 (Basic Operations of Union Find from Tree Structure):
Union(x, y)
💡요약: Union(x, y) 연산은 두 개의 집합을 하나로 합쳐서 대표 노드를 공유하도록 만들어 구현한다. 이때, 한 집합의 대표 노드가 다른 집합의 대표 노드를 가리키게 하여 연결하는 방식이다.
두 집합 합치기
- 왼쪽에는 대표 노드가 c인 집합이 있고, 오른쪽에는 대표 노드가 e인 집합이 있다. 이 두 집합을 Union(x, y) 연산을 통해 하나로 합치려고 한다.
대표 노드 연결
- 두 집합을 하나로 합치기 위해 대표 노드 중 하나가 다른 집합의 대표 노드를 가리키도록 설정한다. 예시에서는 노드 e가 노드 c를 가리키도록 부모 포인터를 변경하여 하나의 트리로 연결한다.
합쳐진 결과
- 결과적으로, e를 포함한 오른쪽 집합이 c를 대표 노드로 가지는 왼쪽 집합에 연결되어 하나의 큰 집합이 된다. 이제 모든 노드는 루트 노드 c를 통해 같은 집합에 속하게 된다.
💡예제: 대규모 네트워크에서 연결 상태 확인을 빠르게 수행해야 할 때 특히 유용한 방법이 될 수 있다. 서버 A, B, C, D가 있다고 가정해보자
초기 상태: 각 서버는 독립적인 네트워크로 초기화된다.
Make_Set(A),Make_Set(B),Make_Set(C),Make_Set(D)
연결 추가: 네트워크 관리자가 서버 A와 B를 연결하면
Union(A, B)연산을 수행한다. 이제 A와 B는 하나의 네트워크로 간주된다.추가 연결: 서버 C와 D를 연결하려면
Union(C, D)를 수행한다. 이로써 C와 D는 하나의 네트워크에 속하게 된다.네트워크 통합: 나중에 A와 C가 연결되면
Union(A, C)를 통해 A, B, C, D가 하나의 네트워크로 합쳐진다.연결 여부 확인: 예를 들어, 서버 B와 D가 같은 네트워크에 속해 있는지 확인하려면 Find_Set(B)와 Find_Set(D)를 호출해 같은 대표 노드를 가지고 있는지 비교하면 된다.
트리구조에서 사용되는 유니온 파인드의 의사 코드 (Pseudocode for Tree Implementation of Union-Find)
💡요약: Make_Set(x)는 노드 x를 독립적인 집합으로 초기화하고, Union(x, y)는 두 집합을 하나로 합치며, Find_Set(x)는 노드 x의 대표 노드를 찾는다.
Make_Set(x)Make_Set(x) 연산은 새로운 집합을 만들기 위해, 노드 x를 유일한 원소로 가지는 집합으로 초기화한다.
x.parent ← x로 설정하여, 노드 x가 자기 자신을 부모로 가리키도록 한다. 즉, 노드 x는 자신의 대표 노드 (Representative Node)가 되는 것이다.
Union(x, y)Union(x, y) 연산은 두 집합을 하나로 합치는 기능을 수행한다.
Find_Set(y).parent ← Find_Set(x)를 통해, y가 속한 집합의 대표 노드가 x의 대표 노드를 가리키도록 연결된다. 이로써 두 집합은 하나로 합쳐진다.
Find_Set(x)Find_Set(x) 연산은 노드 x가 속한 집합의 대표 노드를 찾는 기능을 한다.
if (x = x.parent) return x: 만약 x가 자기 자신을 부모로 가리킨다면, x는 루트 노드이므로 x를 반환한다.
else return Find_Set(x.parent): 그렇지 않다면, x의 부모 노드로 이동하여 다시 Find_Set을 재귀적으로 호출하여 루트 노드에 도달할 때까지 반복한다.
💡예제: 파일 시스템 관리라는 상황을 예로 들어보자. 대형 파일 시스템에서 여러 디렉토리(폴더)들이 있고, 이들 사이에 병합 작업이 필요할 때가 있다. 예를 들어, 두 디렉토리를 하나로 합치거나 특정 파일이 어느 디렉토리에 속해 있는지 빠르게 찾아야 할 때가 있다. 유니온 파인드의 연산을 사용하면 이러한 파일 및 디렉토리 관계를 효율적으로 관리할 수 있게된다.
연산 적용
Make_Set(x): 새 디렉토리 또는 파일을 시스템에 추가할 때 Make_Set을 통해 각각 독립적인 디렉토리로 초기화한다.
- 예를 들어, 디렉토리 "Dir1"과 "Dir2"가 있다고 하면,
Make_Set(Dir1)과Make_Set(Dir2)를 호출하여 각 디렉토리가 독립적인 집합(루트)을 갖도록 설정한다.
- 예를 들어, 디렉토리 "Dir1"과 "Dir2"가 있다고 하면,
Union(x, y): 두 디렉토리를 하나로 병합할 때 사용한다.
예를 들어, "Dir1"과 "Dir2"를 병합하려면
Union(Dir1, Dir2)를 호출하여 하나의 루트를 공유하도록 만든다.이렇게 하면 "Dir1"과 "Dir2"가 하나의 디렉토리 구조로 연결되며, 하위 파일도 함께 포함된 집합으로 관리된다.
Find_Set(x): 특정 파일이나 디렉토리가 어떤 최상위 디렉토리에 속해 있는지 찾는 데 사용된다.
- 예를 들어, 파일 "file.txt"가 어느 디렉토리에 포함되어 있는지 알고 싶다면
Find_Set(file.txt)를 호출하여 "file.txt"의 최상위 디렉토리를 찾을 수 있다. 이를 통해 파일 위치를 빠르게 확인할 수 있게된다.
- 예를 들어, 파일 "file.txt"가 어느 디렉토리에 포함되어 있는지 알고 싶다면
구체적인 예제
디렉토리 초기화: 디렉토리 "A"와 "B"를 각각 독립 디렉토리로 초기화
Make_Set(A),Make_Set(B)
디렉토리 병합: "A"와 "B"를 하나의 구조로 병합한다.
Union(A, B): 이제 "B"가 "A"와 같은 상위 디렉토리를 공유하게 된다.
위치 확인: 파일 "file1"이 속한 최상위 디렉토리를 찾으려면
Find_Set(file1)을 호출하여 속한 디렉토리의 루트 디렉토리를 빠르게 파악할 수 있다.
트리구조의 유니온 파인드 연산에서 효율성을 높이는 2가지 방법
(2 Methods to Increase Efficiency in Union-Find Operations)
랭크를 이용한 유니온 (Union by Rank)
경로 압축 (Path Compression)
💡요약: 유니온 파인드에서 랭크와 경로 압축을 사용하면 트리의 높이가 줄어들어 탐색 연산의 속도를 향상시킬 수 있게 된다. 랭크가 낮은 트리를 높은 트리에 붙이고, 경로 압축을 통해 방문하는 노드를 루트에 바로 연결할 수 있다.
랭크를 이용한 유니온 (Union by Rank)
두 집합을 합칠 때, 랭크 (Rank), 즉 트리의 높이를 기준으로 작은 집합을 큰 집합에 붙인다.
이 방법을 사용하면 트리의 높이를 최소화하여 탐색 시간을 줄일 수 있다. 예를 들어, A라는 집합과 B라는 집합이 있을 때, A의 랭크가 더 높다면, B를 A에 합친다.
경로 압축 (Path Compression)
Find_Set 연산을 수행할 때, 모든 노드가 직접 루트 노드(Direct root node)를 가리키도록 부모 포인터를 변경하는 최적화 기법이다.
즉, 경로 압축은 한 번 루트를 찾는 과정에서 만난 모든 중간 노드들이 다음 탐색 시에는 바로 루트에 접근할 수 있도록 부모 포인터를 루트로 설정해 준다. 이렇게 하면 트리의 깊이가 줄어들어 이후의 탐색 속도가 빨라지게 된다.
예를 들어, 노드 x가 루트까지 가기 위해 여러 개의 부모 노드를 거쳐야 하는 상황에서 경로 압축을 적용하면, 한 번 루트를 찾고 나면 x와 그 중간의 모든 노드들이 루트를 직접 가리키게 된다. 이후로는 탐색할 때 루트에 바로 도달할 수 있어 탐색 시간이 크게 단축되는 것이다.
랭크 (Rank)
- 여기서 랭크는 각 노드에서 자신을 루트로 하는 서브트리의 높이를 의미한다. 랭크를 통해 트리의 균형을 유지할 수 있다.
💡예제: 학교의 학급을 예로 들어보면, 각 학급이 서로 다른 그룹으로 시작할 수 있다. 랭크를 이용한 유니온은 학생 수가 적은 학급을 큰 학급에 합치는 것과 비슷하며, 경로 압축은 학급장이 바뀌었을 때, 모든 학생이 새로운 학급장을 바로 알 수 있게 연결하는 것과 같다.
트리구조 - 랭크를 이용한 Union의 예 (Example of Union by Rank)
💡요약: 두 개의 집합을 합칠 때 트리의 높이 (Rank)를 기준으로 더 낮은 랭크의 트리를 더 높은 랭크의 트리에 붙여서 트리의 높이가 불필요하게 커지지 않도록 한다.
합치고자 하는 두 집합
왼쪽 트리는 c를 루트로 하는 집합이고, c의 랭크는 2이다. 오른쪽 트리는 e를 루트로 하는 집합이고, e의 랭크는 1이다.
각 노드의 랭크는 파란색 상자 안에 표시되어 있으며, 각 노드에서 루트 노드까지의 높이를 나타낸다.
랭크 비교 후 트리 합치기
- 두 트리를 합칠 때, 랭크가 낮은 쪽의 루트 노드 e를 랭크가 높은 쪽의 루트 노드 c에 붙인다. 이는 트리의 높이를 최소화하기 위한 방법이다.
합쳐진 결과
- e가 c를 가리키도록 연결되며, 이제 모든 노드가 루트 노드 c를 공유하는 하나의 트리로 합쳐지게 된다. 이 결과, 트리의 높이가 불필요하게 증가하지 않으며 효율성을 유지할 수 있다.
💡예제: 학교의 두 동아리가 하나로 합쳐질 때, 인원이 많은 동아리의 리더가 전체 리더가 되는 상황을 생각해볼 수 있다. 인원이 적은 동아리의 리더와 멤버들은 큰 동아리의 리더를 따르도록 함으로써, 관리 구조가 복잡해지지 않게 한다.
랭크를 이용한 Union에서 랭크가 증가하는 예
(Example of Rank Increase in Union by Rank)
💡요약: 랭크를 이용한 Union에서 두 집합의 랭크가 같을 때 합치면 하나의 랭크가 증가하게 된다. 이는 트리의 높이를 최소화하면서도 균형을 유지하는 방식이다.
합치고자 하는 두 집합
왼쪽에는 대표 노드가 c이고 랭크가 2인 집합이 있으며, 오른쪽에는 대표 노드가 e이고 랭크가 2인 집합이 있다.
두 집합의 랭크가 같기 때문에, 두 집합을 합칠 때 한쪽의 랭크가 증가하게 된다.
동일한 랭크의 두 집합을 합치기
- 두 집합의 대표 노드가 모두 랭크 2를 가지고 있기 때문에, 하나의 대표 노드를 다른 대표 노드에 붙이는 대신에 한쪽의 랭크를 3으로 증가시키고 나머지 대표 노드가 이 새로운 대표 노드를 가리키도록 한다.
합쳐진 결과
- e가 c를 가리키도록 변경되며, 이로 인해 c의 랭크가 3으로 증가하게 된다. 합쳐진 트리의 루트는 c가 되고, 이제 트리 전체는 하나의 집합으로 관리된다.
💡예제: 두 그룹이 통합될 때, 두 그룹의 리더의 지위가 같다면, 하나의 리더가 전체 리더가 되고 그 리더의 지위(랭크)가 증가하는 상황을 생각할 수 있다.
랭크를 이용한 Union과 Make_Set의 의사 코드
(Pseudocode for Union by Rank and Make_Set)
💡요약: 랭크를 이용한 Union은 두 집합의 랭크를 비교하여 랭크가 낮은 트리를 높은 트리에 붙여 트리의 깊이를 최소화하는 방식이다. 랭크가 같을 경우, 합쳐진 트리의 랭크가 하나 증가한다.
Make_Set(x)Make_Set(x) 연산은 새로운 집합을 만든다.
x.parent ← x는 노드 x가 자기 자신을 부모로 가리키게 하고, x.rank ← 0은 x의 랭크를 0으로 초기화한다.
Union(x, y)Union(x, y) 연산은 두 집합을 합칩니다.
x' ← Find_Set(x)와 y' ← Find_Set(y)를 통해 각 집합의 대표 노드를 찾는다.
if (x'.rank > y'.rank): x의 랭크가 y의 랭크보다 크다면, y의 부모를 x로 설정한다. (y’.parent ← x').
else: 반대의 경우, x의 부모를 y로 설정하고, 만약 두 랭크가 같다면, y의 랭크를 1 증가시킨다 (y’.rank ← y’.rank + 1).
💡예제: 두 그룹이 통합될 때, 두 그룹의 리더의 지위가 같다면, 하나의 리더가 전체 리더가 되고 그 리더의 지위(랭크)가 증가하는 상황을 생각할 수 있다.
트리구조 - 경로 압축의 예 (Example of Path Compression)
💡요약: 경로 압축 (Path Compression)은 유니온 파인드에서 Find_Set연산을 수행할 때, 탐색 경로에 있는 모든 노드가 직접 루트 노드 (Root Node)를 가리키도록 하여 트리의 깊이를 줄이는 최적화 기법이다.
초기 상태
- 왼쪽 그림에서, g 노드가 루트 c까지 가기 위해 e와 h를 거쳐야 한다. 현재 g와 루트 c 사이에 여러 중간 노드가 있다.
Find_Set(g) 수행
- Find_Set(g)를 실행하여 g가 속한 집합의 대표 원소(루트)를 찾는다. 이 과정에서 g에서 e, h, 그리고 최종적으로 루트 c까지 도달한다.
경로 압축 후 결과
- 경로 압축을 통해 g와 경로에 있는 중간 노드들이 모두 루트 c를 직접 가리키도록 변경되었다. 오른쪽 그림처럼, 이제 g, e, h는 모두 c를 직접 가리키게 되어 트리의 높이가 줄어들고, 다음 탐색이 더 빨라진다.
💡예제: 학교에서 학생들이 교장 선생님을 만나려면, 여러 단계를 거쳐야 하는 상황을 생각할 수 있다. 경로 압축을 적용하면, 한 번 만난 후 모든 학생이 바로 교장 선생님을 찾아갈 수 있도록 경로가 단순화된다.
트리구조 - 경로 압축을 이용한 Find_Set (Find_Set with Path Compression)
💡요약: 경로 압축을 적용한 Find_Set은 노드가 속한 트리의 루트를 찾을 때, 경로에 있는 모든 노드가 직접 루트를 가리키도록 부모를 설정하여 탐색 효율을 높인다.
Find_Set(x):
Find_Set(x)는 노드 x가 속한 트리의 루트 노드 (Root Node)를 찾는다.
if (x.parent ≠ x): 만약 x가 자기 자신을 부모로 가리키지 않는다면, 즉, x가 루트 노드가 아니라면, 경로 압축을 적용한다.
x.parent ← Find_Set(x.parent): 경로 압축을 통해 x의 부모를 재귀 호출로 찾은 루트 노드로 설정한다. 이를 통해 x와 그 상위 노드들이 루트를 직접 가리키게 된다.
마지막으로 return x.parent를 통해 최종 루트를 반환한다.
경로 압축의 역할
- 경로 압축을 통해 노드 x와 그 상위 노드들이 모두 루트 노드를 가리키게 되므로, 이후의 탐색에서 트리의 깊이가 감소하여 탐색 속도가 빨라지게 된다.
💡예제: 회사에서 직원들이 상위 관리자(루트)를 찾는 과정을 생각할 수 있다. 경로 압축을 적용하면, 한 번 경로를 찾은 이후로 모든 직원이 바로 상위 관리자에게 연결되어, 다음에 상위를 찾을 때 더 빠르게 도달할 수 있다.
❓수행 시간 (Time Complexity)
: 랭크 (Rank)와 경로 압축 (Path Compression)을 사용하여 유니온 파인드를 최적화했을 때, 연산이 얼마나 효율적으로 수행될까?❓
💡요약: 랭크와 경로 압축을 사용하면 유니온 파인드의 수행 시간은 거의 선형적(Almost Linear)이 다. 이는 **log ∗ n**이 매우 느리게 증가하기 때문에, 많은 연산을 수행해도 시간 복잡도가 효과적으로 관리됨을 의미한다.
수행 시간
- 랭크와 경로 압축을 사용한 유니온 파인드에서는 m번의
Make_Set,Union,Find_Set연산을 수행할 때, 각 연산의 평균적인 시간 복잡도가 O(m⋅log∗n)이 된다. 여기서 n은 집합의 개수를 나타낸다.
log* n
**log*n**은 매우 느리게 증가하는 함수로, n이 엄청나게 큰 값이더라도 매우 작은 수로 제한된다. 이는 사실상 상수 시간 (Almost Constant Time)과 비슷한 수준의 효율성을 보여준다.
**log* n**는 여러 번 로그를 반복하여 계산하며, n이 작을수록 빠르게 1 이하가 되기 때문에 실용적인 문제에서 매우 효율적이다.
"사실상 선형시간임"
- O(m ⋅ log* n)는 m번의 연산이 거의 선형 시간에 가까운 속도로 수행된다는 의미로, 유니온 파인드가 매우 효율적임을 강조할수 있다.
💡예제: 학교에서 수천 명의 학생이 소속된 동아리 활동을 관리할 때, 랭크와 경로 압축을 사용하면 각 학생의 대표(리더)를 빠르게 찾을 수 있다. 학생이 많아도, 탐색 과정에서 경로를 최적화하여 매우 효율적으로 리더를 찾는 것과 같은 원리이다.
❓연결리스트와 트리구조의 수행 시간 (Time Complexity)비교
연결 리스트의 Make_Set과 Find_Set은 상수 시간에 동작할 수 있지만, 트리 구조를 관리하는 유니온 파인드만큼 효율적으로 많은 집합을 병합하거나 찾는 데 최적화되지 않는다.
유니온 파인드의 O(m⋅log∗n) 수행 시간은 더 큰 데이터셋을 다루면서도 거의 선형에 가깝게 빠르게 연산할 수 있어, 많은 집합을 관리하는 문제에서는 연결 리스트보다 훨씬 효율적이다.
따라서, 유니온 파인드가 연결 리스트보다 훨씬 더 큰 규모의 데이터 관리에서 효율적이라고 할 수 있다.
4️⃣ 파이썬의 1차원 리스트 구현
(Implementation of 1-Dimensional List in Python)
💡요약: 1차원 리스트를 이용한 초기화는 각 노드를 처음에 자기 자신이 대표가 되도록 설정하여, 초기 상태에서의 독립된 집합을 표현한다. 리스트는 각 노드의 대표를 나타내며, 인덱스 값으로 초기화된다. 1차원 리스트를 사용하여 초기 상태에서 각 노드를 대표 노드 (Representative Node)로 설정하는 방법을 더 자세히 알아보자
각 노드는 처음에 연결되지 않음
- 초기 상태에서는 모든 노드가 서로 연결되어 있지 않기 때문에, 각 노드는 자기 자신이 대표 노드가 된다.
리스트의 초기화
리스트의 각 위치는 해당 노드의 대표 노드를 나타낸다. 예를 들어, 노드 1의 대표는 1, 노드 2의 대표는 2가 된다.
따라서, 리스트는 각 노드의 인덱스 값 (Index Value)으로 초기화된다.
💡예제: 예를 들어, 학생 번호가 1번부터 6번까지 있는 그룹을 만든다고 가정합니다. 각 학생은 처음에는 자신이 속한 그룹의 대표가 된다. 따라서 1번 학생의 대표는 1이고 2번 학생의 대표는 2가 되는 식이다.
1차원 리스트를 이용한 Union 연산
(Union Operation Using a 1-Dimensional List)
💡요약: Union 연산을 통해 두 노드를 같은 집합으로 연결한다. 각 노드의 대표 노드를 찾아 리스트에서 업데이트하며, 이를 통해 효율적으로 집합을 관리할 수 있다.
Union 연산의 단계
union(1, 4): 첫 번째로, 노드 1과 4를 연결한다. 여기서 각 노드의 대표 노드를 찾고, 1과 4를 연결한다.
union(5, 6): 두 번째로, 노드 5와 6을 연결한다. 마찬가지로 각 노드의 대표 노드를 찾아 연결한다.
union(4, 6): 세 번째로, 4와 6을 연결하려고 한다. 이때, 4와 6의 대표 노드를 찾은 후, 대표 노드 1과 5를 연결하여 하나의 집합으로 만든다.
유니온 파인드 리스트 변화
- 각 연산 후에 리스트에서 대표 노드가 갱신된다. 예를 들어, union(4, 6)을 수행한 후에는 1, 4, 5, 6이 동일한 대표 노드(1)를 가리키게 된다.
💡예제: 동아리 학생들이 각자 다른 팀으로 나뉘어 있다가, 두 팀이 합쳐져 하나의 그룹이 될 때 각 팀의 대표가 모여 새 대표를 정하는 과정과 유사하다.
1차원 리스트 - Find 연산과 경로 압축을 이용하여 대표 노드 찾기 (Find Representative Node using Find Operation & Path Compression)
💡요약: Find 연산은 노드가 속한 집합의 대표 노드를 찾고, 경로 압축을 통해 탐색 속도를 향상시킨다. 경로 압축을 통해 각 노드가 바로 대표 노드를 가리키도록 만들어, 이후 연산에서 더 빠르게 접근할 수 있게 한다.
Find 연산의 작동 원리
① 대상 노드 리스트에 index값과 value값이 동일한지 확인
Find 연산은 현재 노드의 인덱스와 값이 같은지 확인한다. 이는 노드가 자기 자신을 가리키는지 확인하는 과정이다.② 동일하지 않으면 value값이 가리키는 index 위치로 이동
만약 인덱스와 값이 다르다면, 값이 가리키는 인덱스 위치로 이동하여 다시 확인한다.③ 이동 위치의 index값과 value값이 같을 때까지 반복
인덱스와 값이 같을 때까지 이 과정을 반복한다. 이 과정은 재귀 함수로 구현할 수 있다.④ 대표 노드에 도달하면 경로 상의 모든 노드를 대표 노드로 변경
대표 노드를 찾으면, 탐색 경로에 있던 모든 노드의 값을 대표 노드로 변경하여 경로 압축을 수행하게 된다.
💡예제: 학생들이 각자 소속된 동아리의 대표를 찾는 과정이라고 생각할 수 있다. 학생들이 대표를 찾기 위해 계속해서 상위로 올라가지만, 한 번 대표를 찾으면 이후에는 각자 바로 대표를 가리키도록 하여 다음 탐색이 더 빨라지게 된다.
1차원 리스트 - Find 연산과 경로 압축의 동작방식 (How Find Operation & Path Compression works)
Find(6) 연산의 시작: 노드 6의 대표 노드를 찾기 위해 A[6]을 확인합니다.
① A[6] != 6이므로 인덱스와 값이 같지 않다. 따라서, 값이 가리키는 인덱스로 이동하여 A[5]를 확인한.
② A[5] != 5이므로 다시 이동하여 A[1]을 확인한다.
③ A[1] == 1이므로 인덱스와 값이 같아, 노드 1이 대표 노드임을 확인할 수 있다.
경로 압축: 대표 노드(1)를 찾은 후, 탐색 경로에 있던 모든 노드의 값을 대표 노드의 값으로 변경하여 다음 탐색 시 더 빠르게 접근할 수 있게 한다.
💡예제: 학생이 소속된 동아리 대표를 찾는 상황을 생각해볼 수 있다. 처음엔 누가 대표인지 모르기 때문에 여러 사람에게 물어봐야 하지만, 대표를 알게 된 후에는 다른 사람들도 바로 대표를 가리키도록 하여, 다음에 또 물어볼 때 더 빠르게 대표를 찾을 수 있게 된다.
1차원리스트 - Find 연산과 경로 압축을 통해 효율적으로 데이터를 관리하는 방법 (Increase Data management efficiency using Find Operation & Path Compression)
💡요약: Find 연산은 특정 노드의 대표 노드를 찾아주는 연산인데, 경로 압축을 사용하면 이후의 Find 연산 속도가 빨라지게 된다.
연산의 복잡도 감소: 경로 압축을 통해 모든 노드가 직접 대표 노드와 연결되므로 시간 복잡도가 줄어들게 된다.
대표 노드와 바로 연결: Find 연산을 실행할 때 경로에 있는 노드들이 대표 노드와 바로 연결되도록 업데이트된다.
연산 속도 향상: 경로 압축이 완료된 후에는 Find 연산이 O(1)의 시간 복잡도로 매우 빠르게 수행될수 있다.
💡예제:
- 첫 번째 행은 초기 상태로 각 노드가 자기 자신을 가리키고 있다.
두 번째 행은 Find 연산을 수행하면서 경로를 압축하는 과정이다.
세 번째 행은 모든 노드가 대표 노드 1을 가리키게 되어, 이후 Find 연산이 매우 빨라지는 상태가 된다.
1차원 리스트를 사용하여 집합을 표현하기
💡요약: 아래 알고리즘은 각 원소가 포함된 집합을 간단히 표현하고 관리하기 위한 방법을 제공하고 있다. 초기에 {0}, {1}, {2}, ... {n}과 같은 집합이 각각 독립적으로 존재하며, 이들을 합집합 연산과 같은 집합에 포함 여부 확인 연산을 통해 관리한다.
합집합 연산 (Union Operation): 두 원소가 속한 집합을 하나로 합친다. 입력 형식은
0 a b로, 원소a와b가 속한 집합을 합친다.같은 집합에 포함 여부 확인 연산 (Find Operation): 두 원소가 같은 집합에 포함되어 있는지 확인한다. 입력 형식은
1 a b로, 원소a와b가 같은 집합에 속하는지 확인한다.
💡예제:초기 집합이 {0}, {1}, {2}, {3}일 때:
0 1 2연산을 수행하면{1, 2}가 같은 집합이 된다.1 1 2연산을 수행하면1과2가 같은 집합에 속해 있다는 결과를 확인할 수 있다.
1차원 리스트를 사용하여 집합을 표현하기- 출력(Output)
유니온-파인드 (Union-Find) 알고리즘을 통해 집합을 표현하고, 집합 간의 연산을 효율적으로 처리하는 방식이다.
입력 형식:
첫 번째 줄은
n(원소 개수)와m(질의 개수)을 나타낸다.이후 각 줄에
0 a b또는1 a b의 형식으로 연산이 주어진다.0 a b: 원소a와b가 속한 집합을 합집합이다.1 a b: 원소a와b가 같은 집합에 포함되어 있는지 확인한다.
출력 형식:
1로 시작하는 연산의 결과를 YES 또는 NO로 출력한다.YES는
a와b가 같은 집합에 속해 있음을 의미하고, NO는 다른 집합에 속해 있음을 나타낸다.
예제 설명
예제 입력:
7 8: 원소 7개와 8개의 연산이 주어진다.0 1 3: 원소1과3을 같은 집합으로 만든다.1 1 7: 원소1과7이 같은 집합인지 확인 -> NO0 7 6: 원소7과6을 같은 집합으로 만든다.1 7 1: 원소7과1이 같은 집합인지 확인 -> NO0 3 7: 원소3과7을 같은 집합으로 만든다.1 1 6: 원소1과6이 같은 집합인지 확인 -> YES
예제 출력:
- 각
1로 시작하는 연산에 대해NO,NO,YES가 순서대로 출력되었다.
- 각
집합 표현하기 - 문제 분석하기 #1
이미지에는 다양한 Union과 Find 연산이 나와 있다. 각 연산을 수행할 때마다 집합 상태가 어떻게 변하는지 시각적으로 보여주며, 결과로 YES 또는 NO가 출력된다.
union(1, 3)을 수행한 후에는 1과 3이 같은 집합에 속하게 된다.find(1)과find(7)을 비교해 NO가 출력된다. 이는 1과 7이 다른 집합에 있음을 나타낸다.union(7, 6)을 수행하여 7과 6을 같은 집합으로 만들었다.이후
find(7)과find(1)을 비교해 NO가 출력되었다.
union(3, 7)을 수행하여 3과 7을 연결한 후, 대표 노드를 갱신한다.union(4, 2)을 수행하여 4와 2를 같은 집합으로 만든다.union(1, 1)연산은 이미 같은 집합에 속한 원소이므로 불필요한 연산이다.find(1) == find(1)연산을 통해 1과 1이 같은 집합에 속해 있는지 확인하고, 결과로 YES가 출력된다.
집합 표현하기 - 의사 코드 작성(Pseudocode)
Find 연산: 특정 원소가 속한 집합의 대표 노드를 찾는다.
만약
a가 대표 노드라면 그대로 반환하고, 그렇지 않다면a의 대표 노드를 재귀적으로 찾아 반환한다.경로 압축을 통해
a의 대표 노드 값을 갱신하여 추후 찾기 연산 속도를 향상시킨다.
Union 연산: 두 원소가 속한 집합을 하나로 합친다.
a와b의 대표 노드를 찾아, 하나의 대표 노드로 연결한다.
CheckSame 함수: 두 원소가 같은 집합에 속해 있는지 확인하는 함수이다.
a와b의 대표 노드를 찾아 비교하고, 같다면 true, 그렇지 않다면 false를 반환한다.
초기화 과정:
- 각 원소가 독립된 집합으로 초기화되어 자기 자신을 대표 노드로 갖도록 설정한다.
입력과 반복문 처리:
N번 반복하여 각 노드의 대표 노드를 자기 자신으로 초기화한다.M번 반복하여 입력된 질의를 처리한다. 질의가0이면 Union 연산을, 그렇지 않으면 CheckSame을 수행하여 결과값을 출력한다.
💡예제:예를 들어, 다음과 같은 두 연산을 수행할 수 있다.
union(3, 7): 3과 7을 같은 집합으로 합친다.checkSame(3, 7): 3과 7이 같은 집합에 속해 있는지 확인하여 true 또는 false를 반환한다.
