안녕하세요, 스터디 5주차입니다. 이번에는 집합 알고리즘에 대해서 어떻게 표현하는지와 구현하는 방법을 알아보려고 합니다. 도움이 되는 글이었으면 좋겠습니다. 😄
1. 집합(Set)의 정의에 대해 알아보면...
수학에서 집합(Set)은 어떤 명확한 조건을 만족시키는 서로 다른 대상들의 모임을 말합니다.
컴퓨터 과학에서는 순서와 중복이 없는 원소들을 갖는 자료구조를 말합니다.
1-1. 코딩 테스트에 필요한건 상호배타적 집합
집합(Set)은 여러 문제를 해결하기 위해 자주 사용되는데, 특히 상호배타적 집합(Disjoint Set)은 서로 겹치지 않는 원소들로 이루어진 여러 집합 즉, 교집합이 없는 집합관계로 서로 다른 집합들을 효율적으로 관리할 수 있게 해줍니다. 위 그림의 집합A와 집합B는 상호배타적 집합이라 할수 있겠죠. 이글에서는 상호배타적 집합을 중점적으로 이야기하겠습니다.
2. 상호배타적 집합을 표현하기 위해서는?
서로 겹치지 않는 원소들로 이루어진 상호배타적 집합을 위해서 몇가지 고려할 점을 나열해보면 다음과 같습니다.
- 특정 집합 원소들이 하나의 집합의 원소라는 것을 알 수 있어야함
- 각 집합이 빠르게 다른 집합이라는 것을 알 수 있어야함
- 특정원소가 어느 집합에 속하는지 알 수 있었어야함
- 2개의 집합을 하나로 합칠 수 있어야함
나열한 문제들을 모두 고려하면서 충족시키기 위해서는 무엇이 필요할까요?
2-2. 대표원소
위 문제들을 해결하기 위해서는 집합을 식별할 수 있는 원소를 설정하면 됩니다. 말그대로 집합의 원소들 중 대표하는 원소를 정하자.!! 집합을 트리형태로 표현한다면, 대표원소를 루트노드를 설정하고, 서로 연결해주면 됩니다.
2-3. 집합을 배열로 표현하기
상호배타적 집합을 배열로 표현할 수 있습니다. 예를 들어, 위그림 처럼 대표원소 2를 가진 집합 A와 대표원소 4를 가진 집합 B가 있다고 가정해 봅시다. 이를 배열로 표현하면, 각 원소는 자신의 부모 노드를 가리키며, 루트 노드는 자기 자신을 가리킵니다.
이때, 배열의 인덱스는 원소를 나타내고, 해당 인덱스의 값은 부모 노드를 가리킵니다. 루트 노드의 경우 자기 자신을 가리키도록 하며, 존재하지 않는 노드는 -1로 표시할 수 있습니다.
3. 대표원소를 찾는 find 연산
집합 알고리즘에서 주로 쓰이는 연산은 집합을 합치기와 탐색입니다. 그중 탐색을 하는 find 연산은 특정 원소가 속한 집합의 대표원소를 찾는 과정입니다. 이 연산을 통해 원소가 속한 집합을 확인하고, 이를 바탕으로 다른 연산을 수행할 수 있습니다.
위 그림과 같은 예시로 find(7) 연산의 구체적인 과정을 살펴보면 아래와 같습니다.
1. 현재 노드와 부모 노드가 같을때까지 탐색 과정을 반복
2. 현재 노드 7의 부모노드는 6, 같지 않으므로 현재노드를 부모노드인 6으로 변경
3. 현재 노드 6의 부모노드는 2, 같지 않으므로 현재노드를 부모노드인 2로 변경
3. 현재 노드 2의 부모노드는 1, 같지 않으므로 현재노드를 부모노드인 1로 변경
4. 현재 노드 1의 부모노드는 1, 같으므로 현재노드1은 루트노드 임 (루트노드를 리턴)
find(7)을 호출하면, 7번 원소가 속한 집합의 대표 원소를 찾아 반환합니다. 이는 7번 원소가 최종적으로 어떤 집합에 속해 있는지를 확인하는 과정입니다. 만약 7번 원소가 집합 A에 속해 있다면, 이 연산은 집합 A의 대표 원소를 반환하게 됩니다.
3-1. 어떻게하면 경로의 깊이를 줄일 수 있을까?
대표 원소를 찾을 때, 트리의 깊이가 깊다면 탐색에 오랜 시간이 걸릴 수 있습니다. 예를 들어, 아래와 같은 구조를 생각해 봅시다.
1 -> 2 -> 3 -> 4이 경우 find(4)를 호출하면, 1번 노드까지 탐색해야 하므로 시간이 많이 소요됩니다. 따라서 경로의 깊이를 줄이면 이러한 탐색이 더욱 효율적으로 이루어질 수 있습니다.
3-2. 경로압축 알고리즘
경로압축(Path Compression) 알고리즘은 find 연산을 수행할 때 경로의 깊이를 줄이기 위해 사용합니다.
예를 들어, find(4)를 수행할때 모든 중간 노드를 루트 노드에 직접 연결하면, 이후의 find 연산이 더 빠르게 수행될 수 있겠죠.
경로압축을 통해 트리의 깊이가 최소화되므로, 이후의 find 연산은 O(1)에 가까운 시간 복잡도를 가질 수 있습니다.
실제 함수 호출 과정의 그림을 보시면 1, 2, 3, 4의 경로의 깊이가 확 줄어드는걸 알 수 있습니다.
find(4), disjoint[4] = disjoint[3] 이후, disjoint[4] 반환
-> find(3), disjoint[3] = disjoint[2] 이후, disjoint[3] 반환
-> find(2), disjoint[2] = disjoint[1] 이후, disjoint[2] 반환
-> find(1), 루트노드 이므로 disjoint[1] 반환
4. 두개의 집합을 합치는 union 연산
집합 알고리즘에서 주로 쓰이는 연산은 집합을 합치기와 탐색중에 집합을 합치는 union 연산은 두 개의 집합을 하나로 합치는 작업입니다. 이 과정에서 두 집합의 대표원소를 비교하여 하나의 대표원소를 다른 대표원소에 연결하는 방식인데, 일반적으로는 작은 값을 가진 대표원소에 합치는 방법을 사용합니다.
4-1. 그러면 집합을 합칠때도, 깊이를 최소화 할 수 있을까?
좀 더 효율적으로 집합을 합치는 방법은 없을까요?
원소를 탐색할 때 깊이가 최소화된다면, 연산의 효율성을 더욱 높일 수 있지 않을까요? 하여 랭크(rank)라는 개념을 도입할 수 있습니다.
4-2. 랭크기반 알고리즘
랭크가 무엇인지가 가장 중요한데, 단순히 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 말합니다. 랭크 기반 알고리즘을 활용하면 두 트리의 랭크를 비교하여, 더 낮은 트리를 더 높은 트리에 연결함으로써 집합의 높이가 불필요하게 커지는 것을 방지할 수 있게 됩니다.
위 그림 예시, 집합A의 랭크가 2이고, 집합B의 랭크가 1이라면, 집합B를 집합A에 연결하여 전체 트리의 높이를 최소화할 수 있겠죠?
5. 집합의 구현
상호배타적 집합은 다양한 방식으로 구현될 수 있으며, 주로 배열이나 해시테이블을 사용할 수 있습니다.
5-1. 배열로 구현
노드의 최대값이 크지 않은 경우 배열을 사용하여 상호배타적 집합을 구현할 수 있습니다. 배열은 메모리 사용이 효율적이며, 단순한 연산을 수행하는 데 적합합니다.
예시코드
import java.util.Arrays;
public class DisjointSet {
private static final int MAX_SIZE = 10; // 예제에서는 최대 요소 수를 10으로 설정
private int[] parent = new int[MAX_SIZE];
private int[] rank = new int[MAX_SIZE];
// 초기화 함수: n개의 요소로 초기화
public void initialize(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i; // 초기에는 모든 요소가 자기 자신을 부모로 가짐
rank[i] = 0; // 초기 랭크는 0으로 설정
}
}
// find 함수: 경로 압축 기법을 사용하여 루트 찾기
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 경로 압축
}
return parent[x];
}
// union 함수: rank를 사용하여 두 집합 합치기
public void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
// rank가 더 낮은 트리를 더 높은 트리 밑에 붙임
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public static void main(String[] args) {
DisjointSet ds = new DisjointSet();
int n = 10; // 예제용 요소 수
ds.initialize(n);
// unionSets 호출 예시:
ds.unionSets(1, 2);
ds.unionSets(3, 4);
ds.unionSets(2, 4);
ds.unionSets(5, 6);
// find 연산 수행 및 결과 출력
System.out.println("find(1): " + ds.find(1)); // 1
System.out.println("find(2): " + ds.find(2)); // 1
System.out.println("find(3): " + ds.find(3)); // 1
System.out.println("find(4): " + ds.find(4)); // 1
System.out.println("find(5): " + ds.find(5)); // 5
System.out.println("find(6): " + ds.find(6)); // 5
// 상태 확인
System.out.println("Parent array: " + Arrays.toString(ds.parent));
System.out.println("Rank array: " + Arrays.toString(ds.rank));
}
}
5-2. 해시맵으로 구현
노드의 최대값이 매우 큰 경우에는 해시테이블을 사용하여 집합을 구현할 수 있습니다. 해시테이블은 큰 키 범위를 다루는 데 효율적이며, 다양한 크기의 집합을 처리할 때 유리합니다.
예시코드
import java.util.HashMap;
public class DisjointSet {
private HashMap<Long, Long> parent = new HashMap<>();
private HashMap<Long, Integer> rank = new HashMap<>();
// 초기화 함수: 주어진 노드를 초기화
public void initialize(long x) {
parent.put(x, x); // 초기에는 모든 노드가 자기 자신을 부모로 가짐
rank.put(x, 0); // 초기 랭크는 0으로 설정
}
// find 함수: 경로 압축 기법을 사용하여 루트 찾기
public long find(long x) {
if (parent.get(x) != x) {
parent.put(x, find(parent.get(x))); // 경로 압축
}
return parent.get(x);
}
// union 함수: rank를 사용하여 두 집합 합치기
public void unionSets(long x, long y) {
long rootX = find(x);
long rootY = find(y);
if (rootX != rootY) {
// rank가 더 낮은 트리를 더 높은 트리 밑에 붙임
if (rank.get(rootX) > rank.get(rootY)) {
parent.put(rootY, rootX);
} else if (rank.get(rootX) < rank.get(rootY)) {
parent.put(rootX, rootY);
} else {
parent.put(rootY, rootX);
rank.put(rootX, rank.get(rootX) + 1);
}
}
}
public static void main(String[] args) {
DisjointSet ds = new DisjointSet();
// 노드 값이 매우 큰 경우를 가정하여 몇 가지 노드를 초기화
ds.initialize(1000000000L);
ds.initialize(1000000001L);
ds.initialize(2000000000L);
ds.initialize(2000000001L);
// unionSets 연산 수행
ds.unionSets(1000000000L, 1000000001L);
ds.unionSets(2000000000L, 2000000001L);
ds.unionSets(1000000001L, 2000000001L);
// find 연산 수행 및 결과 출력
System.out.println("find(1000000000): " + ds.find(1000000000L));
System.out.println("find(1000000001): " + ds.find(1000000001L));
System.out.println("find(2000000000): " + ds.find(2000000000L));
System.out.println("find(2000000001): " + ds.find(2000000001L));
}
}
6. 그러면 언제 상호배타적 집합 알고리즘을 사용할까?
집합 알고리즘은 주로 서로 다른 그룹 간의 연결 여부를 판단하거나, 그룹을 병합할 때 사용됩니다. 대표적인 예로, 대규모 네트워크에서 두 컴퓨터가 서로 연결되어있는지, 연결 상태를 확인하거나, 이미지에서 각 객체마다 분할해서 어떠한 처리해 해야하는 이미지 세그멘테이션 등의 문제에 적용할 수 있답니다.
집합(Set) 알고리즘, 특히 상호배타적 집합에 대해서 정리 해봤는데요.
알고리즘이 부족한 저한테는 생소한 내용이었는데, 공부하면서 지식을 많이 쌓게된 것 같아요.
부족한 글 읽어 주셔서 감사합니다. 또한 잘못된 내용 있으면 지적해주시면 감사하겠습니다. 🙏
하얀종이 개발자
Reference
https://ko.wikipedia.org/wiki/%EC%A7%91%ED%95%A9 - 위키피디아 집합
https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/ - geeksforgeeks (Introduction to disjoint Set, Union-Find Algorithm)
https://www.geeksforgeeks.org/union-by-rank-and-path-compression-in-union-find-algorithm/ - geeksforgeeks (rank and path compression in union-find Algorithm)
https://www.youtube.com/watch?v=pQ4fcGEG-PY - 코딩테스트 합격자 되기 c++편 - 집합 유튜브 강의
https://goldenrabbit.co.kr/product/cpppass/ - (골든래빗) 코딩테스트 합격자 되기 c++편 - 책
[되기] 코딩 테스트 합격자 되기(C++ 편) - 골든래빗
신입 사원 코딩 테스트를 준비하고 계신가요? 코딩 테스트는 문제만 열심히 푼다고 통과할 수 없습니다. 시험은 전략적으로 준비해야 합니다. 《코딩 테스트 합격자 되기》(C++ 편)은 신입 사원
goldenrabbit.co.kr
'Algorithm & Data Structure' 카테고리의 다른 글
| 그래프 탐색 완벽 가이드: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) (0) | 2024.08.27 |
|---|---|
| 이진탐색트리(Binary Search Tree)의 핵심: 탐색, 구조, 순회 방법 쉽게 배우기 (0) | 2024.08.04 |
| 해시(Hash) 함수와 충돌(Collision) 해결 전략: 효율적인 데이터 관리 (0) | 2024.07.29 |
| 선형 자료구조 탐구: 스택, 큐, 덱으로 배우는 알고리즘 기초 (0) | 2024.07.19 |
| 코딩 테스트 필수 개념: 시간 복잡도를 알면 문제 해결이 쉬워진다 (2) | 2024.07.12 |
