C++ Algorithm Set | "집합 알고리즘" 가이드
이 글의 핵심
C++ Algorithm Set에 대한 실전 가이드입니다.
집합 알고리즘이란?
집합 알고리즘 (Set Algorithm) 은 정렬된 범위에서 집합 연산을 수행하는 STL 알고리즘입니다. 합집합, 교집합, 차집합 등을 지원합니다.
#include <algorithm>
#include <vector>
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> result;
// 합집합
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
// {1, 2, 3, 4, 5, 6}왜 필요한가?:
- 효율성: O(n + m) 시간 복잡도
- 간결성: 복잡한 로직 간소화
- 정확성: 검증된 구현
- 유연성: 커스텀 비교 지원
// ❌ 수동 합집합: 복잡
std::vector<int> result = a;
for (int x : b) {
if (std::find(result.begin(), result.end(), x) == result.end()) {
result.push_back(x);
}
}
std::sort(result.begin(), result.end());
// ✅ set_union: 간결
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));집합 연산 종류:
| 알고리즘 | 수학 기호 | 설명 | 예시 |
|---|---|---|---|
set_union | A ∪ B | 합집합 | {1,2,3} ∪ {2,3,4} = {1,2,3,4} |
set_intersection | A ∩ B | 교집합 | {1,2,3} ∩ {2,3,4} = {2,3} |
set_difference | A - B | 차집합 | {1,2,3} - {2,3,4} = {1} |
set_symmetric_difference | A △ B | 대칭 차집합 | {1,2,3} △ {2,3,4} = {1,4} |
includes | A ⊇ B | 포함 관계 | {1,2,3} ⊇ {2,3} = true |
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> result;
// 합집합: {1, 2, 3, 4, 5, 6}
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
// 교집합: {3, 4}
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
// 차집합: {1, 2}
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
// 대칭 차집합: {1, 2, 5, 6}
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));집합 연산 시각화:
flowchart TD
A["A = 1, 2, 3, 4"]
B["B = 3, 4, 5, 6"]
A --> U["합집합\n1, 2, 3, 4, 5, 6"]
B --> U
A --> I["교집합\n3, 4"]
B --> I
A --> D["차집합 A-B\n1, 2"]
B --> D
A --> S["대칭 차집합\n1, 2, 5, 6"]
B --> S
기본 사용
#include <algorithm>
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> result;
// 정렬 필요
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
// 집합 연산
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));실전 예시
예시 1: 합집합
#include <algorithm>
#include <vector>
int main() {
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> result;
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
for (int x : result) {
std::cout << x << " "; // 1 2 3 4 5 6
}
}예시 2: 교집합
#include <algorithm>
int main() {
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> result;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
for (int x : result) {
std::cout << x << " "; // 3 4
}
}예시 3: 차집합
#include <algorithm>
int main() {
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> result;
// a - b
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
for (int x : result) {
std::cout << x << " "; // 1 2
}
}예시 4: 대칭 차집합
#include <algorithm>
int main() {
std::vector<int> a = {1, 2, 3, 4};
std::vector<int> b = {3, 4, 5, 6};
std::vector<int> result;
// (a - b) ∪ (b - a)
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
for (int x : result) {
std::cout << x << " "; // 1 2 5 6
}
}집합 연산
// 합집합
std::set_union(begin1, end1, begin2, end2, out)
// 교집합
std::set_intersection(begin1, end1, begin2, end2, out)
// 차집합
std::set_difference(begin1, end1, begin2, end2, out)
// 대칭 차집합
std::set_symmetric_difference(begin1, end1, begin2, end2, out)
// 포함 관계
bool includes = std::includes(begin1, end1, begin2, end2)자주 발생하는 문제
문제 1: 정렬
std::vector<int> a = {3, 1, 2};
std::vector<int> b = {4, 3, 5};
// ❌ 정렬 안 됨
// std::set_union(a.begin(), a.end(), b.begin(), b.end(), out); // 정의되지 않은 동작
// ✅ 정렬 후
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::set_union(a.begin(), a.end(), b.begin(), b.end(), out);문제 2: 출력 반복자
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {2, 3, 4};
std::vector<int> result;
// ❌ 크기 부족
// result.resize(3);
// std::set_union(a.begin(), a.end(), b.begin(), b.end(), result.begin());
// ✅ back_inserter
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));문제 3: 중복
std::vector<int> a = {1, 2, 2, 3};
std::vector<int> b = {2, 2, 3, 4};
std::vector<int> result;
// 중복 처리
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
// {1, 2, 2, 3, 4}
// 중복 최대 개수 유지문제 4: 성능
// 집합 연산: O(n + m)
// n, m: 두 범위 크기
// 정렬 필요: O(n log n + m log m)
// 여러 번 연산 시 정렬 한 번만includes
#include <algorithm>
std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {2, 3, 4};
// b가 a의 부분집합?
bool isSubset = std::includes(a.begin(), a.end(), b.begin(), b.end());
std::cout << "부분집합: " << isSubset << std::endl; // true실무 패턴
패턴 1: 권한 관리
#include <algorithm>
#include <vector>
#include <string>
struct User {
std::string name;
std::vector<std::string> permissions;
};
bool hasPermission(const User& user, const std::string& perm) {
std::vector<std::string> required = {perm};
// 정렬
auto userPerms = user.permissions;
std::sort(userPerms.begin(), userPerms.end());
std::sort(required.begin(), required.end());
// 포함 확인
return std::includes(userPerms.begin(), userPerms.end(),
required.begin(), required.end());
}
// 사용
User user{"Alice", {"read", "write", "execute"}};
std::sort(user.permissions.begin(), user.permissions.end());
if (hasPermission(user, "write")) {
std::cout << "쓰기 권한 있음\n";
}패턴 2: 태그 필터링
#include <algorithm>
#include <vector>
#include <string>
std::vector<std::string> filterByTags(
const std::vector<std::string>& allTags,
const std::vector<std::string>& requiredTags
) {
std::vector<std::string> result;
// 교집합: 공통 태그
std::set_intersection(
allTags.begin(), allTags.end(),
requiredTags.begin(), requiredTags.end(),
std::back_inserter(result)
);
return result;
}
// 사용
std::vector<std::string> postTags = {"cpp", "programming", "tutorial"};
std::vector<std::string> searchTags = {"cpp", "advanced"};
std::sort(postTags.begin(), postTags.end());
std::sort(searchTags.begin(), searchTags.end());
auto common = filterByTags(postTags, searchTags);
// 결과: {"cpp"}패턴 3: 변경 사항 추적
#include <algorithm>
#include <vector>
struct ChangeSet {
std::vector<int> added;
std::vector<int> removed;
};
ChangeSet detectChanges(
const std::vector<int>& oldData,
const std::vector<int>& newData
) {
ChangeSet changes;
// 추가된 항목: newData - oldData
std::set_difference(
newData.begin(), newData.end(),
oldData.begin(), oldData.end(),
std::back_inserter(changes.added)
);
// 제거된 항목: oldData - newData
std::set_difference(
oldData.begin(), oldData.end(),
newData.begin(), newData.end(),
std::back_inserter(changes.removed)
);
return changes;
}
// 사용
std::vector<int> oldIds = {1, 2, 3, 4};
std::vector<int> newIds = {2, 3, 5, 6};
auto changes = detectChanges(oldIds, newIds);
// added: {5, 6}
// removed: {1, 4}FAQ
Q1: 집합 알고리즘은 무엇인가요?
A: 정렬된 범위에서 집합 연산을 수행하는 STL 알고리즘입니다.
std::set_union(a.begin(), a.end(), b.begin(), b.end(), out);Q2: 정렬이 필수인가요?
A: 필수입니다. 정렬되지 않으면 정의되지 않은 동작입니다.
// ❌ 정렬 안 됨
std::set_union(a.begin(), a.end(), b.begin(), b.end(), out);
// ✅ 정렬 후
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::set_union(a.begin(), a.end(), b.begin(), b.end(), out);Q3: 중복은 어떻게 처리되나요?
A: 최대 개수를 유지합니다.
std::vector<int> a = {1, 2, 2, 3};
std::vector<int> b = {2, 2, 2, 4};
std::set_union(a.begin(), a.end(), b.begin(), b.end(), out);
// 결과: {1, 2, 2, 2, 3, 4} (2가 3개)Q4: 성능은?
A: O(n + m) 시간 복잡도입니다. 정렬 비용은 별도입니다.
// 집합 연산: O(n + m)
// 정렬: O(n log n + m log m)Q5: includes는?
A: 부분집합 확인입니다.
std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {2, 3, 4};
bool isSubset = std::includes(a.begin(), a.end(), b.begin(), b.end());
// trueQ6: std::set과의 차이는?
A:
- 집합 알고리즘: 정렬된 범위 (vector, array)
std::set: 자동 정렬 컨테이너
// 집합 알고리즘: 범위
std::vector<int> a = {1, 2, 3};
std::sort(a.begin(), a.end());
// std::set: 컨테이너
std::set<int> s = {1, 2, 3};Q7: 출력 반복자는?
A: std::back_inserter 를 사용합니다.
std::vector<int> result;
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));Q8: 집합 알고리즘 학습 리소스는?
A:
- “Effective STL” by Scott Meyers (Item 35-36)
- “C++ Primer” by Stanley Lippman
- cppreference.com - Set operations
관련 글: algorithm, sort, set.
한 줄 요약: 집합 알고리즘은 정렬된 범위에서 집합 연산을 수행하는 STL 알고리즘입니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- C++ Algorithm Sort | “정렬 알고리즘” 가이드
- C++ Algorithm Partition | “분할 알고리즘” 가이드
- C++ Algorithm MinMax | “최소/최대 알고리즘” 가이드
실전 팁
실무에서 바로 적용할 수 있는 팁입니다.
디버깅 팁
- 문제가 발생하면 먼저 컴파일러 경고를 확인하세요
- 간단한 테스트 케이스로 문제를 재현하세요
성능 팁
- 프로파일링 없이 최적화하지 마세요
- 측정 가능한 지표를 먼저 설정하세요
코드 리뷰 팁
- 코드 리뷰에서 자주 지적받는 부분을 미리 체크하세요
- 팀의 코딩 컨벤션을 따르세요
실전 체크리스트
실무에서 이 개념을 적용할 때 확인해야 할 사항입니다.
코드 작성 전
- 이 기법이 현재 문제를 해결하는 최선의 방법인가?
- 팀원들이 이 코드를 이해하고 유지보수할 수 있는가?
- 성능 요구사항을 만족하는가?
코드 작성 중
- 컴파일러 경고를 모두 해결했는가?
- 엣지 케이스를 고려했는가?
- 에러 처리가 적절한가?
코드 리뷰 시
- 코드의 의도가 명확한가?
- 테스트 케이스가 충분한가?
- 문서화가 되어 있는가?
이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.
이 글에서 다루는 키워드 (관련 검색어)
C++, algorithm, set, union, STL 등으로 검색하시면 이 글이 도움이 됩니다.
관련 글
- C++ Algorithm Copy |
- C++ Algorithm Count |
- C++ Algorithm Generate |
- C++ 알고리즘 |
- C++ Algorithm Heap |