C++ 알고리즘 선택 완벽 가이드 | 상황별 STL·커스텀 알고리즘 선택법 [#54-1]

들어가며: 잘못된 알고리즘 선택의 대가

”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 알고리즘과 커스텀 알고리즘의 선택 기준을 알 수 있습니다.
• 흔한 실수를 피하고 성능을 최적화할 수 있습니다.

---

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([](auto x) { return x > 0; })
    | rv::transform([](auto x) { 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(), [](int a, int b) {
    return a <= b;  // 잘못됨! a == b일 때 true 반환하면 안 됨
});

해결법:

// ✅ 올바른 예 - 엄격한 약순서 (strict weak ordering)
// 실행 예제
std::sort(v.begin(), v.end(), [](int a, int b) {
    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(), [](int x) { 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, 프로파일링, 복잡도 표
프로덕션	헬퍼, 정책 패턴, 벤치마크, 메트릭, 폴백
핵심 원칙:

1. 측정 후 최적화 - 추측하지 말고 프로파일링
2. STL 우선 - 검증된 구현 활용
3. 복잡도 이해 - O(n) vs O(n log n) vs O(n²) 차이 인지
4. 전제 조건 준수 - 정렬, 비교자, 반복자 유효성

---

자주 묻는 질문 (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 기초 완벽 가이드 | 초기화·연산·용량 관리와 실전 패턴

---

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

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

• C++ STL 알고리즘 기초 | sort·find·count·transform·accumulate 가이드
• C++ STL 알고리즘 완벽 가이드 | sort·transform·accumulate [#54-1]
• C++ 정렬·검색 완벽 가이드 | 퀵소트·병합정렬·이진탐색·STL [실전]

---

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

C++, 알고리즘, STL, 성능최적화, 알고리즘선택 등으로 검색하시면 이 글이 도움이 됩니다.