C++ STL 고급 알고리즘 | partition·merge·집합 연산·힙으로 데이터 처리 마스터

· 35분 읽기 · 수정 중급 개념
C++ STL 고급 알고리즘 | partition·merge·집합 연산·힙으로 데이터 처리 마스터

이 글의 핵심

partition, merge, set_union, set_intersection, make_heap, push_heap 등 고급 STL 알고리즘. 문제 시나리오, 완전한 예제, 흔한 에러, 베스트 프랙티스, 프로덕션 패턴.

들어가며: 조건 분할·병합·집합 연산이 필요한데 직접 구현했어요

”짝수와 홀수를 나누려다 버그가 났어요”

데이터를 조건에 따라 앞뒤로 나누거나, 정렬된 두 시퀀스를 하나로 합치거나, 두 집합의 교집합·합집합을 구할 때 직접 for문을 작성하다 보면 경계 조건 실수, 성능 이슈가 반복됩니다. C++ STL에는 partition, merge, 집합 연산(set_union, set_intersection 등), 힙 연산(make_heap, push_heap 등)이 이미 구현되어 있어, 한 줄로 표현하면서 검증된 성능을 얻을 수 있습니다.

비유하면 partition은 “합격/불합격 명단을 앞뒤로 나누는 것”, merge는 “이미 정렬된 두 명단을 하나로 합치는 것”, set_union은 “두 반의 출석부를 합쳐 중복 없이 만드는 것”, heap은 “항상 최대값이 맨 위에 오는 우선순위 큐”입니다.

문제의 코드:

// ❌ 나쁜 예: 수동으로 짝수/홀수 분할
std::vector<int> vec = {1, 2, 3, 4, 5, 6};
std::vector<int> evens, odds;
for (int x : vec) {
    if (x % 2 == 0) evens.push_back(x);
    else odds.push_back(x);
}
// 두 벡터를 따로 관리해야 함, 원본 구조 변경 불가

STL 고급 알고리즘으로 해결:

// ✅ partition: 제자리에서 조건에 따라 앞뒤 분할
std::vector<int> vec = {1, 2, 3, 4, 5, 6};
auto pivot = std::partition(vec.begin(), vec.end(),
     { return x % 2 == 0; });
// [begin, pivot): 짝수, [pivot, end): 홀수

이 글을 읽으면:

  • partition·stable_partition으로 조건 분할을 할 수 있습니다.
  • merge·inplace_merge로 정렬된 시퀀스를 병합할 수 있습니다.
  • set_union·set_intersection·set_difference로 집합 연산을 할 수 있습니다.
  • make_heap·push_heap·pop_heap으로 우선순위 큐를 구현할 수 있습니다.
  • 흔한 에러를 피하고 프로덕션 패턴을 적용할 수 있습니다.

목차

  1. 문제 시나리오
  2. Partition: 조건 분할
  3. Merge: 정렬된 시퀀스 병합
  4. 집합 연산: set_union, set_intersection, set_difference
  5. 힙 연산: make_heap, push_heap, pop_heap
  6. 완전한 고급 알고리즘 예제
  7. 자주 발생하는 에러와 해결법
  8. 베스트 프랙티스
  9. 프로덕션 패턴
  10. 구현 체크리스트

1. 문제 시나리오

시나리오 1: 로그 레벨별 분할

상황: 수십만 건의 로그를 ERROR/WARN만 앞쪽에 모아 빠르게 처리하고 싶습니다. 수동으로 두 벡터에 나눠 넣으면 메모리가 두 배로 늘고, 원본 인덱스 정보가 사라집니다.

해결: std::partition으로 제자리에서 조건이 참인 원소를 앞으로 모읍니다. 반환된 pivot으로 [begin, pivot)이 ERROR/WARN, [pivot, end)가 그 외입니다.

시나리오 2: 정렬된 두 리스트 병합

상황: 타임스탬프 기준으로 정렬된 두 개의 이벤트 스트림을 시간순으로 합쳐야 합니다. 수동 병합은 경계 조건(한쪽이 먼저 끝나는 경우)에서 실수하기 쉽습니다.

해결: std::merge는 두 정렬된 범위를 한 번에 병합해 정렬된 결과를 출력합니다. O(n+m)에 동작합니다.

시나리오 3: 두 사용자 그룹의 공통·차이 구하기

상황: A 그룹과 B 그룹의 ID 목록이 있을 때, “둘 다 속한 사람”, “A에만 속한 사람”, “합집합”을 구해야 합니다. 이중 루프로 비교하면 O(n×m)입니다.

해결: 두 범위를 정렬한 뒤 std::set_intersection, std::set_difference, std::set_union을 사용하면 O(n+m)에 처리됩니다.

시나리오 4: 상위 K개만 유지하는 스트리밍

상황: 실시간으로 점수가 들어오는데, 항상 “상위 10명”만 유지해야 합니다. 매번 전체 정렬하면 O(n log n)이 반복됩니다.

해결: std::make_heap + std::push_heap + std::pop_heap으로 최대 힙을 유지하면, 삽입·삭제가 O(log n)이고 상위 K개 추출도 O(k log n)입니다.

고급 알고리즘 분류 다이어그램

flowchart TB
    subgraph partition["분할 (Partition)"]
        P1[partition]
        P2[stable_partition]
    end
    subgraph merge["병합 (Merge)"]
        M1[merge]
        M2[inplace_merge]
    end
    subgraph set["집합 연산"]
        S1[set_union]
        S2[set_intersection]
        S3[set_difference]
        S4[set_symmetric_difference]
    end
    subgraph heap["힙 연산"]
        H1[make_heap]
        H2[push_heap]
        H3[pop_heap]
        H4[sort_heap]
    end
    input["(begin, end) 반복자"] --> partition
    input --> merge
    input --> set
    input --> heap

위 다이어그램 설명: STL 고급 알고리즘은 partition(분할), merge(병합), 집합 연산, 힙 연산으로 분류됩니다. 각각 전제 조건(정렬 여부 등)이 있으므로 사용 전 확인이 필요합니다.

2. Partition: 조건 분할

partition vs stable_partition

std::partition은 조건이 참인 원소를 앞쪽으로, 거짓인 원소를 뒤쪽으로 모읍니다. 반환값은 “거짓인 구간의 첫 반복자”이므로, [begin, pivot)이 참, [pivot, end)가 거짓입니다. 원래 순서는 보장되지 않습니다. 순서를 유지하려면 std::stable_partition을 사용합니다.

flowchart LR
    subgraph before["분할 전"]
        B1[1] --> B2[2] --> B3[3] --> B4[4] --> B5[5] --> B6[6]
    end
    subgraph after["partition 후"]
        A1[2] --> A2[4] --> A3[6] --> A4[1] --> A5[3] --> A6[5]
    end
    before -->|"짝수 앞으로"| after

std::partition: 기본 사용

// g++ -std=c++17 -o partition_demo partition_demo.cpp && ./partition_demo
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};

    // 짝수를 앞으로, 홀수를 뒤로
    auto pivot = std::partition(vec.begin(), vec.end(),
         { return x % 2 == 0; });

    std::cout << "짝수 [begin, pivot): ";
    for (auto it = vec.begin(); it != pivot; ++it)
        std::cout << *it << " ";
    std::cout << "\n";

    std::cout << "홀수 [pivot, end): ";
    for (auto it = pivot; it != vec.end(); ++it)
        std::cout << *it << " ";
    std::cout << "\n";

    return 0;
}

실행 결과:

짝수 [begin, pivot): 8 2 6 4
홀수 [pivot, end): 5 3 7 1

위 코드 설명: partition은 predicate가 참인 원소를 앞으로 모읍니다. 반환값 pivot은 “거짓인 구간의 시작”이므로, [begin, pivot)이 짝수, [pivot, end)가 홀수입니다. 순서는 보장되지 않습니다.

std::stable_partition: 순서 유지

같은 조건 내에서 원래 입력 순서를 유지해야 할 때 사용합니다. 예: “점수 60 이상을 앞으로, 같은 점수 내에서는 원래 순서 유지”.

#include <algorithm>
#include <vector>
#include <iostream>

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 85}, {"Bob", 55}, {"Charlie", 90}, {"David", 60}, {"Eve", 45}
    };

    // 60점 이상을 앞으로, 순서 유지
    auto pivot = std::stable_partition(students.begin(), students.end(),
         { return s.score >= 60; });

    std::cout << "합격 (60점 이상): ";
    for (auto it = students.begin(); it != pivot; ++it)
        std::cout << it->name << "(" << it->score << ") ";
    std::cout << "\n";

    std::cout << "불합격: ";
    for (auto it = pivot; it != students.end(); ++it)
        std::cout << it->name << "(" << it->score << ") ";
    std::cout << "\n";

    return 0;
}

실행 결과:

합격 (60점 이상): Alice(85) Charlie(90) David(60)
불합격: Bob(55) Eve(45)

위 코드 설명: stable_partition은 partition과 동일하게 조건 분할하되, 같은 조건 그룹 내에서 원래 순서를 유지합니다. Alice → Charlie → David 순서가 보존됩니다.

partition_point: 분할 지점 찾기

이미 partition된 범위에서 pivot 위치를 찾을 때 std::partition_point를 사용합니다.

std::vector<int> vec = {2, 4, 6, 1, 3, 5};  // 이미 partition됨
auto pivot = std::partition_point(vec.begin(), vec.end(),
     { return x % 2 == 0; });
// pivot은 1을 가리킴

3. Merge: 정렬된 시퀀스 병합

std::merge: 두 정렬된 범위 병합

std::merge는 두 개의 정렬된 범위를 하나의 정렬된 범위로 병합합니다. 두 범위가 각각 정렬되어 있어야 하며, 결과는 출력 반복자에 씁니다. O(n+m) 시간에 동작합니다.

flowchart LR
    subgraph A["정렬된 A"]
        A1[1] --> A2[3] --> A3[5]
    end
    subgraph B["정렬된 B"]
        B1[2] --> B2[4] --> B3[6]
    end
    subgraph R["merge 결과"]
        R1[1] --> R2[2] --> R3[3] --> R4[4] --> R5[5] --> R6[6]
    end
    A --> R
    B --> R

std::merge: 기본 사용

// g++ -std=c++17 -o merge_demo merge_demo.cpp && ./merge_demo
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> a = {1, 3, 5, 7};
    std::vector<int> b = {2, 4, 6, 8};
    std::vector<int> result(a.size() + b.size());

    std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());

    std::cout << "병합 결과: ";
    for (int x : result)
        std::cout << x << " ";
    std::cout << "\n";
    // 1 2 3 4 5 6 7 8

    return 0;
}

위 코드 설명: merge(시작1, 끝1, 시작2, 끝2, 출력시작)는 두 정렬된 범위를 병합해 출력 범위에 씁니다. 출력 범위 크기는 두 입력 크기의 합이어야 합니다.

std::merge: 커스텀 비교자

내림차순으로 정렬된 두 범위를 병합할 때는 비교자를 넘깁니다.

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> a = {7, 5, 3, 1};  // 내림차순
    std::vector<int> b = {8, 6, 4, 2};  // 내림차순
    std::vector<int> result(8);

    std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin(),
               std::greater<int>());
    // result: 8 7 6 5 4 3 2 1
}

std::inplace_merge: 제자리 병합

한 컨테이너 안에 두 개의 정렬된 구간이 연속으로 있을 때, 이를 하나로 합칠 때 std::inplace_merge를 사용합니다. 예: [1,3,5, 2,4,6] → [1,2,3,4,5,6].

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 3, 5, 7, 2, 4, 6, 8};
    // [0,4): 1,3,5,7 정렬됨
    // [4,8): 2,4,6,8 정렬됨

    std::inplace_merge(vec.begin(), vec.begin() + 4, vec.end());

    for (int x : vec) std::cout << x << " ";
    // 1 2 3 4 5 6 7 8

    return 0;
}

위 코드 설명: inplace_merge(시작, 중간, 끝)는 [시작, 중간)과 [중간, 끝) 두 정렬된 구간을 제자리에서 병합합니다. 병합 정렬(merge sort)의 병합 단계에서 사용됩니다.

병합 정렬에서 inplace_merge 활용

병합 정렬의 병합 단계에서 inplace_merge를 사용합니다. 재귀적으로 좌우를 정렬한 뒤 inplace_merge(begin, mid, end)로 합칩니다.

4. 집합 연산: set_union, set_intersection, set_difference

전제 조건: 두 범위가 정렬되어 있어야 함

std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference는 두 범위가 모두 정렬되어 있을 때만 올바르게 동작합니다. 정렬되지 않으면 잘못된 결과가 나옵니다.

flowchart TB
    subgraph ops["집합 연산"]
        U[set_union: A ∪ B]
        I[set_intersection: A ∩ B]
        D[set_difference: A - B]
        S[set_symmetric_difference: A △ B]
    end
    A["정렬된 A"] --> ops
    B["정렬된 B"] --> ops
    ops --> R["정렬된 결과"]

std::set_union: 합집합

두 정렬된 범위의 합집합을 출력합니다. 중복은 한 번만 포함됩니다.

// g++ -std=c++17 -o set_union_demo set_union_demo.cpp && ./set_union_demo
#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::vector<int> b = {3, 4, 5, 6, 7};
    std::vector<int> result;

    std::set_union(a.begin(), a.end(), b.begin(), b.end(),
                   std::back_inserter(result));

    std::cout << "합집합 (A ∪ B): ";
    for (int x : result) std::cout << x << " ";
    std::cout << "\n";
    // 1 2 3 4 5 6 7

    return 0;
}

위 코드 설명: set_union은 두 정렬된 범위의 합집합을 출력 반복자에 씁니다. back_inserter를 쓰면 결과 크기를 미리 알 필요가 없습니다. 결과도 정렬된 상태입니다.

std::set_intersection: 교집합

두 정렬된 범위의 교집합을 출력합니다.

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::vector<int> b = {3, 4, 5, 6, 7};
    std::vector<int> result;

    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                          std::back_inserter(result));

    std::cout << "교집합 (A ∩ B): ";
    for (int x : result) std::cout << x << " ";
    std::cout << "\n";
    // 3 4 5

    return 0;
}

std::set_difference: 차집합

첫 번째 범위에만 있고 두 번째에는 없는 원소를 출력합니다. A - B.

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::vector<int> b = {3, 4, 5, 6, 7};
    std::vector<int> result;

    std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                        std::back_inserter(result));

    std::cout << "차집합 (A - B): ";
    for (int x : result) std::cout << x << " ";
    std::cout << "\n";
    // 1 2

    return 0;
}

std::set_symmetric_difference: 대칭 차집합

두 집합 중 한쪽에만 있는 원소를 출력합니다. (A - B) ∪ (B - A).

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::vector<int> b = {3, 4, 5, 6, 7};
    std::vector<int> result;

    std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
                                   std::back_inserter(result));

    std::cout << "대칭 차집합 (A △ B): ";
    for (int x : result) std::cout << x << " ";
    std::cout << "\n";
    // 1 2 6 7

    return 0;
}

실전 예제: 두 사용자 그룹 비교

#include <algorithm>
#include <vector>
#include <string>
#include <iterator>
#include <iostream>

int main() {
    std::vector<std::string> group_a = {"alice", "bob", "charlie", "david"};
    std::vector<std::string> group_b = {"bob", "david", "eve", "frank"};

    std::sort(group_a.begin(), group_a.end());
    std::sort(group_b.begin(), group_b.end());

    std::vector<std::string> common, only_a, only_b;

    std::set_intersection(group_a.begin(), group_a.end(),
                          group_b.begin(), group_b.end(),
                          std::back_inserter(common));

    std::set_difference(group_a.begin(), group_a.end(),
                        group_b.begin(), group_b.end(),
                        std::back_inserter(only_a));

    std::set_difference(group_b.begin(), group_b.end(),
                        group_a.begin(), group_a.end(),
                        std::back_inserter(only_b));

    std::cout << "공통: "; for (auto& s : common) std::cout << s << " ";
    std::cout << "\nA에만: "; for (auto& s : only_a) std::cout << s << " ";
    std::cout << "\nB에만: "; for (auto& s : only_b) std::cout << s << " ";

    return 0;
}

실행 결과:

공통: bob david
A에만: alice charlie
B에만: eve frank

5. 힙 연산: make_heap, push_heap, pop_heap

힙이란?

힙(heap)은 “부모가 자식보다 크다(또는 작다)” 조건을 만족하는 완전 이진 트리입니다. std:: 힙 알고리즘은 최대 힙을 가정하며, vec[0]이 항상 최대값입니다. 우선순위 큐를 구현할 때 사용합니다.

flowchart TB
    subgraph heap["최대 힙 구조"]
        H0["9 (최대)"]
        H1["7"] --> H0
        H2["5"] --> H0
        H3["3"] --> H1
        H4["2"] --> H1
        H5["1"] --> H2
    end

std::make_heap: 힙 구성

범위를 힙 구조로 재배치합니다. vec[0]이 최대값이 됩니다.

// g++ -std=c++17 -o heap_demo heap_demo.cpp && ./heap_demo
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

    std::make_heap(vec.begin(), vec.end());

    std::cout << "힙 구성 후 vec[0] (최대): " << vec[0] << "\n";
    // 9

    return 0;
}

std::push_heap: 새 원소 추가

이미 힙인 범위의 맨 뒤에 원소를 push_back한 뒤, std::push_heap을 호출하면 힙 속성이 유지됩니다.

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {9, 5, 7, 3, 2, 1};  // 이미 힙
    std::make_heap(vec.begin(), vec.end());       // 확실히 힙으로

    vec.push_back(8);
    std::push_heap(vec.begin(), vec.end());

    std::cout << "push 8 후 최대: " << vec[0] << "\n";
    // 9 (8이 들어가도 9가 최대)

    return 0;
}

std::pop_heap: 최대값 제거

std::pop_heap은 최대값(vec[0])을 맨 뒤로 보내고, 나머지 구간을 다시 힙으로 만듭니다. 실제로 제거하려면 pop_back()을 호출합니다.

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {9, 7, 5, 3, 2, 1};
    std::make_heap(vec.begin(), vec.end());

    std::pop_heap(vec.begin(), vec.end());  // 9가 맨 뒤로
    int max_val = vec.back();
    vec.pop_back();

    std::cout << "제거된 최대값: " << max_val << "\n";  // 9
    std::cout << "새 최대값: " << vec[0] << "\n";       // 7

    return 0;
}

std::sort_heap: 힙 정렬

힙을 오름차순으로 정렬합니다. pop_heap을 반복하는 것과 동일한 효과입니다.

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    std::make_heap(vec.begin(), vec.end());

    std::sort_heap(vec.begin(), vec.end());

    for (int x : vec) std::cout << x << " ";
    // 1 1 2 3 4 5 6 9

    return 0;
}

주의: sort_heap 호출 후에는 더 이상 힙이 아닙니다. 다시 make_heap을 호출해야 힙 연산을 사용할 수 있습니다.

상위 K개 유지: 우선순위 큐 패턴

최소 힙(min-heap)으로 “상위 K개”를 유지합니다. heap[0]이 K번째로 큰 값이 되며, 새 값이 heap[0]보다 크면 교체합니다.

#include <algorithm>
#include <vector>
#include <iostream>

// 상위 K개만 유지 (최소 힙 사용: heap[0] = K번째로 큰 값)
void push_top_k(std::vector<int>& heap, int value, size_t k) {
    auto cmp = std::greater<int>{};
    if (heap.size() < k) {
        heap.push_back(value);
        std::push_heap(heap.begin(), heap.end(), cmp);
    } else if (value > heap[0]) {
        // heap[0]보다 크면 K번째로 큰 값 교체
        std::pop_heap(heap.begin(), heap.end(), cmp);
        heap.back() = value;
        std::push_heap(heap.begin(), heap.end(), cmp);
    }
}

int main() {
    std::vector<int> data = {5, 2, 9, 1, 7, 6, 3, 8, 4};
    std::vector<int> top3;

    for (int x : data) {
        push_top_k(top3, x, 3);
    }

    std::sort(top3.begin(), top3.end(), std::greater<int>());
    std::cout << "상위 3개: ";
    for (int x : top3) std::cout << x << " ";
    // 9 8 7

    return 0;
}

6. 완전한 고급 알고리즘 예제

예제 1: 로그 필터링 파이프라인 (partition + merge)

// g++ -std=c++17 -o log_pipeline log_pipeline.cpp && ./log_pipeline
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

struct LogEntry {
    std::string timestamp;
    int level;  // 0=DEBUG, 1=INFO, 2=WARN, 3=ERROR
    std::string message;
};

int main() {
    std::vector<LogEntry> logs = {
        {"10:00:01", 1, "User login"},
        {"10:00:02", 3, "Disk full"},
        {"10:00:03", 2, "High memory"},
        {"10:00:04", 1, "Request OK"},
        {"10:00:05", 3, "Connection failed"}
    };

    // 1. WARN(2) 이상을 앞으로 partition
    auto pivot = std::partition(logs.begin(), logs.end(),
         { return e.level >= 2; });

    std::cout << "=== 중요 로그 (WARN 이상) ===\n";
    for (auto it = logs.begin(); it != pivot; ++it)
        std::cout << it->timestamp << " [" << it->level << "] " << it->message << "\n";

    std::cout << "\n=== 일반 로그 ===\n";
    for (auto it = pivot; it != logs.end(); ++it)
        std::cout << it->timestamp << " [" << it->level << "] " << it->message << "\n";

    return 0;
}

예제 2: 두 정렬된 시퀀스 병합 (merge)

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> events_a = {100, 200, 300, 400};  // 타임스탬프
    std::vector<int> events_b = {150, 250, 350, 450};
    std::vector<int> merged(events_a.size() + events_b.size());

    std::merge(events_a.begin(), events_a.end(),
               events_b.begin(), events_b.end(),
               merged.begin());

    std::cout << "병합된 이벤트 시퀀스: ";
    for (int t : merged) std::cout << t << " ";
    std::cout << "\n";
    // 100 150 200 250 300 350 400 450

    return 0;
}

예제 3: 집합 연산 통합 (set_union, set_intersection, set_difference)

#include <algorithm>
#include <vector>
#include <iterator>
#include <iostream>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5, 6};
    std::vector<int> b = {4, 5, 6, 7, 8, 9};

    std::vector<int> u, i, d_a, d_b;

    std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(u));
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(i));
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(d_a));
    std::set_difference(b.begin(), b.end(), a.begin(), a.end(), std::back_inserter(d_b));

    std::cout << "A ∪ B: "; for (int x : u) std::cout << x << " "; std::cout << "\n";
    std::cout << "A ∩ B: "; for (int x : i) std::cout << x << " "; std::cout << "\n";
    std::cout << "A - B: "; for (int x : d_a) std::cout << x << " "; std::cout << "\n";
    std::cout << "B - A: "; for (int x : d_b) std::cout << x << " "; std::cout << "\n";

    return 0;
}

예제 4: 힙 기반 우선순위 큐 (make_heap, push_heap, pop_heap)

#include <algorithm>
#include <vector>
#include <iostream>

template <typename T>
class SimplePriorityQueue {
    std::vector<T> data_;
public:
    void push(const T& value) {
        data_.push_back(value);
        std::push_heap(data_.begin(), data_.end());
    }
    void pop() {
        std::pop_heap(data_.begin(), data_.end());
        data_.pop_back();
    }
    const T& top() const { return data_.front(); }
    bool empty() const { return data_.empty(); }
    size_t size() const { return data_.size(); }
};

int main() {
    SimplePriorityQueue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(20);
    pq.push(50);
    pq.push(40);

    std::cout << "우선순위 큐 (최대값 우선): ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << "\n";
    // 50 40 30 20 10

    return 0;
}

7. 자주 발생하는 에러와 해결법

에러 1: 정렬되지 않은 범위에 set_union/set_intersection 사용

증상: 교집합·합집합 결과가 잘못되거나 중복이 포함됩니다.

원인: 집합 연산은 두 범위가 정렬되어 있을 때만 올바르게 동작합니다.

// ❌ 잘못된 사용
std::vector<int> a = {5, 2, 8, 1};
std::vector<int> b = {3, 7, 2, 9};
std::vector<int> result;
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
               std::back_inserter(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));

에러 2: merge 출력 범위 크기 부족

증상: 버퍼 오버런, Segmentation fault.

원인: merge 결과 크기는 두 입력 크기의 합이어야 합니다.

// ❌ 잘못된 사용
std::vector<int> a = {1, 3, 5};
std::vector<int> b = {2, 4, 6};
std::vector<int> result(3);  // 크기 부족!
std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());

// ✅ 올바른 사용
std::vector<int> result(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());

에러 3: push_heap 전에 힙이 아닌 상태

증상: 힙 속성 깨짐, 최대값이 vec[0]이 아님.

원인: push_heap은 범위 [begin, end-1)이 이미 힙일 때, end-1 위치의 새 원소를 힙에 넣습니다. 순서를 바꾸면 안 됩니다.

// ❌ 잘못된 사용
vec.push_back(10);
std::sort(vec.begin(), vec.end());  // 힙 아님
std::push_heap(vec.begin(), vec.end());  // UB!

// ✅ 올바른 사용
vec.push_back(10);
std::push_heap(vec.begin(), vec.end());  // [begin, end-1)이 힙이어야 함

에러 4: partition pivot 해석 오류

증상: “참인 구간”과 “거짓인 구간”을 바꿔서 사용.

원인: partition 반환값은 거짓인 구간의 첫 반복자입니다. [begin, pivot)이 참, [pivot, end)가 거짓입니다.

// ❌ 잘못된 해석
auto pivot = std::partition(vec.begin(), vec.end(), is_even);
// [pivot, end)가 짝수라고 착각

// ✅ 올바른 해석
// [begin, pivot): is_even이 true인 원소 (짝수)
// [pivot, end): is_even이 false인 원소 (홀수)

에러 5: sort_heap 후 힙 연산 재사용

증상: push_heap/pop_heap 호출 시 잘못된 동작.

원인: sort_heap 호출 후 범위는 일반 정렬된 벡터가 되며, 더 이상 힙이 아닙니다.

// ❌ 잘못된 사용
std::make_heap(vec.begin(), vec.end());
std::sort_heap(vec.begin(), vec.end());
vec.push_back(100);
std::push_heap(vec.begin(), vec.end());  // UB! 힙 아님

// ✅ 올바른 사용
std::make_heap(vec.begin(), vec.end());
vec.push_back(100);
std::push_heap(vec.begin(), vec.end());
// 정렬이 필요하면 sort_heap 호출 (호출 후엔 힙 아님)

에러 6: inplace_merge 구간 잘못 지정

증상: 잘못된 병합 결과.

원인: inplace_merge(begin, mid, end)에서 [begin, mid)와 [mid, end)가 각각 정렬되어 있어야 합니다.

// ❌ 잘못된 사용
std::vector<int> vec = {1, 5, 3, 2, 6, 4};  // 정렬 안 됨
std::inplace_merge(vec.begin(), vec.begin() + 3, vec.end());

// ✅ 올바른 사용
std::vector<int> vec = {1, 3, 5, 2, 4, 6};  // [0,3), [3,6) 각각 정렬됨
std::inplace_merge(vec.begin(), vec.begin() + 3, vec.end());

8. 베스트 프랙티스

1. partition vs stable_partition 선택

  • 순서 무관: partition — 더 빠름, 메모리 적음
  • 순서 유지: stable_partition — 같은 조건 내 원래 순서 보존

2. merge vs inplace_merge 선택

  • 두 개의 별도 컨테이너: merge → 출력 범위에 쓰기
  • 한 컨테이너 내 두 구간: inplace_merge — 제자리 병합, 추가 메모리 사용

3. 집합 연산 전 정렬 필수

std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::set_intersection(...);

4. 힙 연산 순서

  • push: push_back → push_heap
  • pop: pop_heap → pop_back
  • make_heap: 기존 범위를 힙으로 만들 때

5. 출력 범위 크기 확인

merge, set_union 등은 출력 크기를 미리 알 수 있습니다. back_inserter를 쓰면 자동으로 확장되지만, reserve로 재할당을 줄이면 성능에 유리합니다.

std::vector<int> result;
result.reserve(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result));

9. 프로덕션 패턴

패턴 1: Quick Select (partition으로 K번째 원소 찾기)

std::nth_element와 유사하게, partition을 이용해 상대적 순서만 맞추고 K번째 원소를 찾을 수 있습니다. (실제로는 nth_element 사용 권장)

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {5, 2, 9, 1, 7, 6, 3, 8, 4};
    size_t k = 3;  // 4번째로 작은 원소 (0-based: 3)

    auto nth = vec.begin() + k;
    std::nth_element(vec.begin(), nth, vec.end());

    std::cout << "4번째로 작은 원소: " << vec[k] << "\n";

    return 0;
}

패턴 2: 정렬된 스트림 병합

여러 정렬된 시퀀스를 순차적으로 병합할 때 std::merge를 반복합니다.

std::vector<int> merge_all(const std::vector<std::vector<int>>& sorted_vecs) {
    if (sorted_vecs.empty()) return {};
    std::vector<int> result = sorted_vecs[0];
    for (size_t i = 1; i < sorted_vecs.size(); ++i) {
        std::vector<int> tmp(result.size() + sorted_vecs[i].size());
        std::merge(result.begin(), result.end(),
                   sorted_vecs[i].begin(), sorted_vecs[i].end(),
                   tmp.begin());
        result = std::move(tmp);
    }
    return result;
}

패턴 3: 태그 기반 필터링 (partition)

std::vector<Item> items = /* ... */;
auto pivot = std::partition(items.begin(), items.end(),
    [&tags](const Item& i) {
        return std::any_of(tags.begin(), tags.end(),
            [&i](const std::string& t) { return i.has_tag(t); });
    });
// [begin, pivot): 태그 일치, [pivot, end): 불일치

패턴 4: 힙 기반 Top-K 유지

template <typename T>
void maintain_top_k(std::vector<T>& heap, const T& value, size_t k,
                    std::function<bool(const T&, const T&)> cmp = std::less<T>{}) {
    if (heap.size() < k) {
        heap.push_back(value);
        std::push_heap(heap.begin(), heap.end(), cmp);
    } else if (cmp(value, heap.front())) {
        std::pop_heap(heap.begin(), heap.end(), cmp);
        heap.back() = value;
        std::push_heap(heap.begin(), heap.end(), cmp);
    }
}

패턴 5: 집합 연산 체이닝

// (A ∩ B) ∪ (C - D) 같은 복합 연산
std::vector<int> a = /* ... */, b = /* ... */, c = /* ... */, d = /* ... */;
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::sort(c.begin(), c.end());
std::sort(d.begin(), d.end());

std::vector<int> ab, cd, result;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(ab));
std::set_difference(c.begin(), c.end(), d.begin(), d.end(), std::back_inserter(cd));
std::set_union(ab.begin(), ab.end(), cd.begin(), cd.end(), std::back_inserter(result));

성능 요약

연산알고리즘복잡도비고
분할partitionO(n)순서 비보장
분할stable_partitionO(n)순서 유지
병합mergeO(n+m)두 정렬된 범위
병합inplace_mergeO(n)제자리
합집합set_unionO(n+m)정렬 필수
교집합set_intersectionO(n+m)정렬 필수
힙 구성make_heapO(n)
힙 삽입push_heapO(log n)
힙 삭제pop_heapO(log n)

10. 구현 체크리스트

  • partition: 반환 pivot이 [begin, pivot)=참, [pivot, end)=거짓인지 확인
  • merge: 두 입력 범위가 정렬되어 있는지 확인
  • merge: 출력 범위 크기가 입력 크기 합인지 확인
  • 집합 연산: set_union/set_intersection 전에 두 범위 정렬
  • 힙: push_heap 전 [begin, end-1)이 힙인지 확인
  • 힙: pop_heap 후 pop_back으로 실제 제거
  • sort_heap: 호출 후 더 이상 힙이 아님을 인지
  • inplace_merge: [begin, mid), [mid, end) 각각 정렬 여부 확인

정리

카테고리알고리즘용도
분할partition, stable_partition조건에 따라 앞뒤 분할
병합merge, inplace_merge정렬된 시퀀스 병합
집합set_union, set_intersection, set_difference, set_symmetric_difference합집합, 교집합, 차집합
힙make_heap, push_heap, pop_heap, sort_heap우선순위 큐, 상위 K개

핵심 원칙:

  1. partition pivot: [begin, pivot)=참, [pivot, end)=거짓
  2. merge·집합 연산: 입력이 정렬되어 있어야 함
  3. 힙: push_back → push_heap, pop_heap → pop_back 순서 준수
  4. 출력 범위 크기 항상 확인

자주 묻는 질문 (FAQ)

Q. partition과 filter(copy_if)의 차이는?

A. partition은 제자리에서 조건에 따라 앞뒤로 나누고, 원본을 수정합니다. copy_if는 조건에 맞는 원소만 새 컨테이너로 복사하고 원본은 그대로 둡니다. 원본을 바꿔도 되고 메모리를 아끼려면 partition, 원본 보존이 필요하면 copy_if를 사용하세요.

Q. std::priority_queue와 make_heap의 차이는?

A. std::priority_queue는 내부적으로 힙을 사용하는 컨테이너 어댑터입니다. make_heap+push_heap+pop_heap은 vector 등 기존 컨테이너를 힙으로 다룰 때 사용합니다. priority_queue가 더 간단하지만, 힙 전체를 정렬하거나 인덱스로 접근해야 할 때는 vector+힙 연산이 유리합니다.

Q. set_union과 단순 merge의 차이는?

A. merge는 두 정렬된 범위를 무조건 합칩니다. 같은 값이 있으면 둘 다 포함됩니다. set_union은 합집합이므로 같은 값은 한 번만 포함합니다. 중복 제거가 필요하면 set_union, 모든 원소를 시간순으로 합치면 merge를 사용하세요.

Q. 선행으로 읽으면 좋은 글은?

A. C++ STL 알고리즘 기초에서 sort·find·transform을 먼저 익히면 좋습니다. vector 기초와 컨테이너 선택도 참고하세요.

Q. 더 깊이 공부하려면?

A. cppreference — Algorithm library에서 partition, merge, set_*, heap 관련 함수의 시그니처와 요구사항을 확인하세요.

한 줄 요약: partition·merge·집합 연산·힙으로 데이터 분할·병합·집합 처리·우선순위 큐를 STL로 효율적으로 구현할 수 있습니다.

다음 글: C++ 프로파일링 기초. 시리즈 전체 목차는 C++ 시리즈 전체 목차에서 확인할 수 있습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

  • C++ STL 알고리즘 | sort·find·transform 람다와 함께 쓰기 (실전 패턴)
  • C++ vector 기초 완벽 가이드 | 초기화·연산·용량 관리와 실전 패턴
  • C++ 컨테이너 선택 가이드 | vector/list/deque/map/set 상황별 선택과 성능 최적화

이 글에서 다루는 키워드 (관련 검색어)

C++, STL, 알고리즘, partition, merge, set_union, set_intersection, heap, make_heap, push_heap 등으로 검색하시면 이 글이 도움이 됩니다.

관련 글

  • C++ 시리즈 전체 보기
  • C++ Adapter Pattern 완벽 가이드 | 인터페이스 변환과 호환성
  • C++ ADL |
  • C++ Aggregate Initialization |