C++ STL의 set_symmetric_difference란?
이 글에서는 C++ 표준 템플릿 라이브러리(STL)에서 제공하는 set_symmetric_difference 함수를 활용해 두 집합의 대칭차집합을 구하는 프로그램을 살펴봅니다.
대칭차집합(symmetric difference)은 두 집합 중 어느 한쪽에는 속하지만 양쪽 모두에는 속하지 않는 원소들로 구성된 집합입니다. 수학적으로 배타적 논리합(XOR)과 같은 개념으로, 두 집합의 합집합에서 교집합을 제거한 결과라고 이해할 수 있습니다.
C++ STL의 주요 집합 연산
STL 알고리즘이 지원하는 대표적인 집합 연산은 다음과 같습니다.
- 합집합(Union): 두 집합의 모든 원소를 포함 — set_union
- 교집합(Intersection): 두 집합에 공통으로 존재하는 원소만 포함 — set_intersection
- 대칭차집합(Symmetric Difference, XOR): 어느 한쪽에만 존재하는 원소를 포함 — set_symmetric_difference
- 차집합(Difference, Subtraction): 첫 번째 집합에만 존재하는 원소를 포함 — set_difference
알고리즘
Begin
정수형 벡터 v와 반복자(iterator) st를 선언한다.
st = set_symmetric_difference(set1, set1 + n, set2, set2 + n, v.begin()) 으로 초기화한다.
두 집합의 대칭차집합 결과로 얻은 원소들을 출력한다.
End.
예제 코드
아래 코드에서 주의할 점은 set_symmetric_difference가 정렬된(sorted) 범위를 요구하기 때문에, 연산 전에 반드시 sort 함수로 두 배열을 정렬해야 한다는 것입니다.
#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
int set1[] = {5,6,7,8,9,10}; // 첫 번째 집합
int set2[] = {1,2,3,4,6,7}; // 두 번째 집합
vector<int> v(10); // 결과를 저장할 벡터
vector<int>::iterator st;
sort (set1, set1 + 6); // 대칭차집합 연산 전 정렬 필수
sort (set2, set2 + 6);
st = set_symmetric_difference(set1, set1 + 6, set2, set2 + 6, v.begin());
v.resize(st - v.begin()); // 실제 결과 크기에 맞게 벡터 조정
cout<<"두 집합의 대칭차집합은 "<< (v.size())<< "개의 원소를 가집니다: "<<endl;
for (st = v.begin(); st != v.end(); ++st)
cout<< *st<<" ";
cout <<endl;
return 0;
}
실행 결과
두 집합의 대칭차집합은 8개의 원소를 가집니다:
1 2 3 4 5 8 9 10
코드 설명 및 참고 사항
위 예제에서 두 집합은 각각 {5,6,7,8,9,10}과 {1,2,3,4,6,7}입니다. 공통 원소인 6과 7은 교집합에 해당하므로 대칭차집합에서 제외되며, 나머지 원소인 1, 2, 3, 4, 5, 8, 9, 10이 최종 결과로 출력됩니다.
set_symmetric_difference는 결과의 끝 위치를 가리키는 반복자를 반환하므로, 반환값을 이용해v.resize(st - v.begin())처럼 벡터 크기를 실제 결과 크기로 줄이는 것이 좋습니다.- 입력 범위가 정렬되어 있지 않으면 올바른 결과를 보장할 수 없으므로, 항상 사전 정렬을 잊지 마세요.
- 이 함수의 시간 복잡도는 O(N+M)으로, N과 M은 각 입력 범위의 원소 개수입니다.