C++ STL 고급 알고리즘: partition·merge·집합 연산·힙 연산 쓰는 법과 흔한 실수
partition은 조건에 맞는 원소를 앞으로 모으는 제자리 분할이고,merge와 집합 연산은 두 입력 범위가 이미 정렬되어 있다는 전제 위에서 동작합니다. 힙 연산은push_back뒤push_heap,pop_heap뒤pop_back이 한 쌍입니다. 14-1 알고리즘 기초를 먼저 보면 이어서 읽기 좋습니다.
들어가며: 조건 분할·병합·집합 연산이 필요한데 직접 구현했습니다
데이터를 조건에 따라 앞뒤로 나누거나, 정렬된 두 시퀀스를 하나로 합치거나, 두 집합의 교집합·합집합을 구할 때 직접 for문을 작성하다 보면 경계 조건 실수, 성능 이슈가 반복됩니다. C++ STL에는 partition, merge, 집합 연산(set_union, set_intersection 등), 힙 연산(make_heap, push_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> vec2 = {1, 2, 3, 4, 5, 6};
auto pivot = std::partition(vec2.begin(), vec2.end(),
[](int x) { return x % 2 == 0; });
// [begin, pivot): 짝수, [pivot, end): 홀수로그 분할, 리스트 병합, 그룹 비교, Top-K 스트리밍
시나리오 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)이 반복됩니다.
해결: 크기를 K로 제한한 최소 힙을 std::push_heap/std::pop_heap과 std::greater로 유지합니다. 힙의 맨 위가 현재 K번째로 큰 값이므로, 새 점수가 그보다 클 때만 교체하면 되고 원소 하나당 O(log K)입니다.
고급 알고리즘 분류 다이어그램
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(병합), 집합 연산, 힙 연산으로 분류됩니다. 각각 전제 조건(정렬 여부 등)이 있으므로 사용 전 확인이 필요합니다.
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(),
[](int x) { 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;
}실행 결과(libstdc++ 기준, 구현에 따라 순서가 다를 수 있음):
짝수 [begin, pivot): 8 2 6 4
홀수 [pivot, end): 5 3 7 1partition은 predicate가 참인 원소를 앞으로 모읍니다. 반환값 pivot은 “거짓인 구간의 시작”이므로, [begin, pivot)이 짝수, [pivot, end)가 홀수입니다. 순서는 보장되지 않습니다.
std::stable_partition: 순서 유지
같은 조건 내에서 원래 입력 순서를 유지해야 할 때 사용합니다. 예: “점수 60 이상을 앞으로, 같은 점수 내에서는 원래 순서 유지”.
#include <algorithm>
#include <vector>
#include <string>
#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(),
[](const Student& s) { 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 순서가 보존됩니다. 대신 내부적으로 임시 버퍼를 할당하며, 버퍼를 얻으면 O(n)이지만 할당에 실패하면 O(n log n)으로 동작합니다.
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(),
[](int x) { return x % 2 == 0; });
// pivot은 1을 가리킴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(시작, 중간, 끝)는 [시작, 중간)과 [중간, 끝) 두 정렬된 구간을 하나로 병합합니다. “제자리”라는 이름과 달리 내부적으로 임시 버퍼를 할당할 수 있으면 O(n)으로 병합하고, 할당에 실패하면 버퍼 없이 O(n log n)으로 병합합니다. 병합 정렬을 직접 구현할 때 재귀적으로 좌우를 정렬한 뒤 inplace_merge(begin, mid, end)로 합치는 식으로 쓸 수 있습니다.
집합 연산: 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: 합집합
두 정렬된 범위의 합집합을 출력합니다. 두 범위에 공통으로 있는 값은 한 번만 들어갑니다. 정확히는 같은 값이 A에 m번, B에 n번 있으면 결과에는 max(m, n)번 들어가고, 교집합(set_intersection)에서는 min(m, n)번 들어갑니다.
// 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힙 연산: 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개만 유지 (std::greater로 최소 힙: 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;
}로그 필터링 파이프라인과 힙 기반 우선순위 큐 예제
예제 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(),
[](const LogEntry& e) { 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;
}정렬 안 된 집합 연산, 힙 상태 깨짐, inplace_merge 구간 오류
에러 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());partition, merge, 힙 연산을 고르는 기준
partition vs stable_partition 선택
- 순서 무관:
partition— 더 빠름, 메모리 적음 - 순서 유지:
stable_partition— 같은 조건 내 원래 순서 보존
merge vs inplace_merge 선택
- 두 개의 별도 컨테이너:
merge→ 출력 범위에 쓰기 - 한 컨테이너 내 두 구간:
inplace_merge— 같은 컨테이너에 결과를 쓰며, 가능하면 내부적으로 임시 버퍼를 할당
집합 연산 전 정렬 필수
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::set_intersection(...);힙 연산 순서
push:push_back→push_heappop:pop_heap→pop_backmake_heap: 기존 범위를 힙으로 만들 때
출력 범위 크기 확인
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));Quick Select, 스트림 병합, Top-K 유지
패턴 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를 반복할 수 있습니다. 다만 이 방식은 앞에서 합친 결과를 매번 다시 복사하므로, 시퀀스가 k개이고 전체 원소가 N개면 최악 O(N·k)입니다. 시퀀스가 많다면 각 시퀀스의 현재 원소를 최소 힙에 넣고 하나씩 꺼내는 k-way 병합이 O(N log k)로 낫습니다.
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 유지
// Compare가 std::greater<T>면 최소 힙 → 가장 큰 K개를 유지
// Compare가 std::less<T>면 최대 힙 → 가장 작은 K개를 유지
template <typename T, typename Compare = std::greater<T>>
void maintain_top_k(std::vector<T>& heap, const T& value, size_t k,
Compare cmp = Compare{}) {
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));성능 요약
| 연산 | 알고리즘 | 복잡도 | 비고 |
|---|---|---|---|
| 분할 | partition | O(n) | 순서 비보장 |
| 분할 | stable_partition | O(n), 버퍼 없으면 O(n log n) | 순서 유지 |
| 병합 | merge | O(n+m) | 두 정렬된 범위 |
| 병합 | inplace_merge | O(n), 버퍼 없으면 O(n log n) | 같은 컨테이너 안의 두 구간 |
| 합집합 | set_union | O(n+m) | 정렬 필수 |
| 교집합 | set_intersection | O(n+m) | 정렬 필수 |
| 힙 구성 | make_heap | O(n) | |
| 힙 삽입 | push_heap | O(log n) | |
| 힙 삭제 | pop_heap | O(log n) | |
| 힙 정렬 | sort_heap | O(n log n) | 호출 후 힙이 아님 |
자주 묻는 질문 (FAQ)
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은 양쪽에 공통으로 있는 값을 한 번만 넣습니다(같은 값이 A에 m번, B에 n번이면 max(m, n)번). 두 범위의 중복을 합치려면 set_union, 모든 원소를 시간순으로 합치려면 merge를 사용하세요.
다음 글: C++ 프로파일링 기초. 시리즈 전체 목차는 C++ 시리즈 전체 목차에서 확인할 수 있습니다.