C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]

들어가며: 알고리즘 최적화가 왜 필요한가

”데이터가 늘어나니 응답이 10초 넘게 걸려요”

100만 건의 로그를 처리할 때 O(n²) 알고리즘을 쓰면 시간 초과가 발생합니다. 반대로 O(n)으로 줄이려다 메모리를 과다 사용해 OOM(Out of Memory)에 빠지기도 합니다. 알고리즘 최적화는 시간복잡도·공간복잡도·트레이드오프를 이해하고, 문제 제약에 맞는 선택을 하는 것입니다. 이 글에서는 Big-O 분석부터 공간-시간 트레이드오프, 메모이제이션, 프로덕션 패턴까지 실전 활용법을 다룹니다.

요구 환경: C++17 이상

이 글을 읽으면:

• Big-O 표기법으로 알고리즘을 분석할 수 있습니다.
• 공간-시간 트레이드오프를 이해하고 적용할 수 있습니다.
• 실전 알고리즘 최적화 예제를 구현할 수 있습니다.
• 흔한 에러를 피하고 프로덕션 패턴을 적용할 수 있습니다.

---

실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.

목차

1. 문제 시나리오
2. 기본 개념: Big-O와 복잡도
3. 핵심 구현: 최적화 패턴
4. 고급 기법: 공간-시간 트레이드오프
5. 완전한 알고리즘 최적화 예제
6. 자주 발생하는 에러와 해결법
7. 성능 최적화 팁
8. 프로덕션 패턴

---

1. 문제 시나리오

시나리오 1: 대량 데이터 정렬 시 타임아웃

상황: 100만 건의 사용자 ID를 정렬해야 합니다. 버블 정렬을 사용하면 O(n²)이 되어 10초 이상 걸립니다. 실시간 API 응답 요구사항(200ms 이내)을 충족하지 못합니다.

해결: std::sort(인트로소트, O(n log n))로 교체하면 수 밀리초 이내에 완료됩니다. 정렬 알고리즘 선택이 최적화의 첫 단계입니다.

시나리오 2: 정렬된 배열에서 반복 검색

상황: 이미 정렬된 100만 개 ID 목록에서 10만 개의 키를 검색해야 합니다. std::find로 선형 검색하면 O(n × m) = 1조 번 연산으로 수 초가 걸립니다.

해결: std::binary_search 또는 std::lower_bound로 O(log n) 검색하면 10만 × 20 ≈ 200만 번 연산으로 수십 밀리초에 완료됩니다. 데이터 구조와 알고리즘 조합이 핵심입니다.

시나리오 3: 피보나치 재귀 호출 폭발

상황: fib(n)을 재귀적으로 구현하면 fib(40) 호출에 수 초가 걸립니다. 같은 하위 문제를 반복 계산하기 때문입니다.

해결: 메모이제이션(캐시)으로 O(2^n) → O(n)으로 개선합니다. 중복 계산 제거가 최적화의 핵심입니다.

시나리오 4: 메모리 부족 (OOM)

상황: 10GB 데이터를 처리하는데 O(n²) 공간을 사용하는 2차원 DP 테이블을 만들면 OOM이 발생합니다.

해결: 슬라이딩 윈도우 또는 상태 압축으로 O(n²) → O(n) 공간으로 줄입니다. 공간-시간 트레이드오프를 이해해야 합니다.

시나리오 5: 중복 제거 후 성능 저하

상황: std::vector에서 중복을 제거할 때 매번 std::find로 검색하면 O(n²)입니다. 100만 건이면 수 시간이 걸립니다.

해결: std::sort + std::unique + erase로 O(n log n)에 처리하거나, std::unordered_set으로 O(n)에 처리합니다.

알고리즘 최적화 의사결정 흐름

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

---

2. 기본 개념: Big-O와 복잡도

Big-O 표기법이란

Big-O는 입력 크기 n이 커질 때 연산 횟수나 메모리 사용량이 어떻게 증가하는지 나타냅니다. 상수 배와 낮은 차수는 무시하고 최악의 증가 추세를 표현합니다.

// O(1): 상수 시간 - n과 무관
int get_first(const std::vector<int>& vec) {
    return vec.empty() ? 0 : vec[0];
}

// O(n): 선형 - n에 비례
int sum(const std::vector<int>& vec) {
    int s = 0;
    for (int x : vec) s += x;
    return s;
}

// O(n²): 제곱 - n²에 비례 (이중 루프)
void bubble_sort(std::vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i)
        for (size_t j = 0; j < vec.size() - 1 - i; ++j)
            if (vec[j] > vec[j + 1])
                std::swap(vec[j], vec[j + 1]);
}

// O(log n): 로그 - 이진 검색
bool binary_search(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,000	n=1,000,000	대표 예시
O(1)	1	1	배열 인덱싱, 해시 조회
O(log n)	10	20	이진 검색, 균형 트리
O(n)	1,000	1,000,000	선형 스캔, 단일 루프
O(n log n)	10,000	20,000,000	병합/퀵 정렬
O(n²)	1,000,000	1조	버블 정렬, 이중 루프
O(2^n)	-	-	재귀 피보나치(비실용)

공간복잡도

공간복잡도는 추가 메모리 사용량을 나타냅니다. 입력 자체의 크기는 제외하고, 알고리즘이 사용하는 보조 공간을 봅니다.

// O(1) 공간: 추가 메모리 없음
int max_element(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²) 공간: 2차원 DP 테이블
// dp[i][j] = 길이 i, j인 두 수열의 LCS
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));
}

Big-O 분석 다이어그램

flowchart LR
    subgraph time[시간복잡도]
        T1[O(1)]
        T2[O(log n)]
        T3[O(n)]
        T4[O(n log n)]
        T5[O(n²)]
    end
    subgraph space[공간복잡도]
        S1[O(1)]
        S2[O(n)]
        S3[O(n²)]
    end
    T1 --> S1
    T3 --> S2
    T5 --> S3

---

3. 핵심 구현: 최적화 패턴

패턴 1: 불필요한 반복 제거

같은 데이터를 여러 번 순회하지 말고, 한 번의 루프에서 필요한 연산을 모두 수행합니다.

// ❌ 비효율: 두 번 순회
int sum_and_count_evens_bad(const std::vector<int>& vec) {
    int 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<int, int> sum_and_count_evens(const std::vector<int>& vec) {
    int sum = 0, count = 0;
    for (int x : vec) {
        sum += x;
        if (x % 2 == 0) ++count;
    }
    return {sum, count};
}

패턴 2: 조기 종료 (Early Exit)

조건을 만족하면 즉시 반환하여 불필요한 연산을 건너뜁니다.

// ❌ 비효율: 끝까지 순회
bool contains_negative_bad(const std::vector<int>& vec) {
    bool found = false;
    for (int x : vec)
        if (x < 0) found = true;
    return found;
}

// ✅ 효율: 첫 음수 발견 시 즉시 반환
bool contains_negative(const std::vector<int>& vec) {
    for (int x : vec)
        if (x < 0) return true;
    return false;
}

패턴 3: 인덱스 vs 반복자

랜덤 접근이 필요하면 vector + 인덱스가 캐시 친화적입니다. 순차 접근만 필요하면 반복자가 깔끔합니다.

// 인덱스: 이진 검색, DP 등
size_t binary_search_idx(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 hi = mid;
    }
    return lo;
}

// 반복자: STL 알고리즘과 호환
auto it = std::lower_bound(vec.begin(), vec.end(), target);

패턴 4: 데이터 구조 선택

연산	vector	set/map	unordered_set/map
검색	O(n)	O(log n)	O(1) 평균
삽입	O(1) 끝	O(log n)	O(1) 평균
정렬 유지	수동	자동	없음

// 존재 여부만 빠르게 확인 -> unordered_set
#include <unordered_set>
std::unordered_set<int> ids(data.begin(), data.end());
if (ids.count(target)) { /* ... */ }

// 정렬된 순서 유지 + 검색 -> set
#include <set>
std::set<int> sorted_ids(data.begin(), data.end());
auto it = sorted_ids.lower_bound(target);

---

4. 고급 기법: 공간-시간 트레이드오프

트레이드오프 개념

공간을 더 쓰면 시간을 줄일 수 있고, 시간을 더 쓰면 공간을 줄일 수 있습니다. 메모이제이션, 해시 테이블, 사전 계산이 대표적입니다.

flowchart TB
    subgraph trade[트레이드오프]
        A[메모리 ↑] --> B[시간 ↓]
        C[메모리 ↓] --> D[시간 ↑]
    end
    E[메모이제이션] --> A
    F[해시 테이블] --> A
    G[슬라이딩 윈도우] --> C
    H[재계산] --> C

메모이제이션: 피보나치 최적화

재귀 피보나치는 O(2^n)입니다. 메모이제이션으로 O(n) 시간, O(n) 공간으로 개선합니다.

#include <vector>
#include <optional>

// ❌ 비효율: O(2^n)
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;
}

슬라이딩 윈도우: 공간 압축

2차원 DP를 1차원으로 압축하여 O(n²) → O(n) 공간으로 줄입니다.

// 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) {
        // 역순 순회: 이전 행만 참조
        for (int w = W; w >= weights[i]; --w) {
            dp[w] = std::max(dp[w],
                dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

해시 테이블로 검색 가속

정렬 없이 O(1) 평균 검색이 필요할 때 std::unordered_map을 사용합니다.

#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};
}

---

5. 완전한 알고리즘 최적화 예제

예제 1: 최대 부분 배열 합 (Kadane 알고리즘)

문제: 연속된 부분 배열 중 합이 최대인 값을 구합니다. 브루트포스는 O(n²) 또는 O(n³)입니다.

// g++ -std=c++17 -o kadane kadane.cpp && ./kadane
#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>

// ❌ 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";   // 6
    std::cout << "Kadane: " << max_subarray_kadane(vec) << "\n"; // 6
    return 0;
}

실행 결과:

Naive: 6
Kadane: 6

예제 2: 두 수의 합 → 세 수의 합 (정렬 + 투 포인터)

문제: 배열에서 합이 target이 되는 두/세 원소를 찾습니다.

#include <algorithm>
#include <vector>
#include <iostream>

// 두 수의 합: 정렬 O(n log n) + 투 포인터 O(n) = O(n log n)
std::pair<int, int> two_sum_sorted(std::vector<int> vec, int target) {
    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 {};
}

예제 3: LCS (최장 공통 부분 수열) 최적화

문제: 두 수열의 최장 공통 부분 수열 길이. 2차원 DP는 O(nm) 공간입니다. 현재 행과 이전 행만 쓰면 O(min(n,m)) 공간으로 압축합니다.

#include <vector>
#include <algorithm>
#include <string>

// 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) {
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = 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);
    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) {
            if (a[i-1] == b[j-1])
                curr[j] = prev[j-1] + 1;
            else
                curr[j] = std::max(prev[j], curr[j-1]);
        }
        std::swap(prev, curr);
    }
    return prev[m];
}

예제 4: 로그 분석 파이프라인 (STL 알고리즘 조합)

대량 로그를 필터링·정렬·집계하는 실전 예제입니다.

#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <iostream>

struct LogEntry {
    std::string timestamp;
    int level;
    std::string message;
};

void analyze_logs(std::vector<LogEntry>& logs) {
    // 1. 타임스탬프 정렬 O(n log n)
    std::sort(logs.begin(), logs.end(),
         {
            return a.timestamp < b.timestamp;
        });

    // 2. ERROR 개수 O(n)
    int errors = std::count_if(logs.begin(), logs.end(),
         { return e.level >= 3; });

    // 3. WARN 이상만 복사 O(n)
    std::vector<LogEntry> critical;
    critical.reserve(logs.size());
    std::copy_if(logs.begin(), logs.end(), std::back_inserter(critical),
         { return e.level >= 2; });

    // 4. 평균 레벨 O(n)
    int sum = std::accumulate(logs.begin(), logs.end(), 0,
         { return a + e.level; });
    double avg = static_cast<double>(sum) / logs.size();

    std::cout << "Errors: " << errors << ", Avg level: " << avg << "\n";
}

예제 5: 상위 K개 요소 (partial_sort vs nth_element)

전체 정렬 없이 상위 K개만 필요할 때 nth_element가 더 빠릅니다.

#include <algorithm>
#include <vector>
#include <iostream>

// 상위 5개 (정렬된 순서 필요)
void top5_sorted(std::vector<int>& vec) {
    std::partial_sort(vec.begin(), vec.begin() + 5, vec.end(),
                      std::greater<int>());
}

// 상위 5개 (순서 무관, 더 빠름)
void top5_any_order(std::vector<int>& vec) {
    if (vec.size() < 5) return;
    std::nth_element(vec.begin(), vec.begin() + 4, vec.end(),
                     std::greater<int>());
    // vec[0..4]에 상위 5개 (순서 보장 안 됨)
}

---

6. 자주 발생하는 에러와 해결법

에러 1: 정렬되지 않은 범위에 binary_search 사용

증상: 검색 결과가 잘못되거나 예측 불가능합니다.

원인: binary_search, lower_bound, upper_bound는 정렬된 범위에서만 올바르게 동작합니다.

// ❌ 잘못된 사용
std::vector<int> vec = {5, 2, 8, 1, 9};
bool found = std::binary_search(vec.begin(), vec.end(), 5);  // UB!

// ✅ 올바른 사용
std::sort(vec.begin(), vec.end());
bool found = std::binary_search(vec.begin(), vec.end(), 5);

에러 2: accumulate 초기값 타입 불일치

증상: 부동소수점 합계가 잘못되거나 정밀도가 떨어집니다.

원인: 0은 int이므로 double 벡터를 합할 때 매 단계 int로 변환됩니다.

// ❌ 잘못된 사용
std::vector<double> vec = {0.1, 0.2, 0.3};
double sum = std::accumulate(vec.begin(), vec.end(), 0);  // int 0

// ✅ 올바른 사용
double sum = std::accumulate(vec.begin(), vec.end(), 0.0);

에러 3: 비교자 strict weak ordering 위반

증상: std::sort 호출 시 크래시 또는 무한 루프.

원인: a <= b를 사용하면 a == b일 때 true가 되어 a < a가 true가 될 수 있습니다.

// ❌ 잘못된 비교자
std::sort(vec.begin(), vec.end(),
     { return a <= b; });  // 위반

// ✅ 올바른 비교자
std::sort(vec.begin(), vec.end(),
     { return a < b; });

에러 4: 반복자 무효화 후 사용

증상: Segmentation fault 또는 예측 불가능한 동작.

원인: push_back 등으로 재할당이 일어나면 기존 반복자가 무효화됩니다.

// ❌ 위험한 패턴
auto it = vec.begin();
vec.push_back(100);  // 재할당 가능
*it;  // UB

// ✅ 인덱스 사용 또는 반복자 사용 직후에만
size_t idx = std::distance(vec.begin(), it);
vec.push_back(100);

에러 5: 빈 범위에서 나눗셈

증상: 0으로 나누기 또는 잘못된 평균.

원인: vec.empty()일 때 accumulate 결과를 size()로 나누면 0으로 나눕니다.

// ❌ 위험
double avg = std::accumulate(vec.begin(), vec.end(), 0.0) / vec.size();

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

에러 6: 메모이제이션에서 무한 재귀

증상: 스택 오버플로우.

원인: 기저 조건을 빠뜨리거나, 캐시에 저장 전에 재귀 호출합니다.

// ❌ 잘못된 메모이제이션
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];
}

// ✅ 올바른 메모이제이션
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];
}

---

7. 성능 최적화 팁

팁 1: 정렬이 필요할 때만 정렬

한 번만 검색할 거면 std::find(O(n))가 정렬(O(n log n)) + binary_search보다 나을 수 있습니다.

// 한 번만 검색 -> find
auto it = std::find(vec.begin(), vec.end(), target);

// 여러 번 검색 -> 정렬 후 binary_search
std::sort(vec.begin(), vec.end());
for (int key : keys) {
    if (std::binary_search(vec.begin(), vec.end(), key)) { /* ... */ }
}

팁 2: reserve로 재할당 최소화

back_inserter 사용 시 결과 크기를 대략 알 수 있으면 reserve로 재할당을 줄입니다.

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

팁 3: partial_sort vs nth_element

상위 K개만 필요할 때:

• 순서 필요: partial_sort O(n log k)
• 순서 무관: nth_element O(n) 평균, 더 빠름

// 상위 10개, 정렬된 순서
std::partial_sort(vec.begin(), vec.begin() + 10, vec.end(), std::greater<int>());

// 상위 10개, 순서 무관
std::nth_element(vec.begin(), vec.begin() + 9, vec.end(), std::greater<int>());

팁 4: 람다 vs std::function

람다는 컴파일러가 인라인하기 쉽습니다. std::function은 간접 호출 비용이 있습니다.

// ✅ 람다 (인라인 가능)
std::sort(vec.begin(), vec.end(),  { return a < b; });

// ❌ std::function (간접 호출)
std::function<bool(int,int)> cmp =  { return a < b; };
std::sort(vec.begin(), vec.end(), cmp);

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

대용량 데이터 집계 시 std::reduce + std::execution::par로 병렬화합니다.

#include <numeric>
#include <execution>

int sum = std::reduce(std::execution::par, vec.begin(), vec.end(), 0);

팁 6: 캐시 친화적 접근

연속 메모리 접근이 캐시에 유리합니다. vector가 list보다 대부분 빠릅니다.

// ✅ 연속 접근 (캐시 친화적)
for (size_t i = 0; i < vec.size(); ++i)
    process(vec[i]);

// ❌ 랜덤 포인터 따라가기 (캐시 미스)
for (auto* p = head; p; p = p->next)
    process(p->value);

성능 비교 요약

연산	비효율	효율	개선
부분 배열 합	O(n²)	O(n) Kadane	n배
두 수의 합	O(n²)	O(n) 해시	n배
피보나치	O(2^n)	O(n) 메모이제이션	지수적
LCS 공간	O(nm)	O(min(n,m))	m배
상위 K개	O(n log n) sort	O(n) nth_element	log n배

---

8. 프로덕션 패턴

패턴 1: erase-remove idiom

조건에 맞는 원소를 제거할 때 remove_if + erase 조합을 사용합니다.

// 짝수 제거
vec.erase(std::remove_if(vec.begin(), vec.end(),
                          { return x % 2 == 0; }),
          vec.end());

패턴 2: 정렬 + unique로 중복 제거

std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

패턴 3: 안전한 이진 검색 래퍼

정렬 여부를 확인한 뒤 binary_search를 호출하는 래퍼입니다.

#include <algorithm>

template <typename Container, typename T>
bool safe_binary_search(const Container& c, const T& value) {
    if (!std::is_sorted(c.begin(), c.end()))
        return false;
    return std::binary_search(c.begin(), c.end(), value);
}

패턴 4: 알고리즘 선택 가이드

flowchart TB
    subgraph need[요구사항]
        N1[전체 정렬]
        N2[상위 K개]
        N3[존재 여부]
        N4[빠른 검색]
    end
    subgraph choice[선택]
        C1[sort]
        C2[partial_sort / nth_element]
        C3[binary_search]
        C4[unordered_set]
    end
    N1 --> C1
    N2 --> C2
    N3 --> C3
    N4 --> C4

패턴 5: 프로파일링 우선

최적화 전에 병목 지점을 측정합니다. 추측이 아닌 데이터로 결정합니다.

// 프로파일링 예시 (의사 코드)
// 1. 벤치마크로 현재 성능 측정
// 2. 병목 구간 식별 (정렬? 검색? I/O?)
// 3. 해당 구간만 최적화
// 4. 다시 측정하여 개선 확인

패턴 6: 구현 체크리스트

프로덕션에 알고리즘 최적화를 적용할 때 확인할 항목입니다.

• binary_search 계열 사용 전 범위가 정렬되어 있는지 확인
• accumulate 초기값 타입이 집계 결과와 일치하는지 확인 (double이면 0.0)
• 커스텀 비교자가 strict weak ordering을 만족하는지 확인
• remove/remove_if 후 반드시 erase로 논리적 끝 구간 제거
• 대용량 데이터 시 reserve로 재할당 최소화
• 메모리 제한이 있으면 공간 압축(슬라이딩 윈도우) 검토
• 최적화 전 프로파일링으로 병목 확인

패턴 7: 알고리즘 선택 표

요구사항	추천	복잡도
전체 정렬	sort	O(n log n)
같은 값 순서 유지	stable_sort	O(n log n)
상위 K개 (정렬)	partial_sort	O(n log k)
상위 K개 (순서 무관)	nth_element	O(n) 평균
존재 여부 (정렬됨)	binary_search	O(log n)
빠른 존재 여부	unordered_set	O(1) 평균
부분 배열 최대합	Kadane	O(n)
두 수의 합	해시 / 투 포인터	O(n)
중복 제거	sort + unique	O(n log n)

---

정리

항목	설명
Big-O	시간·공간 복잡도로 알고리즘 분석
트레이드오프	메모이제이션, 슬라이딩 윈도우, 해시
최적화 패턴	조기 종료, 반복 제거, 데이터 구조 선택
에러	정렬 없이 binary_search, 초기값 타입, 비교자 위반
성능	reserve, nth_element, 람다, reduce 병렬
프로덕션	erase-remove, sort+unique, 프로파일링 우선

핵심 원칙:

1. Big-O로 알고리즘을 분석하고 병목을 파악한다.
2. 공간-시간 트레이드오프를 이해하고 제약에 맞게 선택한다.
3. 정렬된 범위에서만 binary_search 계열을 사용한다.
4. accumulate 초기값 타입을 결과와 일치시킨다.
5. 최적화 전 프로파일링으로 병목을 확인한다.

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 성능 크리티컬한 시스템, 대용량 데이터 처리, 실시간 제약 등에 활용합니다. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

한 줄 요약: 시간복잡도·공간복잡도·트레이드오프를 마스터하고, 문제 시나리오별 최적 알고리즘을 선택할 수 있습니다.

---

관련 글

• C++ 동적 계획법 완벽 가이드 | 메모이제이션·타뷸레이션·최적화 [#54-4]
• C++ 분할정복 완벽 가이드 | 병합정렬·퀵소트·이진탐색·클로스페어·Strassen [실전]
• C++ 고급 프로파일링 완벽 가이드 | perf·gprof
• C++ Benchmarking |