상황별 C++ 알고리즘 고르기: STL로 충분한 경우와 직접 구현할 때, 흔한 성능 함정

작성 0xmote · 2026년 3월 16일 · 20분 읽기 · 수정 2026년 10월 9일 고급 개념

같은 결과를 내는 코드라도 어떤 알고리즘을 골랐느냐에 따라 연산 횟수가 자릿수 단위로 달라집니다. 정렬되지 않은 100만 개 원소에서 값을 찾으면 최악의 경우 100만 번 비교해야 하지만, 정렬된 배열에서 이진 검색을 하면 약 20번(log2 10^6 ≈ 20)이면 됩니다. 문제는 이런 차이가 데이터가 작은 개발 환경에서는 드러나지 않다가, 운영 데이터가 커진 뒤에야 나타난다는 점입니다.

이 글은 실무에서 자주 만나는 상황마다 어떤 STL 알고리즘이 맞는지, 그리고 그 알고리즘들이 요구하는 전제 조건을 어겼을 때 어떤 버그가 생기는지 정리합니다.

상황별 선택

같은 컨테이너에서 여러 번 검색

로그 레코드 100만 건에서 특정 user_id를 찾는 일이 한 번뿐이라면 std::find_if로 한 번 훑는 것이 가장 빠릅니다. 정렬은 그 자체로 O(n log n)이기 때문입니다. 하지만 ID 1000개를 각각 찾는다면 선형 검색은 최악의 경우 10억 번 비교가 됩니다. 이때는 한 번 정렬해 두고 이진 검색을 하거나, 해시 테이블을 만드는 편이 낫습니다.

std::vector<LogRecord> logs = loadLogs("access.log");
std::sort(logs.begin(), logs.end(),
          [](const LogRecord& a, const LogRecord& b) { return a.user_id < b.user_id; });

for (int id : ids_to_find) {
    // 같은 user_id의 레코드가 여러 개일 수 있으므로 구간 전체를 얻음
    auto [first, last] = std::equal_range(
        logs.begin(), logs.end(), id,
        [](const auto& lhs, const auto& rhs) {
            auto key = [](const auto& x) {
                if constexpr (std::is_same_v<std::decay_t<decltype(x)>, int>) return x;
                else return x.user_id;
            };
            return key(lhs) < key(rhs);
        });
    for (auto it = first; it != last; ++it) process(*it);
}

equal_range에 넘기는 비교자는 (원소, 값)과 (값, 원소) 두 방향으로 모두 호출되므로, 위처럼 양쪽 타입을 다 받아야 합니다. 이게 번거롭다면 lower_bound와 upper_bound를 각각 한 방향 비교자로 호출하거나, C++20의 std::ranges::equal_range(logs, id, {}, &LogRecord::user_id)처럼 프로젝션을 쓰면 간단합니다.

정렬과 해시 중 무엇을 고를지는 쓰임새에 달렸습니다. 정렬된 vector는 메모리가 연속이라 캐시 효율이 좋고, 범위 검색(user_id가 100~200 사이)도 할 수 있습니다. std::unordered_map<int, std::vector<LogRecord*>>는 조회당 평균 O(1)이지만 노드마다 할당이 일어나 메모리를 더 쓰고, 순서 기반 질의는 못 합니다. 데이터가 한 번 만들어진 뒤 바뀌지 않고 조회만 반복된다면 정렬된 vector가 대개 좋은 선택입니다.

첫 등장 순서를 유지하며 중복 제거

std::unique는 인접한 중복만 제거하므로, 일반적으로는 먼저 정렬해야 합니다. 그러면 원래 순서가 사라집니다. 첫 등장 순서를 지켜야 한다면 이미 본 값을 집합에 기록하며 한 번 훑습니다.

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) {   // 처음 본 값일 때만 true
        unique_events.push_back(x);
    }
}
// unique_events: {3, 1, 2}

순서가 상관없다면 sort 후 unique + erase가 추가 메모리 없이 동작하고, 데이터가 크면 해시 집합보다 빠른 경우가 많습니다.

부분 문자열 검색

std::string::find와 검색기 없이 쓰는 std::search(first, last, s_first, s_last)는 표준이 최악 O(n×m)을 허용하고, 주요 구현도 각 위치에서 패턴을 비교해 보는 방식입니다. 일반적인 텍스트에서는 첫 글자부터 금방 불일치가 나므로 거의 선형으로 동작하지만, 텍스트가 aaaa...a이고 패턴이 aaa...ab처럼 마지막 글자에서야 어긋나는 입력에서는 위치마다 패턴 길이만큼 비교하게 됩니다.

C++17부터는 std::search에 검색기(searcher)를 넘겨 다른 알고리즘을 쓸 수 있습니다.

#include <algorithm>
#include <functional>   // std::boyer_moore_horspool_searcher

std::string text = loadLargeText();
std::string pattern = loadPattern();
std::boyer_moore_horspool_searcher searcher(pattern.begin(), pattern.end());

for (auto it = text.begin();;) {
    it = std::search(it, text.end(), searcher);
    if (it == text.end()) break;
    processMatch(std::distance(text.begin(), it));
    ++it;   // 겹치는 매치도 찾음
}

Boyer-Moore 계열은 패턴을 전처리해, 불일치가 나면 여러 칸을 건너뜁니다. 자연어나 로그처럼 문자 종류가 다양한 텍스트에서 긴 패턴을 찾을 때 효과가 큽니다. 반대로 패턴이 몇 글자로 짧으면 전처리 비용 때문에 find가 더 빠른 경우가 흔하고, Horspool 변형은 최악의 경우 여전히 O(n×m)입니다. 입력을 통제할 수 없고 최악 시간을 O(n + m)으로 확실히 보장해야 한다면 KMP를 직접 구현하는 것이 맞습니다.

상위 K개만 필요할 때

100만 개 중 상위 10개가 필요하다고 전체를 정렬하면 필요 없는 일을 많이 하게 됩니다.

std::vector<int> data = loadMillionRecords();

// 상위 10개를 정렬된 상태로: 약 n log k 비교
std::partial_sort(data.begin(), data.begin() + 10, data.end(), std::greater<int>());

// 상위 10개를 순서 없이: 평균 O(n)
std::nth_element(data.begin(), data.begin() + 9, data.end(), std::greater<int>());
// data[9]는 10번째로 큰 값이고, data[0..8]은 그보다 크거나 같음

partial_sort는 앞쪽 K개로 힙을 만들고 나머지 원소를 하나씩 힙과 비교하므로 비교 횟수가 약 n log k입니다. nth_element는 퀵 셀렉트 계열로 평균 선형 시간에 K번째 원소를 제자리에 놓고, 그 앞에는 더 큰 값들이 순서 없이 모입니다. 상위 K개를 정렬된 상태로 원하면 nth_element 뒤에 앞쪽 K개만 sort해도 됩니다. 데이터가 스트림으로 들어와 전부 메모리에 올릴 수 없다면 크기 K의 최소 힙(std::priority_queue)을 유지하는 방법을 씁니다.

최댓값과 그 위치

std::max_element는 값이 아니라 이터레이터를 반환하므로 위치를 바로 얻을 수 있습니다. 최댓값을 구한 뒤 find로 다시 찾으면 두 번 훑게 됩니다.

auto it = std::max_element(v.begin(), v.end());   // 빈 범위면 v.end()
if (it != v.end()) {
    std::size_t idx = std::distance(v.begin(), it);
}

최솟값과 최댓값이 모두 필요하면 std::minmax_element가 한 번 순회로 둘 다 구하며, 비교 횟수도 따로 두 번 호출할 때(약 2n)보다 적은 약 1.5n입니다. 최댓값이 여러 개일 때 max_element는 첫 번째를, minmax_element의 최댓값은 마지막 것을 가리킨다는 차이가 있습니다.

조건 검사

“관리자가 한 명이라도 있는가”를 count_if(...) > 0으로 쓰면 첫 관리자를 찾은 뒤에도 끝까지 셉니다. any_of, all_of, none_of는 결과가 정해지는 순간 멈춥니다.

bool has_admin = std::any_of(users.begin(), users.end(),
                             [](const User& u) { return u.role == Role::Admin; });

정렬된 두 범위 합치기와 집합 연산

이미 정렬된 두 벡터를 이어 붙인 뒤 다시 정렬하면 O((n+m) log(n+m))이지만, std::merge는 두 범위를 앞에서부터 비교하며 O(n+m)에 합칩니다.

std::vector<int> a = {1, 3, 5}, b = {2, 4, 6};
std::vector<int> merged;
merged.reserve(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(merged));

std::vector<int> x = {1, 2, 3, 4}, y = {2, 4, 6};
std::vector<int> uni, diff, inter;
std::set_union(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(uni));          // {1,2,3,4,6}
std::set_difference(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(diff));    // {1,3}
std::set_intersection(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(inter)); // {2,4}

set_* 알고리즘도 입력이 같은 기준으로 정렬되어 있어야 합니다. 이름에 set이 들어가지만 std::set이 아니라 정렬된 범위에 대한 알고리즘입니다.

선택 기준 정리

flowchart TD
  A[검색이 필요한가] --> B{데이터가 정렬되어 있는가}
  B -->|예| C["lower_bound / equal_range: O(log n)"]
  B -->|아니오| D{같은 데이터에서 여러 번 검색하는가}
  D -->|아니오| E["find / find_if: O(n)"]
  D -->|예| F["정렬 후 이진 검색 또는 해시 테이블"]

하려는 일	알고리즘	비교·연산 횟수	메모리
한 번 찾기	`find`, `find_if`	O(n)	O(1)
정렬된 범위에서 찾기	`binary_search`, `lower_bound`, `upper_bound`, `equal_range`	O(log n)	O(1)
전체 정렬	`sort`	O(n log n) (C++11부터 최악도 보장)	O(log n)
같은 값의 원래 순서 유지	`stable_sort`	버퍼가 있으면 O(n log n), 없으면 O(n log² n)	O(n) 버퍼 시도
상위 K개, 정렬된 상태로	`partial_sort`	약 n log k	O(1)
K번째 값	`nth_element`	평균 O(n)	O(1)
정렬된 두 범위 병합	`merge`, `inplace_merge`	O(n+m) (`inplace_merge`는 버퍼가 없으면 O(n log n))	출력 범위 / 버퍼
조건 검사	`any_of`, `all_of`, `none_of`	최대 O(n), 조기 종료	O(1)
조건에 맞는 원소 제거	`remove_if` + `erase` (C++20 `std::erase_if`)	O(n)	O(1)
합계	`accumulate`, `reduce`	O(n)	O(1)

표준 라이브러리 알고리즘을 먼저 쓰는 이유는 단순히 “검증됐다”는 것만이 아닙니다. 루프를 직접 쓰면 그 코드가 무엇을 하는지 읽어야 알 수 있지만, partial_sort나 any_of는 이름만으로 의도가 드러납니다. 직접 구현이 필요한 경우는 표준에 없는 알고리즘(그래프 탐색, KMP 같은 특수 문자열 매칭), 도메인 지식으로 더 나은 복잡도를 얻을 수 있는 경우(값의 범위가 작아 계수 정렬이 가능한 경우 등), 그리고 프로파일링으로 표준 알고리즘이 병목임이 확인된 경우 정도입니다.

C++20 Ranges를 쓰면 여러 단계를 파이프로 연결해 쓸 수 있습니다. view는 지연 평가되므로 아래 코드는 take(10)이 10개를 채우면 더 이상 원소를 처리하지 않습니다.

#include <ranges>

auto result = data
    | std::views::filter([](int x) { return x > 0; })
    | std::views::transform([](int x) { return x * 2; })
    | std::views::take(10);

전제 조건을 어겨서 생기는 버그

정렬되지 않은 범위에서 이진 검색

binary_search, lower_bound, upper_bound, equal_range는 범위가 검색 기준에 대해 정렬(정확히는 분할)되어 있다고 가정합니다. 이 전제를 어기면 결과는 의미가 없고, 예외나 경고도 없습니다.

std::vector<int> v = {5, 2, 8, 1, 9};
bool found = std::binary_search(v.begin(), v.end(), 8);   // 전제 위반: 결과 신뢰 불가

std::sort(v.begin(), v.end());
found = std::binary_search(v.begin(), v.end(), 8);        // true

같은 문제가 “정렬 기준과 검색 기준이 다를 때”도 생깁니다. user_id로 정렬한 벡터에서 name으로 lower_bound를 하면 컴파일은 되지만 결과는 무의미합니다. 디버그 빌드에서는 libstdc++의 -D_GLIBCXX_DEBUG나 MSVC의 디버그 이터레이터가 이런 전제 위반 일부를 런타임에 검사해 줍니다.

엄격한 약순서를 만족하지 않는 비교자

sort, set, map 등은 비교자가 엄격한 약순서를 만족한다고 가정합니다. comp(a, a)는 항상 false여야 하고, comp(a, b)와 comp(b, c)가 참이면 comp(a, c)도 참이어야 하며, “둘 다 상대보다 작지 않음”이라는 동등 관계도 추이적이어야 합니다.

// 잘못된 예: a == b일 때 true
std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });

// 올바른 예
std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

// 여러 기준: std::tie로 사전식 비교
std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return std::tie(a.last, a.first, a.age) < std::tie(b.last, b.first, b.age);
});

<= 비교자로 std::sort를 호출하면 libstdc++의 구현은 경계 검사 없이 “자기보다 작지 않은 원소가 나올 때까지” 이동하는 루프를 쓰기 때문에, 같은 값이 많으면 범위 밖까지 읽어 크래시가 날 수 있습니다. 부동소수점 값에 NaN이 섞여 있을 때도 같은 문제가 생깁니다. NaN은 어떤 값과 비교해도 false라서 동등 관계의 추이성이 깨지기 때문입니다.

remove 후 erase 누락

std::vector<int> v = {1, 2, 3, 2, 4};
std::remove(v.begin(), v.end(), 2);                        // size는 여전히 5
v.erase(std::remove(v.begin(), v.end(), 2), v.end());      // erase-remove: {1, 3, 4}
std::erase(v, 2);                                          // C++20: 같은 일을 한 줄로

알고리즘은 이터레이터만 받기 때문에 컨테이너의 크기를 바꿀 수 없습니다. remove는 남길 원소를 앞으로 옮기고 새 끝을 반환할 뿐이며, 그 뒤의 원소들은 이동된 후의 유효하지만 지정되지 않은 값입니다. C++20의 std::erase, std::erase_if는 컨테이너별로 올바른 삭제를 해 주므로 이 실수를 원천적으로 막습니다.

순회 중 erase로 인한 이터레이터 무효화

// 잘못된 예: erase 후 it는 무효이므로 ++it가 정의되지 않은 동작
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) v.erase(it);
}

// 올바른 예 1: erase가 반환하는 다음 이터레이터 사용
for (auto it = v.begin(); it != v.end();) {
    if (*it % 2 == 0) it = v.erase(it);
    else ++it;
}

// 올바른 예 2: 한 번에 제거 (vector에서는 이쪽이 O(n)으로 더 빠름)
std::erase_if(v, [](int x) { return x % 2 == 0; });

vector에서 순회하며 하나씩 erase하면 지울 때마다 뒤쪽 원소를 앞으로 당기므로 최악 O(n²)입니다. 조건으로 여러 개를 지울 때는 erase_if(또는 erase-remove)를 쓰는 것이 정확성과 성능 양쪽에서 낫습니다.

출력 범위 크기 부족

출력 이터레이터를 받는 알고리즘(copy, transform, merge 등)은 출력 범위가 충분히 크다고 가정하고 그냥 씁니다.

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());   // 버퍼 오버런

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

출력 크기를 미리 알면 그 크기로 만들어 begin()을 넘기고, 모르면 back_inserter를 씁니다. back_inserter를 쓸 때도 최대 크기를 알면 reserve를 해 두어 재할당을 줄입니다.

부동소수점 누적

std::vector<float> vals(1'000'000, 0.1f);
float f = std::accumulate(vals.begin(), vals.end(), 0.0f);   // 100000과 크게 다름
double d = std::accumulate(vals.begin(), vals.end(), 0.0);   // 훨씬 정확

accumulate의 누적 타입은 세 번째 인자의 타입으로 정해집니다. 0.0f를 넘기면 float로 더하는데, 합이 커질수록 0.1f가 합의 유효 자릿수 아래로 밀려나 오차가 커집니다. 0(int)을 넘기면 소수점 아래가 매번 잘리는 더 심한 버그가 됩니다. 정확도가 중요하면 double로 누적하거나 Kahan 합산을 씁니다. std::reduce는 더하는 순서를 바꿀 수 있어 병렬화가 가능하지만, 그만큼 부동소수점 결과가 실행마다 미세하게 달라질 수 있습니다.

성능 확인과 병렬 알고리즘

측정

알고리즘 선택의 효과는 복잡도로 예측할 수 있지만, 실제 차이는 캐시, 분기 예측, 데이터 분포에 따라 달라집니다. 크기가 작을 때는 O(n) 선형 검색이 연속 메모리 덕분에 이진 검색이나 해시보다 빠른 경우도 흔합니다. 결정을 내리기 전에 실제 데이터 크기와 분포로 측정하는 것이 좋고, Google Benchmark 같은 도구가 반복 실행과 통계를 처리해 줍니다.

#include <benchmark/benchmark.h>
#include <algorithm>
#include <numeric>
#include <random>

static void BM_FullSortTop10(benchmark::State& state) {
    std::vector<int> base(state.range(0));
    std::iota(base.begin(), base.end(), 0);
    std::shuffle(base.begin(), base.end(), std::mt19937{42});
    for (auto _ : state) {
        auto v = base;   // 매 반복 같은 입력 (복사 비용도 측정에 포함됨)
        std::sort(v.begin(), v.end(), std::greater<int>());
        benchmark::DoNotOptimize(v.data());
    }
}
BENCHMARK(BM_FullSortTop10)->Range(1 << 10, 1 << 20);

static void BM_PartialSortTop10(benchmark::State& state) {
    std::vector<int> base(state.range(0));
    std::iota(base.begin(), base.end(), 0);
    std::shuffle(base.begin(), base.end(), std::mt19937{42});
    for (auto _ : state) {
        auto v = base;
        std::partial_sort(v.begin(), v.begin() + 10, v.end(), std::greater<int>());
        benchmark::DoNotOptimize(v.data());
    }
}
BENCHMARK(BM_PartialSortTop10)->Range(1 << 10, 1 << 20);
BENCHMARK_MAIN();

두 벤치마크가 같은 복사 비용을 포함하므로 차이는 정렬 방식에서 나옵니다. PauseTiming/ResumeTiming으로 준비 작업을 빼는 방법도 있지만, 그 호출 자체의 오버헤드가 작은 입력에서는 측정값을 왜곡할 수 있습니다.

병렬 실행 정책 (C++17)

#include <algorithm>
#include <execution>
#include <numeric>

std::sort(std::execution::par, v.begin(), v.end());
std::transform(std::execution::par, src.begin(), src.end(), dst.begin(), op);
double sum = std::reduce(std::execution::par, v.begin(), v.end(), 0.0);

병렬 정책은 원소 처리가 서로 독립적일 때만 써야 합니다. 람다 안에서 공유 변수를 수정하면 데이터 레이스입니다. par_unseq는 한 스레드 안에서도 여러 원소의 작업을 섞어(벡터화) 실행할 수 있어서, 원소 처리 중에 뮤텍스를 잡거나 메모리를 할당하면 데드락이나 정의되지 않은 동작이 됩니다.

병렬 알고리즘이 실제로 병렬로 도는지는 표준 라이브러리 구현에 따라 다릅니다. GCC의 libstdc++는 병렬 실행을 Intel TBB에 맡기므로 TBB를 설치하고 -ltbb로 링크해야 하며, 그렇지 않으면 링크 오류가 나거나 순차 실행되는 환경이 있습니다. MSVC는 자체 스레드 풀을 쓰고, libc++의 지원은 버전에 따라 제한적입니다. “par를 붙였는데 빨라지지 않는다”면 코드보다 빌드 설정을 먼저 확인해야 합니다. 또 원소가 수천 개 수준이면 작업을 나누는 비용이 처리 시간보다 커서 오히려 느려질 수 있으므로, 충분히 큰 데이터에서 측정해 보고 적용합니다.

메모리 부족과 정렬

std::sort는 제자리 정렬이라 추가 메모리를 거의 쓰지 않으므로, 정렬 중 bad_alloc을 걱정할 일은 사실상 없습니다(원소의 복사·이동 연산이 던지는 예외는 별개). 추가 버퍼를 쓰는 std::stable_sort도 버퍼를 얻지 못하면 예외를 던지지 않고 느린 제자리 알고리즘으로 전환합니다. 메모리 부족이 실제로 문제 되는 곳은 정렬할 데이터를 메모리에 모두 올리는 단계이며, 그때의 해결책은 데이터를 청크 단위로 정렬해 파일에 쓰고 병합하는 외부 정렬입니다.