C++ 알고리즘 선택 완벽 가이드 | 상황별 STL·커스텀 알고리즘 선택법 [#54-1]
![C++ 알고리즘 선택 완벽 가이드 | 상황별 STL·커스텀 알고리즘 선택법 [#54-1]](/og/s/cpp-series-54-1-algorithm-selection.webp)
이 글의 핵심
C++ 알고리즘 선택의 함정을 피하고, 상황에 맞는 최적의 알고리즘을 고르는 방법. 문제 시나리오, 선택 가이드, 흔한 실수, 성능 팁, 프로덕션 패턴. 알고리즘 선택은 C++ 개발에서 가장 쉽게 놓치기 쉬운 성능 함정입니다. 비유하면 "서울에서 부산까지 가는데 자전거를 타는 것"과 "KTX를 타는 것"의 차이입니다. 같은 목적지에 도달하더라도, 선택한 수단(알고리즘)에 따라 소요 시간이 수십 배, 수백 배 달라집니다.
들어가며: 잘못된 알고리즘 선택의 대가
”100만 건 로그를 처리하는데 10분이 걸려요”
알고리즘 선택은 C++ 개발에서 가장 쉽게 놓치기 쉬운 성능 함정입니다. 비유하면 “서울에서 부산까지 가는데 자전거를 타는 것”과 “KTX를 타는 것”의 차이입니다. 같은 목적지에 도달하더라도, 선택한 수단(알고리즘)에 따라 소요 시간이 수십 배, 수백 배 달라집니다.
잘못된 선택 vs 올바른 선택을 요약하면 아래와 같습니다.
flowchart TD
subgraph wrong[❌ 잘못된 선택]
W1[정렬되지 않은 벡터] --> W2[선형 검색 O(n)]
W2 --> W3[100만 번 비교]
W3 --> W4[10초 이상]
end
subgraph right[✅ 올바른 선택]
R1[정렬된 벡터] --> R2[이진 검색 O(log n)]
R2 --> R3[약 20번 비교]
R3 --> R4[마이크로초 단위]
end
이 글에서는 실제로 겪는 문제 시나리오부터 시작해, 상황별 알고리즘 선택 가이드, 자주 하는 실수, 성능 최적화 팁, 프로덕션에서 쓰는 패턴까지 단계별로 다룹니다.
이 글을 읽으면:
- 문제 상황에 맞는 알고리즘을 빠르게 선택할 수 있습니다.
- STL 알고리즘과 커스텀 알고리즘의 선택 기준을 알 수 있습니다.
- 흔한 실수를 피하고 성능을 최적화할 수 있습니다.
실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.
목차
1. 문제 시나리오
시나리오 1: 대용량 로그 파일에서 특정 ID 검색
상황: 100만 건의 로그 레코드에서 user_id == 12345인 항목을 찾아야 합니다.
잘못된 접근:
// ❌ 매번 선형 검색 O(n) - 100만 건이면 100만 번 비교
std::vector<LogRecord> logs = loadLogs("access.log");
for (const auto& log : logs) {
if (log.user_id == target_id) {
process(log);
break; // 첫 번째만 찾음
}
}문제점: 한 번만 검색하면 괜찮지만, 여러 ID를 반복 검색하면 O(n × 쿼리 수)가 됩니다. 1000개 ID를 검색하면 10억 번 비교가 발생합니다.
올바른 접근:
// ✅ 정렬 후 이진 검색 O(n log n) 초기화 + O(log n) per 쿼리
std::vector<LogRecord> logs = loadLogs("access.log");
std::sort(logs.begin(), logs.end(),
{
return a.user_id < b.user_id;
});
// 여러 ID 검색 시
for (int id : ids_to_find) {
auto it = std::lower_bound(logs.begin(), logs.end(), id,
{ return r.user_id < val; });
if (it != logs.end() && it->user_id == id) {
process(*it);
}
}결과: 초기 정렬 비용은 있지만, 쿼리가 많을수록 이진 검색이 압도적으로 유리합니다.
시나리오 2: 중복 제거 후 순서 유지
상황: 사용자 활동 스트림에서 중복을 제거하되, 첫 등장 순서를 유지해야 합니다.
잘못된 접근:
// ❌ std::unique는 인접 중복만 제거 - 정렬 필요 시 순서 파괴
std::vector<int> events = {3, 1, 2, 1, 3, 2};
std::sort(events.begin(), events.end()); // 순서 파괴됨!
events.erase(std::unique(events.begin(), events.end()), events.end());
// 결과: {1, 2, 3} - 원래 순서(3, 1, 2) 손실올바른 접근:
// ✅ std::unordered_set으로 첫 등장 순서 유지
std::vector<int> events = {3, 1, 2, 1, 3, 2};
std::unordered_set<int> seen;
std::vector<int> unique_events;
unique_events.reserve(events.size());
for (int x : events) {
if (seen.insert(x).second) { // 새로 삽입된 경우만
unique_events.push_back(x);
}
}
// 결과: {3, 1, 2} - 첫 등장 순서 유지시나리오 3: 부분 문자열 검색 (KMP vs 단순 검색)
상황: 1MB 텍스트에서 100자 패턴을 검색합니다.
잘못된 접근:
// ❌ 단순 검색 - 최악 O(n×m), 패턴이 반복되면 매우 느림
std::string text = loadLargeText();
std::string pattern = "aaa...aaa"; // 100개의 'a'
size_t pos = 0;
while ((pos = text.find(pattern, pos)) != std::string::npos) {
processMatch(pos);
++pos;
}문제점: text = "aaaa...aaaa" (100만 개 ‘a’), pattern = "aaa...a" (100개 ‘a’)일 때, 매 위치마다 100번 비교하고 실패하는 최악의 경우가 발생합니다.
올바른 접근:
// ✅ std::search 또는 KMP - O(n + m)
std::string text = loadLargeText();
std::string pattern = "aaa...aaa";
auto it = text.begin();
while (true) {
it = std::search(it, text.end(), pattern.begin(), pattern.end());
if (it == text.end()) break;
processMatch(std::distance(text.begin(), it));
++it;
}참고: std::search는 구현체에 따라 naive 또는 Boyer-Moore 등을 사용합니다. 패턴이 매우 길고 반복적이면 Boyer-Moore를 직접 구현하거나 전문 라이브러리를 쓰는 것이 좋습니다.
시나리오 4: Top-K 요소 추출
상황: 100만 건 중 상위 10개만 필요합니다.
잘못된 접근:
// ❌ 전체 정렬 O(n log n) - 10개만 필요한데 100만 건 정렬
std::vector<int> data = loadMillionRecords();
std::sort(data.begin(), data.end(), std::greater<int>());
for (int i = 0; i < 10; ++i) {
process(data[i]);
}올바른 접근:
// ✅ std::partial_sort 또는 std::nth_element - O(n log k) 또는 O(n)
std::vector<int> data = loadMillionRecords();
std::partial_sort(data.begin(), data.begin() + 10, data.end(), std::greater<int>());
for (int i = 0; i < 10; ++i) {
process(data[i]);
}
// 또는 순서 무관하면 nth_element가 더 빠름 O(n) 기대
std::nth_element(data.begin(), data.begin() + 9, data.end(), std::greater<int>());
// data[0..9]에 상위 10개 (순서는 보장 안 됨)시나리오 5: 범위 내 최대/최소와 인덱스 동시에
상황: 벡터에서 최대값과 그 인덱스를 함께 구해야 합니다.
잘못된 접근:
// ❌ 두 번 순회 - O(2n)
int max_val = *std::max_element(v.begin(), v.end());
size_t idx = std::find(v.begin(), v.end(), max_val) - v.begin();
// 최대값이 여러 개면 첫 번째만 찾음올바른 접근:
// ✅ max_element가 이터레이터 반환 - 인덱스 계산 O(n) 1회
auto it = std::max_element(v.begin(), v.end());
int max_val = *it;
size_t idx = std::distance(v.begin(), it);시나리오 6: 조건 만족하는지 검사 (all_of, any_of, none_of)
상황: 사용자 권한 목록에서 “관리자”가 한 명이라도 있는지 확인합니다.
잘못된 접근:
// ❌ count로 전체 순회 - short-circuit 없음
bool has_admin = std::count_if(users.begin(), users.end(),
{ return u.role == Role::Admin; }) > 0;올바른 접근:
// ✅ any_of - 첫 번째 만족 시 즉시 반환
bool has_admin = std::any_of(users.begin(), users.end(),
{ return u.role == Role::Admin; });시나리오 7: 두 컨테이너 합치기 (merge vs concat)
상황: 정렬된 두 벡터를 하나의 정렬된 벡터로 합쳐야 합니다.
잘못된 접근:
// ❌ concat 후 정렬 - O((n+m) log(n+m))
std::vector<int> result = a;
result.insert(result.end(), b.begin(), b.end());
std::sort(result.begin(), result.end());올바른 접근:
// ✅ std::merge - O(n + m), 이미 정렬된 입력 활용
std::vector<int> a = {1, 3, 5}, b = {2, 4, 6};
std::vector<int> result;
result.reserve(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result));
// result: {1, 2, 3, 4, 5, 6}시나리오 8: 정렬된 범위에서 구간 검색 (equal_range)
상황: 정렬된 벡터에서 값 42와 같은 모든 원소의 구간 [first, last)를 구합니다.
잘못된 접근:
// ❌ lower_bound + upper_bound 두 번 호출 - 비효율적이진 않지만
// equal_range가 한 번에 처리
auto lo = std::lower_bound(v.begin(), v.end(), 42);
auto hi = std::upper_bound(v.begin(), v.end(), 42);올바른 접근:
// ✅ equal_range - 한 번의 이진 탐색으로 [first, last) 반환
auto [lo, hi] = std::equal_range(v.begin(), v.end(), 42);
size_t count = std::distance(lo, hi); // 42의 개수
for (auto it = lo; it != hi; ++it) {
process(*it);
}시나리오 9: 정렬된 범위 집합 연산 (set_union, set_difference)
상황: 두 정렬된 사용자 ID 목록의 합집합/차집합을 구합니다.
// ✅ 정렬된 입력 전제
std::vector<int> a = {1, 2, 3, 4}, b = {2, 4, 6};
std::vector<int> union_result, diff_result;
std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(union_result));
// union_result: {1, 2, 3, 4, 6}
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(diff_result));
// diff_result: {1, 3} - a에만 있고 b에 없는 것2. 알고리즘 선택 완벽 가이드
2.1 검색 알고리즘 선택
flowchart TD
A[검색이 필요한가?] --> B{데이터 정렬 여부}
B -->|정렬됨| C[std::binary_search / lower_bound / upper_bound]
B -->|정렬 안 됨| D{검색 횟수}
D -->|1회| E[std::find - O(n)]
D -->|다수| F[정렬 후 이진검색 또는 std::unordered_set]
C --> G[O(log n)]
E --> H[O(n)]
F --> I[O(n log n) + O(log n)×쿼리]
| 상황 | 권장 알고리즘 | 복잡도 | 비고 |
|---|---|---|---|
| 정렬된 시퀀스, 존재 여부만 | std::binary_search | O(log n) | |
| 정렬된 시퀀스, 이터레이터 필요 | std::lower_bound, upper_bound | O(log n) | |
| 정렬 안 됨, 1회 검색 | std::find | O(n) | |
| 정렬 안 됨, 다수 검색 | 정렬 후 이진검색 또는 unordered_set | O(n log n) 초기화 | |
| 해시 가능 타입, 다수 검색 | std::unordered_set::find | O(1) 평균 |
코드 예시: 정렬된 범위에서 lower_bound
// 정렬된 벡터에서 42 이상인 첫 원소
std::vector<int> v = {1, 3, 5, 7, 9, 11};
auto it = std::lower_bound(v.begin(), v.end(), 42);
if (it != v.end()) {
std::cout << "첫 번째 42 이상: " << *it << "\n";
} else {
std::cout << "42 이상인 원소 없음\n";
}2.2 정렬 알고리즘 선택
flowchart TD
S[정렬이 필요한가?] --> T{요구사항}
T -->|전체 정렬| U{안정 정렬 필요?}
U -->|예| V[std::stable_sort - O(n log n)]
U -->|아니오| W[std::sort - O(n log n)]
T -->|상위 K개만| X[std::partial_sort - O(n log k)]
T -->|K번째 원소만| Y[std::nth_element - O(n)]
T -->|두 범위 병합| Z[std::merge - O(n+m)]
| 상황 | 권장 알고리즘 | 복잡도 | 비고 |
|---|---|---|---|
| 일반 정렬 | std::sort | O(n log n) | introsort, 대부분 최선 |
| 동일 값 순서 유지 | std::stable_sort | O(n log n) | 메모리 추가 사용 |
| 상위 K개만 | std::partial_sort | O(n log k) | K << n일 때 유리 |
| K번째만 필요 | std::nth_element | O(n) 평균 | 순서 보장 없음 |
| 이미 정렬된 두 범위 | std::inplace_merge | O(n) | 제자리 병합 |
2.3 변환·필터 알고리즘 선택
| 작업 | 권장 알고리즘 | 비고 |
|---|---|---|
| 각 원소 변환 | std::transform | 새 컨테이너에 저장 |
| 조건 만족하는 것만 복사 | std::copy_if | erase-remove 대신 |
| 조건 만족하는 것 제거 | std::remove_if + erase | 제자리 수정 |
| 누적 합/곱 | std::accumulate, std::reduce | C++17 reduce는 병렬 가능 |
| 부분합 | std::partial_sum |
예시: copy_if로 필터링
std::vector<int> nums = {1, 2, 3, 4, 5, 6};
std::vector<int> evens;
std::copy_if(nums.begin(), nums.end(), std::back_inserter(evens),
{ return x % 2 == 0; });
// evens: {2, 4, 6}2.4 수치·집계 알고리즘 선택
| 작업 | 권장 알고리즘 | 비고 |
|---|---|---|
| 합계 | std::accumulate | 순차, 부동소수점 주의 |
| 합계 (병렬) | std::reduce (C++17) | 부동소수점 순서 비결정 |
| 최대/최소 | std::max_element, min_element | 이터레이터 반환 |
| 개수 | std::count, std::count_if | |
| 모든/어떤 조건 | std::all_of, any_of, none_of | short-circuit |
2.5 STL vs 커스텀 알고리즘 결정
flowchart TD
D[알고리즘 필요] --> Q{STL에 있는가?}
Q -->|예| U[STL 사용]
Q -->|아니오| V{표준화 가능?}
V -->|예| W[Boost, range-v3 등 검토]
V -->|아니오| X[커스텀 구현]
U --> Y[검증됨, 최적화됨]
X --> Z[복잡도 분석 필수]
STL을 우선 쓰는 이유:
- 컴파일러 벤더별로 최적화됨
- 이터레이터 추상화로 컨테이너 독립
- 버그 가능성 적음
C++20 Ranges 활용 (가독성 향상):
#include <ranges>
namespace rv = std::ranges::views;
// 파이프 스타일 - 의도가 명확
auto result = data
| rv::filter( { return x > 0; })
| rv::transform( { return x * 2; })
| rv::take(10);커스텀을 고려하는 경우:
- 도메인 특화 (예: 지리 좌표 거리)
- STL에 없는 알고리즘 (예: A*, 특수 문자열 매칭)
- 극한 성능이 필요한 경우 (프로파일링 후)
3. 자주 발생하는 에러와 해결법
에러 1: 정렬되지 않은 범위에 binary_search 사용
증상: 결과가 잘못되거나, 찾아야 할 값이 있는데 못 찾음.
// ❌ 잘못된 예
std::vector<int> v = {5, 2, 8, 1, 9};
bool found = std::binary_search(v.begin(), v.end(), 8); // undefined behavior!해결법:
// ✅ 올바른 예
std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 8); // true규칙: binary_search, lower_bound, upper_bound, equal_range는 반드시 정렬된 범위에서만 사용합니다.
에러 2: 비교자(comparator)의 엄격한 약순서 위반
증상: 크래시, 무한 루프, 잘못된 정렬 결과.
// ❌ 잘못된 예 - a < b와 b < a가 동시에 true일 수 있음
std::sort(v.begin(), v.end(), {
return a <= b; // 잘못됨! a == b일 때 true 반환하면 안 됨
});해결법:
// ✅ 올바른 예 - 엄격한 약순서 (strict weak ordering)
std::sort(v.begin(), v.end(), {
return a < b; // a == b일 때 false
});규칙: 비교자는 comp(a, a) == false, comp(a, b) && comp(b, c) => comp(a, c) 등을 만족해야 합니다.
에러 3: remove/remove_if 후 erase 누락
증상: “삭제했는데” 크기가 그대로이거나, 끝에 쓰레기 값이 남음.
// ❌ 잘못된 예
std::vector<int> v = {1, 2, 3, 2, 4};
std::remove(v.begin(), v.end(), 2); // v는 {1, 3, 4, ?, ?} - size는 5!해결법:
// ✅ 올바른 예 - erase-remove idiom
std::vector<int> v = {1, 2, 3, 2, 4};
v.erase(std::remove(v.begin(), v.end(), 2), v.end());
// v: {1, 3, 4}, size: 3이유: std::remove는 실제 삭제가 아니라 “유지할 원소”를 앞으로 모을 뿐입니다. erase로 새 끝 이터레이터부터 end()까지 제거해야 합니다.
에러 4: 반복자 무효화 (iterator invalidation)
증상: 크래시, undefined behavior.
// ❌ 잘못된 예
std::vector<int> v = {1, 2, 3};
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it % 2 == 0) {
v.erase(it); // it 무효화! 다음 ++it가 UB
}
}해결법:
// ✅ 올바른 예 - erase-remove idiom
v.erase(std::remove_if(v.begin(), v.end(), { return x % 2 == 0; }), v.end());
// 또는 수동 루프 시 erase 반환값 사용
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) {
it = v.erase(it);
} else {
++it;
}
}에러 5: 출력 범위 크기 부족
증상: 버퍼 오버런, 크래시.
// ❌ 잘못된 예
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6};
std::vector<int> out(2); // 크기 부족!
std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin()); // UB해결법:
// ✅ 올바른 예 - back_inserter 사용
std::vector<int> out;
out.reserve(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));
// 또는 크기 미리 할당
std::vector<int> out(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());에러 6: accumulate와 부동소수점
증상: 합계가 예상과 다름 (부동소수점 누적 오차).
// ⚠️ 주의 - float 누적 시 오차
std::vector<float> vals(1000000, 0.1f);
float sum = std::accumulate(vals.begin(), vals.end(), 0.0f);
// sum != 100000.0 (오차 발생)해결법:
// ✅ Kahan summation 또는 double 사용
double sum = std::accumulate(vals.begin(), vals.end(), 0.0); // double로 누적
// 또는 C++17 std::reduce (병렬, 순서 비결정이지만 대량 합산 시 유리)
#include <numeric>
double sum = std::reduce(std::execution::par, vals.begin(), vals.end(), 0.0);에러 7: 정렬 기준과 검색 기준 불일치
증상: lower_bound로 찾은 결과가 기대와 다름.
// ❌ 잘못된 예 - 정렬은 user_id, 검색은 name
std::sort(users.begin(), users.end(),
{ return a.user_id < b.user_id; });
auto it = std::lower_bound(users.begin(), users.end(), "Alice",
{ return u.name < n; }); // UB!해결법: 정렬 기준과 검색 기준이 동일해야 합니다. user_id로 정렬했으면 user_id로 검색합니다.
// ✅ 올바른 예
int target_id = 12345;
auto it = std::lower_bound(users.begin(), users.end(), target_id,
{ return u.user_id < id; });에러 8: move 후 원본 사용
증상: std::move로 이동한 컨테이너를 다시 사용.
// ❌ 잘못된 예
std::vector<int> a = {1, 2, 3};
std::vector<int> b = std::move(a);
std::sort(a.begin(), a.end()); // UB - a는 빈 상태해결법: 이동 후 원본은 “유효하지만 unspecified” 상태입니다. 사용하지 않습니다.
// ✅ 올바른 예
std::vector<int> b = std::move(a);
// a는 더 이상 사용하지 않음4. 성능 최적화 팁
4.1 reserve로 재할당 최소화
// ❌ back_inserter만 사용 - 여러 번 재할당
std::vector<int> result;
std::copy_if(src.begin(), src.end(), std::back_inserter(result), pred);
// ✅ 크기 예측 가능하면 reserve
std::vector<int> result;
result.reserve(src.size()); // 최악의 경우 전부 복사
std::copy_if(src.begin(), src.end(), std::back_inserter(result), pred);4.2 람다 캡처 최소화
// ❌ 전체 캡처 - 불필요한 복사
std::sort(v.begin(), v.end(), [=](int a, int b) {
return a * factor < b * factor; // factor만 필요
});
// ✅ 필요한 것만 참조 캡처
int factor = 10;
std::sort(v.begin(), v.end(), [&factor](int a, int b) {
return a * factor < b * factor;
});4.3 정렬된 데이터는 범위 알고리즘 활용
// set_intersection, set_union, set_difference - 정렬된 입력 전제
std::vector<int> a = {1, 2, 3, 4}, b = {2, 4, 6};
std::vector<int> intersection;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(intersection));
// intersection: {2, 4}4.4 프로파일링 후 최적화
// 추측이 아닌 측정
#include <chrono>
auto start = std::chrono::high_resolution_clock::now();
myAlgorithm(data);
auto end = std::chrono::high_resolution_clock::now();
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "Elapsed: " << ms << " ms\n";원칙: 병목이 확인된 부분만 최적화합니다. “이게 느릴 것 같다”는 추측은 종종 틀립니다.
4.5 메모리 할당 줄이기
// ❌ 루프 안에서 임시 벡터 생성
for (const auto& item : items) {
std::vector<int> temp = process(item); // 매 반복마다 할당
use(temp);
}
// ✅ 루프 밖으로 이동
std::vector<int> temp;
temp.reserve(estimated_size);
for (const auto& item : items) {
temp.clear();
processInto(item, temp);
use(temp);
}4.6 알고리즘 복잡도 요약표
| 알고리즘 | 평균 | 최악 | 메모리 |
|---|---|---|---|
std::sort | O(n log n) | O(n log n) | O(log n) |
std::stable_sort | O(n log n) | O(n log n) | O(n) |
std::partial_sort | O(n log k) | O(n log k) | O(log n) |
std::nth_element | O(n) | O(n²) | O(log n) |
std::find | O(n) | O(n) | O(1) |
std::binary_search | O(log n) | O(log n) | O(1) |
std::merge | O(n+m) | O(n+m) | O(n+m) |
std::inplace_merge | O(n) | O(n log n) | O(1) 또는 O(n) |
4.7 알고리즘 선택 빠른 참조표
| ”이런 게 필요해요” | 추천 알고리즘 |
|---|---|
| 값이 있는지 1번만 확인 | std::find |
| 정렬된 범위에서 검색 | std::binary_search, lower_bound |
| 여러 번 검색 (정렬 가능) | 정렬 후 lower_bound |
| 여러 번 검색 (해시 가능) | std::unordered_set |
| 전체 정렬 | std::sort |
| 같은 값 순서 유지 | std::stable_sort |
| 상위 10개만 | std::partial_sort |
| 10번째 값만 | std::nth_element |
| 조건 만족하는 것 제거 | remove_if + erase |
| 조건 만족하는 것 복사 | std::copy_if |
| 각 원소 변환 | std::transform |
| 합계 | std::accumulate |
| 최대/최소 위치 | std::max_element, min_element |
| 모두/하나라도/전혀 | all_of, any_of, none_of |
4.8 데이터 크기별 권장 전략
| 데이터 크기 | 검색 | 정렬 | 비고 |
|---|---|---|---|
| ~100 | 선형 검색, 단순 정렬 | std::sort | 오버헤드가 더 클 수 있음 |
| ~10,000 | 이진 검색 고려 | std::sort | |
| ~1,000,000 | 반드시 이진/해시 | std::sort, partial_sort | reserve 필수 |
| 10,000,000+ | 인덱스/DB 검토 | 병렬 정렬, 외부 정렬 | 메모리 제약 확인 |
5. 프로덕션 패턴
5.1 알고리즘 선택 헬퍼
// 상황별 알고리즘 선택을 코드로 문서화
enum class SearchScenario {
SingleLookup,
MultipleLookup,
SortedRange
};
template<typename Container, typename Value>
auto selectSearchStrategy(const Container& c, const Value& v, SearchScenario scenario) {
if (scenario == SearchScenario::SortedRange) {
return std::lower_bound(std::begin(c), std::end(c), v);
}
if (scenario == SearchScenario::SingleLookup) {
return std::find(std::begin(c), std::end(c), v);
}
// MultipleLookup: 호출 전에 정렬 또는 set 구축 필요
throw std::logic_error("MultipleLookup requires pre-sorted or hash container");
}5.2 정책 기반 알고리즘 래퍼
template<typename Iterator, typename Predicate, typename Policy>
void filterAndProcess(Iterator first, Iterator last, Predicate pred, Policy policy) {
// Policy: RemoveInPlace, CopyToNew, CountOnly 등
if constexpr (std::is_same_v<Policy, RemoveInPlace>) {
auto new_end = std::remove_if(first, last, std::not_fn(pred));
// erase는 컨테이너 의존이므로 호출자가 처리
} else if constexpr (std::is_same_v<Policy, CopyToNew>) {
std::copy_if(first, last, policy.output(), pred);
}
}5.3 벤치마크용 알고리즘 비교
#include <benchmark/benchmark.h> // Google Benchmark
static void BM_Sort(benchmark::State& state) {
std::vector<int> v(state.range(0));
for (auto _ : state) {
state.PauseTiming();
std::iota(v.begin(), v.end(), 0);
std::reverse(v.begin(), v.end());
state.ResumeTiming();
std::sort(v.begin(), v.end());
}
}
BENCHMARK(BM_Sort)->Range(1 << 10, 1 << 20);
static void BM_PartialSortTop10(benchmark::State& state) {
std::vector<int> v(state.range(0));
for (auto _ : state) {
state.PauseTiming();
std::iota(v.begin(), v.end(), 0);
std::shuffle(v.begin(), v.end(), std::mt19937{42});
state.ResumeTiming();
std::partial_sort(v.begin(), v.begin() + 10, v.end(), std::greater<int>());
}
}
BENCHMARK(BM_PartialSortTop10)->Range(1 << 10, 1 << 20);5.4 로깅·모니터링과 연동
struct AlgorithmMetrics {
size_t comparisons = 0;
size_t moves = 0;
std::chrono::microseconds elapsed{0};
};
template<typename It>
AlgorithmMetrics sortWithMetrics(It first, It last) {
AlgorithmMetrics m;
auto start = std::chrono::high_resolution_clock::now();
std::sort(first, last);
m.elapsed = std::chrono::duration_cast<std::chrono::microseconds>(
std::chrono::high_resolution_clock::now() - start);
// 프로덕션: 로그 수집
logMetric("sort_comparisons", m.comparisons);
logMetric("sort_elapsed_us", m.elapsed.count());
return m;
}5.5 실패 시 폴백 전략
template<typename Container>
void robustSort(Container& c) {
try {
std::sort(c.begin(), c.end());
} catch (const std::bad_alloc&) {
// 메모리 부족 시 partial_sort로 상위만 처리
size_t k = std::min(c.size(), size_t(10000));
std::partial_sort(c.begin(), c.begin() + k, c.end());
logWarning("Fallback to partial_sort due to memory pressure");
}
}5.6 병렬 알고리즘 (C++17)
#include <execution>
#include <algorithm>
// 병렬 정렬 - 대용량 데이터 처리
std::sort(std::execution::par, v.begin(), v.end());
// 병렬 변환
std::transform(std::execution::par, src.begin(), src.end(), dst.begin(), op);
// 병렬 reduce - 부동소수점 순서 비결정
double sum = std::reduce(std::execution::par, v.begin(), v.end(), 0.0);주의: std::execution::par는 데이터 레이스가 없을 때만 사용합니다. 공유 상태 수정 시 std::execution::par_unseq는 더 위험합니다.
5.7 단위 테스트용 알고리즘 검증
#include <cassert>
#include <algorithm>
void testAlgorithmSelection() {
std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end());
assert(std::is_sorted(v.begin(), v.end()));
assert(std::binary_search(v.begin(), v.end(), 5));
auto [lo, hi] = std::equal_range(v.begin(), v.end(), 5);
assert(std::distance(lo, hi) >= 1);
}5.8 A/B 테스트용 알고리즘 비교
enum class AlgorithmVersion { Legacy, Optimized };
std::vector<Result> process(AlgorithmVersion version) {
if (version == AlgorithmVersion::Legacy) {
std::sort(data.begin(), data.end());
return legacySearch(data);
} else {
std::partial_sort(data.begin(), data.begin() + 100, data.end());
return optimizedSearch(data);
}
}6. 구현 체크리스트
알고리즘 선택 시
- 검색 횟수 확인 (1회 vs 다수)
- 데이터 정렬 여부 확인
- Top-K인지 전체 정렬인지 확인
- 순서 유지 필요 여부 (stable_sort)
- 메모리 제약 확인
코드 작성 시
-
binary_search/lower_bound전에 정렬 확인 - 비교자가 엄격한 약순서 만족하는지 확인
-
remove/remove_if후erase호출 - 출력 범위 크기 또는
back_inserter사용 - 반복자 무효화 주의 (erase in loop)
성능 검증 시
- 프로파일링으로 병목 확인
- 대표 데이터 크기로 벤치마크
-
reserve로 불필요한 재할당 방지 - 알고리즘 복잡도가 요구사항에 맞는지 확인
정리
| 항목 | 핵심 |
|---|---|
| 문제 시나리오 | 검색·정렬·필터·Top-K 등 상황별 잘못된/올바른 선택 |
| 선택 가이드 | 검색/정렬/변환/집계별 표와 플로우차트 |
| 흔한 에러 | 정렬 전제 위반, 비교자 오류, erase 누락, 반복자 무효화 |
| 성능 팁 | reserve, 프로파일링, 복잡도 표 |
| 프로덕션 | 헬퍼, 정책 패턴, 벤치마크, 메트릭, 폴백 |
핵심 원칙:
- 측정 후 최적화 - 추측하지 말고 프로파일링
- STL 우선 - 검증된 구현 활용
- 복잡도 이해 - O(n) vs O(n log n) vs O(n²) 차이 인지
- 전제 조건 준수 - 정렬, 비교자, 반복자 유효성
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 대용량 데이터 처리, 검색·정렬·필터링 로직 설계, 성능 크리티컬한 시스템에서 올바른 알고리즘 선택이 필수입니다. 로그 분석, 추천 시스템, 실시간 랭킹 등에서 바로 적용할 수 있습니다.
Q. 선행으로 읽으면 좋은 글은?
A. STL 알고리즘 기본, 정렬 알고리즘, 알고리즘 최적화를 순서대로 읽으면 좋습니다.
Q. 더 깊이 공부하려면?
A. cppreference - algorithm, 《알고리즘 설계》 교재, LeetCode/백준으로 복잡도 분석을 연습하세요.
한 줄 요약: 상황에 맞는 알고리즘을 선택하면 성능이 수십 배 달라집니다.
관련 글
- C++ STL 알고리즘 기초 완벽 가이드 | sort·find
- C++ STL 알고리즘 완벽 가이드 | sort·transform·accumulate [#54-1]
- C++ 알고리즘 |
- C++ vector 기초 완벽 가이드 | 초기화·연산·용량 관리와 실전 패턴