pkglog

C++ 알고리즘 최적화: Big-O로 병목 찾기, 공간-시간 트레이드오프, 메모이제이션

작성 · · 22분 읽기 · 수정 고급 실습

들어가며: 데이터가 늘면 느려지는 코드

테스트 데이터 수천 건에서는 문제없던 코드가 운영 데이터 수십만 건에서 갑자기 느려지는 경우의 상당수는 연산 횟수가 입력 크기의 제곱으로 늘어나는 알고리즘 때문입니다. 반대로 시간을 줄이겠다고 모든 중간 결과를 메모리에 쌓다가 메모리가 부족해지기도 합니다. 알고리즘 최적화는 시간복잡도와 공간복잡도를 읽고, 문제의 제약에 맞는 쪽으로 둘을 맞바꾸는 작업입니다. 이 글에서는 Big-O 분석에서 출발해 공간-시간 트레이드오프, 메모이제이션, 몇 가지 대표 문제의 최적화 과정과 STL 알고리즘을 쓸 때 흔한 실수를 다룹니다.

메모이제이션 예제가 std::optional을 쓰므로 C++17 이상으로 컴파일합니다.

느려지는 코드에서 자주 보는 상황

연산 횟수를 세어 보면 무엇이 문제인지 대부분 드러납니다. 아래의 시간 감각은 단순 연산을 초당 대략 10억 번(10⁹) 처리한다고 놓은 어림셈이며, 실제 값은 연산 종류와 캐시 상황에 따라 크게 달라집니다.

100만 개를 버블 정렬로 정렬하면 비교가 약 n²/2 = 5천억 번이라 수 분에서 수십 분이 걸립니다. std::sort는 O(n log n)이라 약 2천만 번 비교 수준이고, 실제로도 1초에 한참 못 미칩니다. 정렬 알고리즘 선택이 최적화의 첫 단계인 이유입니다.

정렬된 100만 개 목록에서 키 10만 개를 찾을 때 std::find로 선형 검색하면 최악의 경우 100만 × 10만 = 1천억 번 비교가 필요합니다. 목록이 이미 정렬되어 있으므로 std::binary_search나 std::lower_bound를 쓰면 키당 약 20번, 전체 약 200만 번이면 끝납니다. 같은 데이터라도 자료의 성질(정렬됨)을 활용하는 알고리즘을 고르는 것이 핵심입니다.

fib(n)을 그대로 재귀로 구현하면 같은 하위 문제를 반복해서 계산하므로 호출 수가 지수적으로 늘어, fib(40)만 해도 호출이 수억 번에 이릅니다. 결과를 캐시하는 메모이제이션으로 각 하위 문제를 한 번만 계산하면 O(n)이 됩니다.

std::vector에서 중복을 제거하면서 원소마다 결과 벡터를 std::find로 검사하면 O(n²)이라, 100만 건이면 비교가 수천억 번에 이릅니다. std::sort + std::unique + erase로 O(n log n), 또는 std::unordered_set으로 평균 O(n)에 처리할 수 있습니다.

메모리 쪽에서는 길이 n인 두 수열에 대해 n × m 크기의 2차원 DP 테이블을 만들다가 메모리가 부족해지는 경우가 흔합니다. 많은 DP는 바로 이전 행만 참조하므로, 행 두 개만 번갈아 쓰는 롤링 배열로 O(n × m)을 O(min(n, m)) 공간으로 줄일 수 있습니다.

flowchart TB
    subgraph input[입력]
        N[데이터 크기 n]
        Q[쿼리 횟수]
        M[메모리 제한]
    end
    subgraph decision[의사결정]
        D1{n이 작음?\n< 10^4}
        D2{정렬 가능?}
        D3{중복 계산?}
    end
    subgraph result[선택]
        R1[브루트포스 OK]
        R2[정렬 + 이진검색]
        R3[메모이제이션]
        R4[공간 압축]
    end
    N --> D1
    D1 -->|Yes| R1
    D1 -->|No| D2
    D2 -->|Yes| R2
    D2 -->|No| D3
    D3 -->|Yes| R3
    D3 -->|No| R4

Big-O로 시간·공간 복잡도 읽기

Big-O 표기법

Big-O는 입력 크기 n이 커질 때 연산 횟수나 메모리 사용량이 얼마나 빨리 늘어나는지의 상한을 나타냅니다. 상수 배와 낮은 차수 항은 무시합니다. 흔히 최악의 경우를 Big-O로 말하지만, 평균 경우(unordered_map 조회의 평균 O(1))나 분할 상환(vector::push_back의 분할 상환 O(1))처럼 어떤 경우를 말하는지 함께 밝혀야 정확합니다.

// O(1): n과 무관
int get_first(const std::vector<int>& vec) {
    return vec.empty() ? 0 : vec[0];
}
// O(n): n에 비례
long long sum(const std::vector<int>& vec) {
    long long s = 0;
    for (int x : vec) s += x;
    return s;
}
// O(n²): 이중 루프
void bubble_sort(std::vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i)
        for (size_t j = 0; j + 1 < vec.size() - i; ++j)
            if (vec[j] > vec[j + 1])
                std::swap(vec[j], vec[j + 1]);
}
// O(log n): 탐색 범위를 매번 절반으로 줄임
bool contains_sorted(const std::vector<int>& vec, int target) {
    size_t lo = 0, hi = vec.size();
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (vec[mid] < target) lo = mid + 1;
        else if (vec[mid] > target) hi = mid;
        else return true;
    }
    return false;
}

시간복잡도 비교표

복잡도n=1,000n=1,000,000대표 예시
O(1)11배열 인덱싱, 해시 조회
O(log n)1020이진 검색, 균형 트리
O(n)1,0001,000,000선형 스캔, 단일 루프
O(n log n)10,00020,000,000병합/퀵 정렬
O(n²)1,000,0001조버블 정렬, 이중 루프
O(2^n)약 10^301계산 불가단순 재귀 피보나치

n이 1,000일 때 O(n²)은 100만 번이라 충분히 빠르지만, n이 1,000배가 되면 연산은 100만 배가 됩니다. 작은 입력에서 문제가 드러나지 않는 이유가 이것이고, 테스트 데이터 크기를 운영 데이터에 가깝게 맞춰야 하는 이유이기도 합니다.

공간복잡도

공간복잡도는 입력 자체를 제외하고 알고리즘이 추가로 쓰는 보조 공간을 봅니다.

// O(1) 보조 공간 (빈 벡터는 호출자가 걸러야 함)
int max_value(const std::vector<int>& vec) {
    int m = vec[0];
    for (size_t i = 1; i < vec.size(); ++i)
        if (vec[i] > m) m = vec[i];
    return m;
}
// O(n) 보조 공간: 결과 벡터
std::vector<int> doubled(const std::vector<int>& vec) {
    std::vector<int> result(vec.size());
    for (size_t i = 0; i < vec.size(); ++i)
        result[i] = vec[i] * 2;
    return result;
}
// O(n·m) 보조 공간: LCS용 2차원 DP 테이블
std::vector<std::vector<int>> lcs_table(size_t n, size_t m) {
    return std::vector<std::vector<int>>(n + 1, std::vector<int>(m + 1, 0));
}

재귀 함수의 호출 스택도 보조 공간에 포함됩니다. 깊이 n의 재귀는 O(n) 스택을 쓰고, n이 수십만을 넘으면 스택 오버플로가 날 수 있습니다.

반복 제거·조기 종료·자료구조 교체

불필요한 반복 제거

같은 데이터를 여러 번 순회해야 하는 계산은 한 번의 루프로 합칠 수 있습니다. 복잡도는 둘 다 O(n)으로 같지만, 데이터가 캐시보다 크면 메모리에서 두 번 읽는 비용이 실제 차이를 만듭니다.

// 두 번 순회
std::pair<long long, int> sum_and_count_evens_2pass(const std::vector<int>& vec) {
    long long sum = 0;
    for (int x : vec) sum += x;
    int count = 0;
    for (int x : vec) if (x % 2 == 0) ++count;
    return {sum, count};
}
// 한 번 순회
std::pair<long long, int> sum_and_count_evens(const std::vector<int>& vec) {
    long long sum = 0;
    int count = 0;
    for (int x : vec) {
        sum += x;
        if (x % 2 == 0) ++count;
    }
    return {sum, count};
}

조기 종료

답이 정해지는 즉시 반환하면 평균 연산 수가 줄어듭니다. 최악의 경우 복잡도는 같지만, 조건을 만족하는 원소가 앞쪽에 있을 가능성이 높으면 차이가 큽니다. 표준 알고리즘으로는 std::any_of, std::find_if가 같은 일을 합니다.

bool contains_negative(const std::vector<int>& vec) {
    for (int x : vec)
        if (x < 0) return true;   // 첫 음수에서 종료
    return false;
}
// 같은 의미: std::any_of(vec.begin(), vec.end(), [](int x) { return x < 0; })

자료구조 선택

연산vector (정렬 안 됨)set/mapunordered_set/map
검색O(n)O(log n)평균 O(1), 최악 O(n)
삽입끝에 분할 상환 O(1)O(log n)평균 O(1)
순서 유지직접 정렬항상 정렬됨없음
#include <set>
#include <unordered_set>
// 존재 여부만 빠르게 확인
std::unordered_set<int> ids(data.begin(), data.end());
if (ids.contains(target)) { /* ... */ }   // C++20, 이전에는 count()
// 정렬된 순서 유지 + 범위 검색
std::set<int> sorted_ids(data.begin(), data.end());
auto it = sorted_ids.lower_bound(target);

표의 복잡도가 같아도 상수가 다릅니다. 원소가 수십 개 정도라면 정렬된 vector의 선형 또는 이진 검색이 노드 기반 set이나 해시 테이블보다 빠른 경우가 많습니다. 메모리가 연속이라 캐시 효율이 좋고, 노드 할당과 해시 계산이 없기 때문입니다. 한 번 만들고 여러 번 검색하는 데이터라면 정렬된 vector + lower_bound도 좋은 선택입니다.

메모이제이션과 해시로 공간을 내주고 시간을 얻기

메모리를 더 쓰면 시간을 줄일 수 있고, 계산 순서를 바꾸거나 시간을 조금 더 쓰면 메모리를 줄일 수 있습니다.

flowchart TB
    subgraph trade[트레이드오프]
        A[메모리 ↑] --> B[시간 ↓]
        C[메모리 ↓] --> D[시간 ↑ 또는 같음]
    end
    E[메모이제이션] --> A
    F[해시 테이블] --> A
    G[DP 롤링 배열] --> C
    H[재계산] --> C

메모이제이션: 피보나치

#include <functional>
#include <optional>
#include <vector>
// 지수 시간: 같은 하위 문제를 반복 계산
long long fib_naive(int n) {
    if (n <= 1) return n;
    return fib_naive(n - 1) + fib_naive(n - 2);
}
// 메모이제이션: O(n) 시간, O(n) 공간(캐시 + 재귀 스택)
long long fib_memo(int n) {
    if (n <= 1) return n;
    std::vector<std::optional<long long>> cache(n + 1);
    cache[0] = 0;
    cache[1] = 1;
    std::function<long long(int)> fib = [&](int k) -> long long {
        if (cache[k]) return *cache[k];
        cache[k] = fib(k - 1) + fib(k - 2);
        return *cache[k];
    };
    return fib(n);
}
// 반복: O(n) 시간, O(1) 공간
long long fib_iter(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

단순 재귀의 호출 수는 fib(n) 자체에 비례해 약 1.618ⁿ으로 늘어납니다. 메모이제이션은 각 k에 대해 한 번만 계산하므로 O(n)이 되고, 반복문 버전은 직전 두 값만 필요하다는 점을 이용해 공간까지 O(1)로 줄입니다. long long은 fib(92)까지만 담을 수 있으므로 그보다 큰 n에는 큰 수 타입이나 모듈러 연산이 필요합니다. 재귀 메모이제이션은 깊이 n만큼 스택을 쓰므로, n이 크면 반복문 버전(bottom-up)이 안전합니다.

롤링 배열: DP 공간 줄이기

0/1 배낭 문제의 기본 DP는 dp[i][w](i번째 물건까지 고려, 용량 w)로 O(n·W) 공간을 씁니다. 각 행은 바로 위 행만 참조하므로 1차원 배열 하나로 줄일 수 있습니다.

// 0/1 배낭: O(n·W) 시간, O(W) 공간
int knapsack_1d(const std::vector<int>& weights,
                const std::vector<int>& values, int W) {
    std::vector<int> dp(W + 1, 0);
    for (size_t i = 0; i < weights.size(); ++i) {
        // 용량을 큰 쪽에서 작은 쪽으로 순회해야 dp[w - weights[i]]가 아직 이전 행 값
        for (int w = W; w >= weights[i]; --w) {
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

순회 방향이 핵심입니다. 작은 용량부터 순회하면 같은 물건으로 갱신된 값을 다시 읽게 되어 물건을 여러 번 넣는 무한 배낭 문제가 됩니다. 대신 1차원으로 줄이면 어떤 물건을 골랐는지 역추적할 정보가 사라지므로, 선택 목록까지 필요하다면 2차원 테이블이나 별도 기록이 필요합니다.

해시 테이블로 검색 가속

#include <unordered_map>
#include <vector>
// 두 수의 합: 이중 루프 O(n²) → 해시 평균 O(n)
std::pair<int, int> two_sum(const std::vector<int>& vec, int target) {
    std::unordered_map<int, size_t> seen;   // 값 → 인덱스
    for (size_t i = 0; i < vec.size(); ++i) {
        int complement = target - vec[i];
        if (auto it = seen.find(complement); it != seen.end())
            return {static_cast<int>(it->second), static_cast<int>(i)};
        seen[vec[i]] = i;
    }
    return {-1, -1};
}

지금까지 본 값을 해시에 저장하는 O(n) 메모리를 내주고, 원소마다 나머지 전체를 훑던 O(n) 검색을 평균 O(1) 조회로 바꿉니다. target - vec[i]는 값이 int 범위 끝에 가까우면 오버플로할 수 있으므로, 입력 범위가 넓다면 long long으로 계산합니다.

Kadane·투 포인터·LCS로 보는 최적화 과정

최대 부분 배열 합 (Kadane 알고리즘)

연속된 부분 배열 중 합이 최대인 값을 구합니다. 모든 구간을 다 보면 O(n³), 누적합으로 O(n²)입니다.

// g++ -std=c++17 -o kadane kadane.cpp && ./kadane
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
// O(n²): 시작점마다 끝점을 늘려 가며 합 갱신
int max_subarray_naive(const std::vector<int>& vec) {
    int best = INT_MIN;
    for (size_t i = 0; i < vec.size(); ++i) {
        int sum = 0;
        for (size_t j = i; j < vec.size(); ++j) {
            sum += vec[j];
            best = std::max(best, sum);
        }
    }
    return best;
}
// O(n): Kadane 알고리즘
int max_subarray_kadane(const std::vector<int>& vec) {
    if (vec.empty()) return 0;
    int current = vec[0];
    int best = vec[0];
    for (size_t i = 1; i < vec.size(); ++i) {
        current = std::max(vec[i], current + vec[i]);
        best = std::max(best, current);
    }
    return best;
}
int main() {
    std::vector<int> vec = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    std::cout << "Naive: " << max_subarray_naive(vec) << "\n";
    std::cout << "Kadane: " << max_subarray_kadane(vec) << "\n";
}
Naive: 6
Kadane: 6

Kadane은 “i에서 끝나는 최대 부분 배열 합”을 current로 유지합니다. 이전까지의 합이 음수라면 이어 붙이는 것보다 i에서 새로 시작하는 편이 낫기 때문에 max(vec[i], current + vec[i])가 됩니다. 이렇게 “끝 위치를 고정한 부분 문제”로 바꾸면 O(n²)개의 구간을 보지 않고 한 번의 순회로 답을 얻습니다. 원소가 모두 음수여도 가장 큰 원소 하나를 답으로 돌려준다는 점도 확인할 만합니다.

두 수의 합 → 세 수의 합 (정렬 + 투 포인터)

#include <algorithm>
#include <vector>
// 두 수의 합: 정렬 O(n log n) + 투 포인터 O(n)
std::pair<int, int> two_sum_sorted(std::vector<int> vec, int target) {
    if (vec.size() < 2) return {-1, -1};   // size() - 1이 언더플로하지 않도록
    std::sort(vec.begin(), vec.end());
    size_t lo = 0, hi = vec.size() - 1;
    while (lo < hi) {
        int sum = vec[lo] + vec[hi];
        if (sum == target) return {vec[lo], vec[hi]};
        if (sum < target) ++lo;
        else --hi;
    }
    return {-1, -1};
}
// 세 수의 합: 정렬 후 원소 하나를 고정하고 나머지에서 투 포인터, O(n²)
std::vector<int> three_sum(std::vector<int> vec, int target) {
    std::sort(vec.begin(), vec.end());
    for (size_t i = 0; i + 2 < vec.size(); ++i) {
        size_t lo = i + 1, hi = vec.size() - 1;
        int remain = target - vec[i];
        while (lo < hi) {
            int sum = vec[lo] + vec[hi];
            if (sum == remain) return {vec[i], vec[lo], vec[hi]};
            if (sum < remain) ++lo;
            else --hi;
        }
    }
    return {};
}

정렬된 배열에서 양 끝 합이 목표보다 작으면 왼쪽을, 크면 오른쪽을 옮기는 것만으로 모든 후보 쌍을 빠짐없이 배제할 수 있어 O(n)이 됩니다. 해시 버전(평균 O(n))과 비교하면 정렬 비용이 들고 원래 인덱스를 잃지만, 추가 메모리가 거의 없고 세 수의 합처럼 확장하기 쉽습니다.

LCS 공간 최적화

두 문자열의 최장 공통 부분 수열 길이는 2차원 DP로 O(n·m) 시간과 공간이 듭니다. 각 행이 바로 이전 행만 참조하므로, 짧은 쪽 길이만큼의 행 두 개로 공간을 줄일 수 있습니다.

#include <algorithm>
#include <string>
#include <vector>
// O(n·m) 시간, O(n·m) 공간
int lcs_full(const std::string& a, const std::string& b) {
    size_t n = a.size(), m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (size_t i = 1; i <= n; ++i)
        for (size_t j = 1; j <= m; ++j)
            dp[i][j] = (a[i-1] == b[j-1]) ? dp[i-1][j-1] + 1
                                          : std::max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}
// O(n·m) 시간, O(min(n, m)) 공간: 행 두 개를 번갈아 사용
int lcs_compressed(const std::string& a, const std::string& b) {
    if (a.size() < b.size()) return lcs_compressed(b, a);   // b를 짧은 쪽으로
    size_t n = a.size(), m = b.size();
    std::vector<int> prev(m + 1, 0), curr(m + 1, 0);
    for (size_t i = 1; i <= n; ++i) {
        for (size_t j = 1; j <= m; ++j)
            curr[j] = (a[i-1] == b[j-1]) ? prev[j-1] + 1 : std::max(prev[j], curr[j-1]);
        std::swap(prev, curr);
    }
    return prev[m];
}

두 문자열이 각각 10만 자라면 전체 테이블은 int 100억 개, 약 40GB로 만들 수조차 없지만, 압축 버전은 약 800KB면 됩니다. 시간복잡도는 그대로이고, 길이만 필요하고 실제 부분 수열은 필요 없을 때 쓸 수 있는 방법입니다. 부분 수열 자체가 필요하면서 공간도 줄여야 한다면 Hirschberg 알고리즘이 O(min(n, m)) 공간에서 복원까지 해 줍니다.

로그 분석 파이프라인

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <string>
#include <vector>
struct LogEntry {
    std::string timestamp;
    int level;
    std::string message;
};
void analyze_logs(std::vector<LogEntry>& logs) {
    if (logs.empty()) return;
    // 1. 타임스탬프 정렬 O(n log n) (ISO 8601 형식이면 문자열 비교가 시간 순서와 같음)
    std::sort(logs.begin(), logs.end(),
              [](const LogEntry& a, const LogEntry& b) { return a.timestamp < b.timestamp; });
    // 2. ERROR(레벨 3 이상) 개수 O(n)
    auto errors = std::count_if(logs.begin(), logs.end(),
                                [](const LogEntry& e) { return e.level >= 3; });
    // 3. WARN(레벨 2) 이상만 복사 O(n)
    std::vector<LogEntry> critical;
    std::copy_if(logs.begin(), logs.end(), std::back_inserter(critical),
                 [](const LogEntry& e) { return e.level >= 2; });
    // 4. 평균 레벨 O(n)
    long long sum = std::accumulate(logs.begin(), logs.end(), 0LL,
                                    [](long long a, const LogEntry& e) { return a + e.level; });
    double avg = static_cast<double>(sum) / logs.size();
    std::cout << "Errors: " << errors << ", Critical: " << critical.size()
              << ", Avg level: " << avg << "\n";
}

전체 비용은 정렬의 O(n log n)이 지배합니다. 정렬이 필요 없는 집계만 한다면 2~4단계를 루프 하나로 합쳐 O(n) 한 번에 끝낼 수 있고, 시간 순서가 필요한 부분만 정렬하는 편이 낫습니다. critical에 logs.size()만큼 reserve하면 재할당은 없어지지만 경고 비율이 낮을 때 메모리를 과하게 잡으므로, 대략의 비율을 알 때만 그만큼 예약합니다.

상위 K개 (partial_sort vs nth_element)

#include <algorithm>
#include <functional>
#include <vector>
// 상위 k개, 정렬된 순서: O(n log k)
void top_k_sorted(std::vector<int>& vec, size_t k) {
    k = std::min(k, vec.size());
    std::partial_sort(vec.begin(), vec.begin() + k, vec.end(), std::greater<int>());
}
// 상위 k개, 순서 무관: 평균 O(n)
void top_k_any_order(std::vector<int>& vec, size_t k) {
    if (k == 0 || k > vec.size()) return;
    std::nth_element(vec.begin(), vec.begin() + (k - 1), vec.end(), std::greater<int>());
    // vec[0..k-1]에 상위 k개가 들어 있음(내부 순서는 보장 안 됨)
}

nth_element는 k번째 위치에 올 원소를 제자리에 놓고, 그 앞에는 그보다 크거나 같은 원소, 뒤에는 작거나 같은 원소를 모읍니다. 반복자 범위를 넘는 vec.begin() + k는 미정의 동작이므로 k가 크기보다 클 수 있다면 먼저 걸러야 합니다.

STL 알고리즘에서 흔한 실수

binary_search, lower_bound, upper_bound, equal_range는 범위가 비교 기준에 맞게 정렬(정확히는 분할)되어 있다고 가정합니다. 정렬되지 않은 범위에서 호출하면 표준상 전제 조건 위반이라 결과를 믿을 수 없습니다.

std::vector<int> vec = {5, 2, 8, 1, 9};
bool wrong = std::binary_search(vec.begin(), vec.end(), 5);   // 전제 조건 위반
std::sort(vec.begin(), vec.end());
bool found = std::binary_search(vec.begin(), vec.end(), 5);   // OK

정렬 여부를 std::is_sorted로 매번 검사하면 그 자체가 O(n)이라 이진 검색을 쓰는 의미가 사라집니다. 개발 빌드에서만 assert(std::is_sorted(...))로 확인하는 정도가 적당합니다.

accumulate 초기값 타입

std::accumulate의 누적 타입은 초기값의 타입을 따릅니다. 0을 넘기면 누적 변수가 int가 되어, double 벡터를 더할 때마다 결과가 int로 잘립니다.

std::vector<double> vec = {0.1, 0.2, 0.3};
double wrong = std::accumulate(vec.begin(), vec.end(), 0);     // 0 (매 단계 소수부가 잘림)
double right = std::accumulate(vec.begin(), vec.end(), 0.0);   // 0.6

정수 합도 같은 이유로 int 범위를 넘을 수 있다면 0LL을 넘깁니다.

비교자의 strict weak ordering 위반

std::sort의 비교자는 comp(a, a)가 항상 false여야 합니다. <=를 쓰면 같은 값끼리 true가 되어 이 조건이 깨지고, 동작이 미정의가 됩니다. 실제로 libstdc++의 std::sort는 이 경우 배열 경계 밖을 읽다가 크래시할 수 있습니다.

std::sort(vec.begin(), vec.end(), [](int a, int b) { return a <= b; });   // 위반
std::sort(vec.begin(), vec.end(), [](int a, int b) { return a < b; });    // OK

double에 NaN이 섞여 있을 때도 < 비교가 strict weak ordering을 만족하지 않으므로 같은 문제가 생깁니다.

반복자 무효화

vector에 push_back해서 재할당이 일어나면 기존 반복자, 포인터, 참조가 모두 무효가 됩니다.

auto it = vec.begin() + 3;
vec.push_back(100);   // 재할당이 일어나면 it는 해제된 메모리를 가리킴
// *it;              // 미정의 동작
size_t idx = 3;       // 인덱스는 재할당 후에도 유효
vec.push_back(100);
int x = vec[idx];

빈 범위의 평균

빈 벡터의 합을 size()로 나누면 0을 0으로 나눈 NaN(부동소수점)이 되거나, 정수 나눗셈이라면 0으로 나누기가 되어 미정의 동작입니다.

double avg = vec.empty() ? 0.0
                         : std::accumulate(vec.begin(), vec.end(), 0.0) / vec.size();

메모이제이션의 무한 재귀

기저 조건을 빠뜨리면 재귀가 끝나지 않아 스택 오버플로가 납니다. 캐시 확인은 계산 전에, 저장은 계산 후에 합니다.

// 기저 조건이 없어 n이 음수로 내려가며 끝없이 재귀
long long fib_bad(std::vector<long long>& cache, int n) {
    cache[n] = fib_bad(cache, n - 1) + fib_bad(cache, n - 2);
    return cache[n];
}
// cache는 -1로 초기화되어 있다고 가정
long long fib_ok(std::vector<long long>& cache, int n) {
    if (n <= 1) return n;
    if (cache[n] != -1) return cache[n];
    cache[n] = fib_ok(cache, n - 1) + fib_ok(cache, n - 2);
    return cache[n];
}

상수 배를 줄이는 습관

필요할 때만 정렬

검색을 한 번만 한다면 O(n)인 std::find가 O(n log n) 정렬 + 이진 검색보다 낫습니다. 검색이 많을수록 정렬 비용이 분산되므로, 대략 검색 횟수가 log n보다 훨씬 많아지면 정렬해 두는 쪽이 이득입니다.

auto it = std::find(vec.begin(), vec.end(), target);   // 한 번만 검색
std::sort(vec.begin(), vec.end());                     // 여러 번 검색
for (int key : keys) {
    if (std::binary_search(vec.begin(), vec.end(), key)) { /* ... */ }
}

reserve로 재할당 줄이기

결과 크기의 상한을 알면 reserve로 재할당과 원소 복사를 없앨 수 있습니다.

std::vector<int> result;
result.reserve(vec.size());
std::copy_if(vec.begin(), vec.end(), std::back_inserter(result),
             [](int x) { return x % 2 == 0; });

비교자는 std::function 대신 람다로

std::sort는 비교자 타입을 템플릿 인자로 받으므로, 람다를 직접 넘기면 컴파일러가 비교를 인라인할 수 있습니다. std::function으로 감싸면 비교마다 간접 호출이 생겨 인라인이 막힙니다.

std::sort(vec.begin(), vec.end(), [](int a, int b) { return a < b; });   // 인라인 가능
std::function<bool(int, int)> cmp = [](int a, int b) { return a < b; };
std::sort(vec.begin(), vec.end(), cmp);                                    // 비교마다 간접 호출

std::reduce로 병렬 집계 (C++17)

#include <execution>
#include <numeric>
long long total = std::reduce(std::execution::par, vec.begin(), vec.end(), 0LL);

std::reduce는 순서를 바꿔 계산할 수 있어야 하므로 연산이 결합·교환 법칙을 만족해야 합니다(부동소수점 덧셈은 결과가 실행마다 미세하게 달라질 수 있습니다). GCC의 libstdc++에서 병렬 정책은 Intel TBB에 의존하므로 -ltbb로 링크해야 하고, 데이터가 작으면 스레드 분배 비용 때문에 오히려 느립니다.

캐시 친화적 접근

같은 O(n) 순회라도 연속 메모리를 순서대로 읽는 쪽이 훨씬 빠릅니다. vector 순회는 하드웨어 프리페처가 다음 데이터를 미리 가져오지만, 연결 리스트는 다음 노드 주소를 현재 노드를 읽어야 알 수 있어 노드마다 캐시 미스가 나기 쉽습니다.

for (size_t i = 0; i < vec.size(); ++i) process(vec[i]);    // 연속 접근
for (auto* p = head; p; p = p->next) process(p->value);      // 포인터 추적

요구사항별 알고리즘 선택

요구사항추천복잡도
전체 정렬sortO(n log n)
같은 값의 원래 순서 유지stable_sortO(n log n), 메모리가 부족하면 O(n log² n)
상위 K개 (정렬)partial_sortO(n log k)
상위 K개 (순서 무관)nth_element평균 O(n)
정렬된 범위에서 존재 여부binary_searchO(log n)
정렬 없이 존재 여부unordered_set평균 O(1)
부분 배열 최대합KadaneO(n)
두 수의 합해시 / 정렬 + 투 포인터평균 O(n) / O(n log n)
중복 제거sort + unique + eraseO(n log n)
조건에 맞는 원소 제거remove_if + erase (C++20 std::erase_if)O(n)

어떤 최적화든 먼저 측정해서 병목이 정말 그곳인지 확인하는 것이 출발점입니다. 복잡도를 줄이는 변경은 효과가 크지만, 전체 실행 시간의 몇 퍼센트만 차지하는 함수를 고쳐서는 체감할 수 있는 차이가 나지 않습니다. 측정 방법은 프로파일러 비교와 벤치마킹 글을 참고하세요.

같이 보면 좋은 글