집합 개념
순서와 중복이 없는 원소들을 갖는 자료구조
집합의 종류
집합의 종류는 다양하다. 원소 갯수가 유한한 집합(유한집합), 원소 갯수가 무한한 집합(무한집합), 아무런 원소가 없는 집합(공집합) 등등..
상호배타적 집합
교집합(공통의 원소가 존재하는 집합)이 없는 집합. 즉 두개의 집합 사이에 공통의 원소가 존재하지 않는 집합.
상호배타적 집합의 특성을 활용하는 분야
- 그래프 알고리즘에서 많이 활용한다. 그래프 알고리즘에서는 사이클 확인이 다수 존재하는데, 그 작업에 상호배타적 집합 개념을 활용한다. 이 외에도 상호 배타적 집합 개념을 활용하는 알고리즘은 다양하다.
1. 이미지 분할
- 이미지를 서로 다른 부분으로 나누는데 사용. ex) 사람과 배경을 겹치지 않게 분할하는데 사용 될 수 있음.
2. 도로 네트워크 구성
- 도로를 구축할 때 각 도로를 서로 교차하지 않도록 설계하는데 사용 할 수 있음.
3.최소 신장 트리 알고리즘 구현
- 최소 신장 트리 알고리즘을 구현해서, 간선을 추가 할 때마다 사이클을 형성하는지 여부 체크
4. 게임 개발
- 캐릭터의 동작을 자연스럽게 구현 ex) 캐릭터의 충돌시 겹치지 않도록
5. 클러스터링 작업
- 각 작업이 서로 겹치지 않도록 구성 할 수 있음. 이렇게 작업간의 의존 관계가 없으면. 동시에 여러 작업을 진행가능
집합의 연산
보통 집합은 트리로 표현하면 대표적인 연사은 합치기와 탐색이 존재
배열을 활용한 트리로 집합 표현하기
집한은 배열을 활용한 트리로 구현. 각 집합에는 대표 원소가 있어야 함
대표 원소란?
- 대표 원소는 집합의 원소 중 집합을 대표하는 역할을 함. 집합의 형태를 트리로 표현 할 경우 대표 원소와 루트 노드는 개념적으로 동일함.
배열로 집합을 표현하는 것
하나의 배열로 상호배타적 관계를 가지는 집합을 모두 표현한다는 것을 의미
- 배열의 인덱스는 자신을, 배열의 값은 부모 노드를 의미.
루트 노드는 말 그대로 집합의 대표 원소이기 때문에 없고, 본인이 부모노드 , 루트 노드는 값 자체가 배열의 인덱스와 동일. 하단의 사진 참조
집합을 표현할 때 사용하는 배열의 크기는 배열의 인덱스가 모든 집합의 원소를 표현 할 수 있으면 됨.
집합 표현 완벽 정리
위와 같은 집합을 앞서 본 것처럼 disjointSet 배열을 활용한 트리로 나타내면 다음 특성을 가지게 된다 .
- 각 집합의 루트 노드는 1과 4.
이를 disjointSet 배열에 표현하면 disjointSet[1] = 1, disjointSer[4] = 4 즉, 인덱스와 값이 같다.- disjointSet[3] = 2, disjointSet[2] =1 해석하면,
집합 A의 원소 3의 부모는 2, 집합 B의 원소 2의 부모는 1이라는 뜻
2-1. 원소 3은 disjointSet3] = 2, disjointSet[2] = 1, disjointSet[1] = 1이므로 원소 3은 원소 1이 루트 노드인 집합에 속한다'라고 이야기할 수 있다.- 집합 A와 집합 B를 표현할 배열의 크기를 10으로 한다.
- 두 집합은 하나의 배열(disjointSet)로 표현할 수 있다.
※ 집합의 개수는 루트 노드의 개수를 보면 된다. 즉, 배열의 인덱스와 값이 같은 경우가 몇 번인지 확인.
집합을 배열로 구현 하는 방법
01 초기 각 노드는 자기 자신을 루트 노드로 하였고, 집합에 없는 인덱스의 값은 -1로 했다.. 아직 1, 2, 3, 4, 5, 8, 9는 누구와도 연결되지 않았으므로 자기 자신을 부모 노드로 한다.
02 이제 집합이 완성되었을 때 그림. 그림을 보면 2개의 집합이 존재한다. 집합 A는 {1, 2, 3, 5, 9}이고 집합 B는 {4, 8}입니다. 루트 노드는 음영 처리한 1과 4입니다. 그리고 점선으로 노드 9의 루트 노드를 찾는 과정을 표시했습니다. 9 -> 3 -> 2 -> 1 순서로 이동.
유니온-파인드 알고리즘
집합 알고리즘은 보통 합치기(union)와 탐색(find) 두 가지로 이루어져 있다. 이 둘을 묶어서 유니온-파인드 알고리즘 이라고 부른다.
파인드 연산
- 특정 노드의 루트 노드가 무엇인지 탐색하는 방법. 보통 파인드 연산은 특정 노드가 같은 집합에 있는지 확인 할 때 사용
가장 간단한 방법은 현재 노드의 부모 노드로 거슬러 올라가며 부모 노드가 루트 노드일 경우 연산을 종료하는 것이다. 이 연산은 재귀함수로 구현 할 수 있지만, 아래의 사진과 같이 최악의 경우 시간 복잡도가 O(N) 일 수 있다. 파인드 연산의 목표는 루트 노드를 찾는 것이지, 부모 노드를 찾는 것이 아니기에 경로 압축을 사용 할 수 있다.
경로 압축
집합의 형태를 유지하면서도 트리의 높이를 줄이면 된다. 트리의 높이를 줄이므로 앞서 언급한 파인드 연산의 부모 노드를 거치는 과정을 줄일 수 있다.
경로 압축 전후의 트리를 비교하면 트리의 깊이가 다르다. 트리의 깊이가 낮아지면 최악 경우 수행해야하는 연산 횟수가 줄어듭니다.
유니온 연산
- 두 집합을 하나로 합치는 연산 두 집합을 합친다는건 두 집합의 루트 노드를 같게 하는 것. 이 때 루트 노드는 두 집합의 루트 노드 중 하나가 되면 됨. 그림으로 보면 좀더 명확하다.
위 사진과 같은 노드를 아래의 사진과 같이 합칠 수 있다.
위와 같은 경우 트리의 깊이가 깊어 질 수록 연산 비용이 커진다는 단점이 있다. 이를 개선하기위해서 랭크라는 개념을 사용한다.
랭크
- 현재 노드를 기준으로 하였을때 가장 깊은 노드까지의 경로 길이
- 두 노드의 루트 노드를 구하여 랭크의 값이 큰 값을 기준으로 삼아 두 집합을 합칩니다.
