C++ set_union·set_intersection·set_difference: 정렬된 범위의 집합 연산

작성 0xmote · 2026년 3월 21일 · 16분 읽기 · 수정 2026년 9월 24일 중급 튜토리얼

이 글의 핵심

집합 알고리즘은 입력이 정렬돼 있다고 가정하기 때문에 정렬을 빠뜨리면 오류 없이 틀린 결과를 냅니다. 결과를 담을 출력 반복자 선택, 중복 원소가 몇 번 포함되는지에 대한 규칙, std::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));

수동 합집합은 코드가 길다는 것보다 복잡도가 문제입니다. b의 원소마다 result 전체를 std::find로 훑으므로 O(n·m)이고, 두 벡터가 각각 10만 개면 수십억 번의 비교가 됩니다. set_union이 O(n + m)으로 끝나는 비결은 두 입력이 정렬되어 있다는 전제입니다. 두 범위의 앞에서부터 원소를 하나씩 비교하며 작은 쪽을 출력하고 그쪽을 한 칸 전진시키는, 병합 정렬의 병합 단계와 같은 방식이라 각 원소를 한 번씩만 봅니다. 교집합·차집합도 같은 두 포인터 순회에서 “어느 쪽 원소를 출력할지”만 다릅니다.

이 전제는 알고리즘이 확인하지 않습니다. 정렬되지 않은 입력을 넘기면 에러 없이 틀린 결과가 나오고, 표준상 정의되지 않은 동작입니다. MSVC의 디버그 빌드는 sequence not ordered 단언으로 잡아 주지만, GCC·Clang의 기본 빌드는 아무 말도 하지 않습니다(libstdc++는 -D_GLIBCXX_DEBUG를 주면 검사합니다). 이 알고리즘들을 쓰는 코드에서 버그가 난다면 가장 먼저 “입력이 같은 비교 기준으로 정렬되어 있는가”를 확인하십시오.

집합 연산 종류:

알고리즘	수학 기호	설명	예시
`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}
result.clear();  // back_inserter는 뒤에 이어 붙이므로 연산마다 비워야 함
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(result));

// 차집합: {1, 2}
result.clear();
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                    std::back_inserter(result));

// 대칭 차집합: {1, 2, 5, 6}
result.clear();
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
                              std::back_inserter(result));

std::back_inserter(result)는 출력할 때마다 result.push_back()을 호출하는 반복자입니다. 기존 내용을 지우지 않고 뒤에 이어 붙이므로, 같은 result에 여러 연산을 연달아 쓰면 결과가 섞입니다. 위 코드에서 result.clear()를 넣은 이유이며, 실제 코드에서는 연산마다 별도의 변수를 쓰는 편이 읽기 쉽습니다. 결과 크기의 상한을 알고 있다면 result.reserve(a.size() + b.size())로 재할당을 줄일 수 있습니다.

집합 연산 시각화:

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
    }
}

예제들이 #include <algorithm>만 적고 있지만, 실제로 컴파일하려면 std::back_inserter를 위한 <iterator>와 출력을 위한 <iostream>도 필요합니다. 표준 라이브러리 구현에 따라 <algorithm>이 이 헤더들을 간접적으로 포함해 우연히 컴파일되기도 하지만, 컴파일러를 바꾸면 'back_inserter' is not a member of 'std' 에러가 나는 흔한 원인이므로 쓰는 헤더는 직접 include하는 것이 원칙입니다.

네 알고리즘은 모두 출력 범위의 끝을 가리키는 반복자를 반환합니다. back_inserter를 쓸 때는 이 반환값이 필요 없지만, 미리 크기를 잡아 둔 배열에 쓸 때는 반환값으로 실제로 쓴 개수를 알 수 있습니다(아래 “문제 2”). C++20의 std::ranges::set_union(a, b, std::back_inserter(result))는 컨테이너를 통째로 받아 begin/end를 반복해 적지 않아도 되고, 입력 반복자의 끝 위치까지 함께 돌려줍니다.

집합 연산

// 합집합
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);

정렬 기준도 일치해야 합니다. 입력을 std::sort(a.begin(), a.end(), std::greater<>())로 내림차순 정렬했다면 set_union에도 같은 비교자 std::greater<>()를 마지막 인자로 넘겨야 합니다. 문자열을 대소문자 무시로 정렬했는데 집합 연산은 기본 비교(<)로 하면, 정렬은 되어 있어도 “같은 기준”이 아니라서 결과가 틀립니다. 구조체라면 정렬과 집합 연산에 같은 람다 변수를 재사용하는 것이 실수를 막는 가장 쉬운 방법입니다.

문제 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));

주석 처리된 코드의 문제는 result가 3칸인데 합집합 결과는 4개({1, 2, 3, 4})라는 점입니다. 출력 반복자는 범위를 확인하지 않으므로 네 번째 원소를 벡터 끝 너머에 써서 메모리를 망가뜨립니다. 미리 공간을 잡는 방식이 필요하다면(예: 재할당 없이 고정 버퍼를 쓰고 싶을 때) 최대 크기인 a.size() + b.size()로 resize한 뒤, 반환된 반복자로 남는 부분을 잘라 냅니다.

result.resize(a.size() + b.size());
auto it = std::set_union(a.begin(), a.end(), b.begin(), b.end(), result.begin());
result.erase(it, result.end());  // 실제로 쓴 부분만 남김

출력 범위가 입력 범위와 겹쳐서도 안 됩니다. a의 합집합 결과를 a.begin()부터 덮어쓰면 아직 읽지 않은 입력을 덮어쓰게 되어 정의되지 않은 동작입니다.

문제 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}
// 중복 최대 개수 유지

중복이 있는 범위는 수학의 집합이 아니라 다중집합(multiset)으로 취급됩니다. 어떤 값이 A에 m번, B에 n번 있으면 합집합에는 max(m, n)번, 교집합에는 min(m, n)번, 차집합 A−B에는 max(m − n, 0)번, 대칭 차집합에는 |m − n|번 나옵니다. 이 규칙은 “재고 목록” 같은 다중집합 연산에서는 유용하지만, 태그나 ID처럼 중복이 없어야 하는 데이터라면 입력 단계에서 a.erase(std::unique(a.begin(), a.end()), a.end());로 먼저 정리해야 예상한 결과가 나옵니다. std::unique도 인접한 중복만 제거하므로 반드시 정렬한 뒤에 호출해야 합니다.

문제 4: 성능

// 집합 연산: O(n + m)
// n, m: 두 범위 크기

// 정렬 필요: O(n log n + m log m)

// 여러 번 연산 시 정렬 한 번만

전체 비용은 정렬이 좌우합니다. 집합 연산 자체는 O(n + m)이지만 정렬되지 않은 데이터에서 시작하면 O(n log n + m log m)이 들고, 연산이 한 번뿐이라면 std::unordered_set에 한쪽을 넣고 다른 쪽을 조회하는 O(n + m) 평균 방식이 더 빠를 수 있습니다. 반대로 같은 데이터에 여러 번 집합 연산을 한다면, 정렬된 상태를 유지하는 비용은 한 번만 내면 되고 이후 연산은 모두 선형이며 결과도 정렬된 상태로 나와 다음 연산에 바로 쓸 수 있습니다. 해시 기반 방식은 결과 순서가 정해지지 않고 해시 계산 비용이 있으므로, 결과가 정렬되어야 하거나 원소 비교가 싸다면 정렬 기반이 유리합니다. 정렬된 std::vector는 std::set보다 메모리가 연속적이라 순회도 훨씬 빠릅니다.

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

std::includes(a..., b...)는 “b의 모든 원소가 a에 있는가”, 즉 b ⊆ a를 검사합니다. 인자 순서가 헷갈리기 쉬운데, 큰 쪽(포함하는 쪽)을 먼저 넘깁니다. std::cout으로 출력하면 true가 아니라 1이 찍히므로, 문자로 보고 싶다면 std::boolalpha를 먼저 출력하십시오. 다중집합 규칙도 그대로 적용되어, b에 2가 두 번 있으면 a에도 2가 두 번 이상 있어야 true입니다. 빈 범위 b는 모든 a의 부분집합이므로 항상 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";
}

이 예제는 includes의 사용법을 보여 주지만, 권한 하나를 확인하는 용도로는 과합니다. hasPermission은 호출될 때마다 권한 목록을 복사하고 정렬하므로 O(k log k)가 들고, 원소 하나짜리 required를 위해 벡터까지 만듭니다. 호출자가 이미 user.permissions를 정렬해 두었으니 함수 안에서는 std::binary_search(user.permissions.begin(), user.permissions.end(), perm)로 O(log k)에 끝낼 수 있고, 권한이 몇 개뿐이라면 std::find가 더 단순합니다.

includes가 제값을 하는 경우는 여러 권한을 한꺼번에 요구할 때입니다. 어떤 작업에 {"read", "write"}가 모두 필요하다면, 정렬된 사용자 권한과 정렬된 요구 권한을 includes 한 번으로 선형 시간에 비교할 수 있습니다. 이때도 정렬은 데이터를 저장할 때 한 번만 하고 조회 경로에서는 하지 않는 것이 요점입니다.

패턴 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"}

filterByTags는 이름과 달리 필터링 여부를 판단하지 않고 공통 태그를 돌려줍니다. 검색 조건이 “요청한 태그 중 하나라도 있으면”(OR)이라면 결과가 비어 있지 않은지 확인하면 되고, “요청한 태그가 모두 있어야”(AND)라면 교집합보다 std::includes(postTags..., searchTags...)가 의도에 맞습니다. 위 예에서 AND 검색이라면 advanced가 없으므로 이 글은 걸러져야 합니다.

std::string은 사전식으로 비교되므로 "CPP"와 "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}

변경 추적은 집합 알고리즘이 가장 빛나는 실무 패턴입니다. DB에 저장된 ID 목록과 새로 받은 ID 목록을 비교해 추가할 것과 삭제할 것을 구하는 동기화 작업에서, 두 목록을 한 번 정렬해 두면 차집합 두 번으로 O(n + m)에 끝납니다. 제가 이 패턴을 쓸 때 가장 자주 본 실수는 한쪽 목록이 DB에서 ORDER BY로 정렬되어 왔다고 믿고 다른 쪽만 정렬하는 것이었는데, DB의 정렬 규칙(collation)과 C++의 < 비교가 다르면 문자열 키에서 조용히 틀린 결과가 나옵니다. 신뢰할 수 없는 정렬 순서라면 양쪽을 모두 C++에서 다시 정렬하는 편이 안전합니다.

detectChanges는 입력이 정렬되어 있다고 가정하므로, 함수 문서나 이름(detectChangesSorted)으로 그 전제를 드러내거나 디버그 빌드에서 assert(std::is_sorted(oldData.begin(), oldData.end()))로 확인해 두면 좋습니다. 추가·삭제 외에 “값이 바뀐 항목”까지 필요하다면 ID만이 아니라 (ID, 값) 쌍을 비교해야 하므로, 이때는 두 목록을 직접 병합 순회하며 세 경우를 한 번에 분류하는 코드를 쓰는 편이 낫습니다.

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());
// true

Q6: std::set과의 차이는?

집합 알고리즘: 정렬된 범위 (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: 집합 알고리즘 학습 리소스는?

“Effective STL” by Scott Meyers (Item 35-36)
“C++ Primer” by Stanley Lippman
cppreference.com - Set operations

관련 글: algorithm, sort, set.

집합 알고리즘은 정렬된 범위에서 집합 연산을 수행하는 STL 알고리즘입니다.