집합이란?
집합은 유일한 개체를 담는 자료구조이다. 즉 중복이 허용되지 않는다.
예를들면, A란 집합에 {1,2,3}원소가 있고 B란 집합에 {2,3,4} 원소가 있다면 A + B인 C 집합은 {1,2,3,4}가 된다.
집합 메쏘드
- union(B) : 집합 B와의 합집합
- intersect(B) : 집합 B와의 교집합
- subtrat(B) : 집합 B와의 차집합
집합은 연결리스트 형태로 구현 가능하고 각 노드는 하나의 집합 원소를 표현한다.
다음은 각 메쏘드에 대한 설명이다.
이 때 효율적인 구현을 위하여 정렬된 리스트로 표현하겠다.(오름차순)
Union (합집합)
코드 설명에 앞서 여기서 List 구조체는 헤더 노드와, 트레일러 노드를 포함한 구조체이다. A, B 두 집합을 합하여 C라는 새로운 집합을 만드는 과정이다.
void Union(List* A, List* B, List* C) {
// step1. A집합과 B집합의 첫 번째 원소를 각각 curA와 curB에 연결
Node* curA = A->head->next;
Node* curB = B->head->next;
// step2. 둘중 한 집합이 끝까지 읽을 때까지 C집합에 A,B원소 크기 비교하여 원소 추가
while (curA != NULL && curB != NULL) {
//A의 원소가 B 원소보다 작다면 C 집합에 A 원소를 추가하고 다음 원소로 넘어가기
if (curA->data < curB->data) {
insert(C, curA->data);
curA = curA->next;
}
//B의 원소가 A 원소보다 작다면 C 집합에 B 원소를 추가하고 다음 원소로 넘어가기
else if (curA->data > curB->data) {
insert(C, curB->data);
curB = curB->next;
}
//A, B원소 같은 경우 둘 중 아무거나 추가하고 A, B 다음 원소로 이동
else {
insert(C, curA->data);
curA = curA->next;
curB = curB->next;
}
}
//위 조건에서 A, B 집합이 하나라도 끝까지 다 탐색했을 때 while문을 종료하므로 A,B 둘 중 아직 끝까지 탐색하지 않았다면 그 집합 원소를 그대로 C 집합에 추가한다.
//A집합의 원소가 남아있을 때
while (curA != NULL) {
insert(C, curA->data);
curA = curA->next;
}
//B집합의 원소가 남아있을 때
while (curB != NULL) {
insert(C, curB->data);
curB = curB->next;
}
}
각 단계별로 주석을 작성했으니 전체적으로 코드를 설명해보겠다.
union 메쏘드는 A와 B집합을 하나의 C집합으로 합하는 과정이다.
A집합의 첫 번째 원소와, B집합의 첫 번째 원소부터 각각 비교하여 작은 원소부터 추가해주는 것이다.
예를 들면 A{1,3,7}, B{2,4,6,8,10,12} 집합이 있다면 첫 번째 원소인 1과 2를 비교하여 1 < 2이므로 C집합에 1 추가(C{1}), 그 다음 원소인 3과 2를 비교하여 3 > 2이므로 C집합에 2추가(C{1,2}), 3과 4 비교.... 이런식으로 비교를 진행한다.
이렇게 비교를 진행하다 A의 마지막 원소인 7과 B의 4번째 원소인 8을 비교한 직후 7이 C집합에 추가될 것이고 A집합 탐색이 끝났으니 B집합은 8,10,12 원소를 추가하지 못한 채로 while문을 빠져나갈 것이다.
따라서 (B집합의 원소가 남아있을 때)라는 조건에서 8,10,12 원소를 C집합에 마저 추가해줄 수 있다.
최종적으로 C집합의 원소는 C{1,2,3,4,6,7,8,10,12}가 된다.
intersect (교집합)
void intersect(List* A, List* B, List* C) {
Node* curA = A->head->next;
Node* curB = B->head->next;
while (curA != NULL && curB != NULL) {
if (curA->data > curB->data)//
curB = curB->next;
else if (curA->data < curB->data)
curA = curA->next;
else {
insert(C, curA->data);
curA = curA->next;
curB = curB->next;
}
}
}합집합을 이해했으면 교집합은 훨씬 쉽다.
합집합과 방식은 비슷하니 간략하게 설명하겠다.
합집합은 A원소와 B원소를 비교하여 작은 원소를 집합 C에 추가하였다면 교집합은 A원소와 B원소가 같을 때만 추가시켜주면 된다.
그리고 합집합과 달리 A집합 혹은 B집합 중 어느 하나라도 탐색이 끝날 경우에 더 이상 탐색할 필요가 없다. 원소가 남아있지 않다는 말은 즉 교집합이 없다는 말과 같기 때문이다.
subtract(차집합)
void subtract(List* A, List* B, List* C)
{
Node* curA = A->head;
Node* curB = B->head;
while (curA != NULL && curB != NULL)
{
if (curA->data > curB->data){
curB = curB->next;
}
else if (curA->data < curB->data){
insert(C, curA);
curA = curA->next;
}
else{
curA = curA->next;
curB = curB->next;
}
}
while (curA != NULL){
insert(C, curA);
curA = curA->next;
}
}
차집합은 B집합에 없는 A의 원소를 C집합에 추가한다.(C = A - B)
차집합도 위에서 했던 합집합, 교집합과 비슷하지만 처음에 구현하면서 살짝 헷갈렸다.
이 때 핵심은 B에 포함되지 않는 A의 원소를 C집합에 추가하는 것이므로 합집합과 다르게 A > B라면 추가하지 않고 B를 다음원소에 넘겨주고, A < B일 때만 추가해주는 것이다.
오름차순으로 정렬된 데이터라는 것을 떠올리면 쉽게 이해할 수 있다.
A{1,2,4,8}, B{2,3,4,6}이라는 집합이 있을 경우 먼저 A의 1과 B의 2를 비교하여 A가 작으므로 C에 1을 추가한다.
즉 A < B라는 뜻은 'B에는 이 원소가 없습니다'라는 뜻이다.
A의 2와 B의 2는 겹치므로 추가하지 않고 넘어가고 이런 식으로 탐색이 진행된다.
이 때도 합집합과 같은 메커니즘으로 A탐색이 끝나지 않았는데 B 탐색이 종료됐다? 그렇다면 A집합의 남아있는 모든 원소는 B집합에 없는 원소이므로 몽땅 추가해주면 된다.
