C++ 코테용 STL 컨테이너/알고리즘 시간복잡도 치트시트 [#32-3]

· 20분 읽기 · 수정 초급 치트시트
C++ 코테용 STL 컨테이너/알고리즘 시간복잡도 치트시트 [#32-3]

이 글의 핵심

C++ 코테용 STL 컨테이너/알고리즘 시간복잡도 치트시트 [#32-3]에 대해 정리한 개발 블로그 글입니다. C++ 실전 가이드 #10-1~10-3에서 vector, string, map, set, unordered_map, 그리고 sort·find 등 알고리즘을 다뤘습니다. 이 글은 코딩 테스트에서 "어떤 연산이 얼마나… 개념과 예제 코드를 단계적으로 다루며, 실무·학습에 참고할 수 있…

들어가며: “이 문제엔 뭘 써야 하지?”

코테에서 자료구조 선택 실패로 시간 초과가 나는 이유

C++ 실전 가이드 #10-1~10-3에서 vector, string, map, set, unordered_map, 그리고 sort·find 등 알고리즘을 다뤘습니다. 이 글은 코딩 테스트에서 “어떤 연산이 얼마나 걸리는지” 와 “상황별로 어떤 컨테이너를 골라야 하는지” 를 표 위주로 압축합니다. 시험 전에 한 번 훑어 두면 좋은 치트시트입니다.

실제 겪는 문제 시나리오:

  1. “맨 앞에 삽입” 문제: vector의 insert(begin(), x)를 반복 → O(n²) 누적으로 시간 초과. deque나 list를 썼어야 함.
  2. “키 존재 여부” 문제: map으로만 풀다가 → O(log n) 검색이 N번 반복되며 느려짐. unordered_map이면 O(1) 평균.
  3. “k번째 큰 수” 문제: 매 쿼리마다 sort 호출 → O(n log n) × 쿼리 수로 폭발. nth_element나 priority_queue로 O(n) 또는 O(log n)에 해결.
  4. “정렬된 배열에서 검색”: find로 선형 검색 → O(n). binary_search·lower_bound를 쓰면 O(log n).
  5. “반복자 무효화” 문제: vector 순회 중 erase 후 it++만 하면 크래시. it = v.erase(it)로 받아야 함.
  6. “빈 컨테이너 접근” 문제: pq.top() 또는 v.front()를 empty() 체크 없이 호출 → undefined behavior.

이 글에서는 위와 같은 실패 패턴을 피하고, 연산별 시간복잡도와 상황별 선택 가이드를 표와 코드로 정리합니다.

flowchart TB
  subgraph problem["자주 겪는 실패 시나리오"]
    P1[vector 앞 삽입 반복 → TLE]
    P2[map으로 키 검색만 → 느림]
    P3[매번 sort 호출 → 폭발]
    P4["정렬된데 find 사용 → O(n)"]
  end
  subgraph solution["올바른 선택"]
    S1[deque / list]
    S2[unordered_map]
    S3[nth_element / priority_queue]
    S4[lower_bound / binary_search]
  end
  P1 --> S1
  P2 --> S2
  P3 --> S3
  P4 --> S4

이 글에서 다루는 것:

  • 시퀀스 컨테이너: vector, deque, list — 연산별 시간복잡도
  • 연관 컨테이너: map, set, unordered_map, unordered_set
  • 어댑터: priority_queue, stack, queue
  • 반복자(Iterator): 종류별 사용법과 무효화 주의점
  • 알고리즘: sort, lower_bound, binary_search 등
  • 상황별 선택 가이드 표
  • 자주 하는 실수, 베스트 프랙티스, 프로덕션 패턴

STL 컨테이너를 성능·용도별로 나누면 아래와 같습니다. 코테에서는 시퀀스는 vector 중심, 키 검색은 map/unordered_map, 최대/최소 빠른 추출은 priority_queue를 먼저 떠올리면 됩니다.

flowchart LR
  subgraph seq["시퀀스"]
    vector[vector]
    deque[deque]
    list[list]
  end
  subgraph assoc["연관"]
    map[map / set]
    umap[unordered_map / set]
  end
  subgraph adapt["어댑터"]
    pq[priority_queue]
  end
  seq --> assoc
  assoc --> adapt

개념을 잡는 비유

C++에서 자주 쓰는 비유로, 템플릿은 붕어빵 틀, 스마트 포인터는 자동 청소 로봇, RAII는 자동문처럼 스코프를 나가며 자원을 정리한다고 기억해 두면 다른 글과도 연결하기 쉽습니다.

목차

  1. 시퀀스: vector, deque, list
  2. 연관: map/set vs unordered_map/set
  3. 어댑터: priority_queue, stack, queue
  4. 반복자(Iterator) 치트시트
  5. 주요 알고리즘 시간복잡도
  6. 상황별 컨테이너 선택 표
  7. 자주 하는 실수와 해결법
  8. 베스트 프랙티스
  9. 프로덕션 패턴
  10. 성능 최적화 팁
  11. 구현 체크리스트

1. 시퀀스: vector, deque, list

vector

연산시간복잡도비고
[], at(i)O(1)랜덤 액세스
push_back, pop_backO(1) amortized끝 추가/삭제
insert/erase (앞/중간)O(n)뒤쪽 원소 이동
reserve 후 push_backO(1)재할당 최소화
  • 연속 메모리 → 캐시 친화적, 순회·인덱싱 빠름.
  • 앞/중간 삽입·삭제가 많으면 비효율적.

실전 예시: vector가 적합한 경우

// 백준 스타일: N개 정수 입력받아 인덱스로 접근
// - push_back만 사용, [] 접근 많음 → vector 최적
#include <vector>
#include <iostream>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> v;
    v.reserve(n);  // 재할당 방지
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        v.push_back(x);  // O(1) amortized
    }
    // O(1) 인덱스 접근으로 DP 등에 활용
    for (size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << " ";
    }
    return 0;
}

vector가 부적합한 경우 (앞쪽 삽입 반복)

// ❌ 나쁜 예: 매번 맨 앞에 삽입 → O(n) × n = O(n²)
std::vector<int> bad;
for (int i = 0; i < 100000; ++i) {
    bad.insert(bad.begin(), i);  // 매번 O(n) 이동
}

// ✅ 좋은 예: deque 사용 → O(1) × n = O(n)
#include <deque>
std::deque<int> good;
for (int i = 0; i < 100000; ++i) {
    good.push_front(i);  // O(1)
}

deque

연산시간복잡도비고
[], at(i)O(1)랜덤 액세스
push_back, pop_backO(1)
push_front, pop_frontO(1)vector와의 차이
insert/erase (중간)O(n)
  • 앞뒤 삽입/삭제가 모두 필요할 때 vector 대신 고려.

실전 예시: BFS 큐, 슬라이딩 윈도우

// BFS에서 deque 사용 (앞에서 pop, 뒤에서 push)
#include <deque>
#include <vector>

void bfs(const std::vector<std::vector<int>>& graph, int start) {
    std::deque<int> q;
    q.push_back(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();  // O(1)
        for (int v : graph[u]) {
            q.push_back(v);  // O(1)
        }
    }
}

list (연결 리스트)

연산시간복잡도비고
push_front, pop_front, push_back, pop_backO(1)
insert/erase (위치 알 때)O(1)반복자 유지 시
[], 순차 접근O(n)랜덤 액세스 없음
  • 중간 삽입/삭제가 많고 인덱스 접근이 거의 없을 때만 고려. 코테에서는 vector를 기본으로 두고, 앞쪽 삽입이 많으면 deque를 쓰는 경우가 많음.

요약 표: 시퀀스

연산vectordequelist
뒤 추가/삭제O(1) amortO(1)O(1)
앞 추가/삭제O(n)O(1)O(1)
중간 삽입/삭제O(n)O(n)O(1)*
인덱스 접근O(1)O(1)O(n)

* 반복자 위치가 이미 있을 때

2. 연관: map/set vs unordered_map/set

map, set (Red-Black Tree)

연산시간복잡도비고
insert, erase, findO(log n)키 기준
[] (map)O(log n)없으면 삽입
순회키 정렬 순오름차순
  • 정렬된 순서가 필요하거나, “가장 작은/큰 키”를 자주 쓸 때 유리.

실전 예시: 정렬된 키가 필요한 경우

// "범위 내 키 개수" 또는 "k번째로 작은 키" 필요 시
#include <map>
#include <iostream>

int main() {
    std::map<int, int> cnt;
    cnt[3] = 1;
    cnt[1] = 2;
    cnt[4] = 1;
    // 순회 시 키 오름차순: 1, 3, 4
    for (const auto& [k, v] : cnt) {
        std::cout << k << ":" << v << " ";
    }
    // lower_bound, upper_bound로 범위 쿼리 O(log n)
    auto it = cnt.lower_bound(2);  // 2 이상인 첫 키
    return 0;
}

unordered_map, unordered_set (해시 테이블)

연산시간복잡도비고
insert, erase, findO(1) 평균최악 O(n)
[] (unordered_map)O(1) 평균
순회순서 없음
  • 키만 빠르게 찾으면 되고 순서가 필요 없을 때 map보다 빠름. 해시 충돌이 심하면 최악 O(n)이므로, 코테에서 보통은 unordered_map이 유리한 경우가 많음.

실전 예시: 두 수의 합, 빈도 카운트

// "두 수의 합" 문제: 값 존재 여부만 O(1)에 확인
#include <unordered_map>
#include <vector>

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;  // 값 -> 인덱스
    for (size_t i = 0; i < nums.size(); ++i) {
        int need = target - nums[i];
        if (seen.count(need)) {  // O(1) 평균
            return {static_cast<int>(seen[need]), static_cast<int>(i)};
        }
        seen[nums[i]] = i;
    }
    return {};
}

map vs unordered_map 성능 비교 (개념)

flowchart LR
  subgraph map_use["map 사용 시점"]
    M1[키 정렬 필요]
    M2[lower_bound / 범위 쿼리]
    M3[최소/최대 키 자주 접근]
  end
  subgraph umap_use["unordered_map 사용 시점"]
    U1[존재 여부만]
    U2[값 조회만]
    U3[빈도 카운트]
  end

요약 표: 연관

연산map / setunordered_map / unordered_set
삽입/삭제/검색O(log n)O(1) 평균
키 순서정렬됨없음
사용 상황정렬·범위 쿼리존재 여부·값 조회

3. 어댑터: priority_queue, stack, queue

priority_queue (힙)

연산시간복잡도비고
pushO(log n)
popO(log n)최대(또는 최소) 제거
topO(1)최대(또는 최소) 조회
  • 최대/최소를 반복해서 꺼내는 패턴(다익스트라, 이벤트 스케줄 등)에 사용.
  • 기본은 최대 힙 (std::less). 최소 힙은 std::greater<int> 를 세 번째 템플릿 인자로 주면 top() 이 최소값이 됩니다.
// 복사해 붙여넣은 뒤: g++ -std=c++17 -o pq_demo pq_demo.cpp && ./pq_demo
#include <queue>
#include <vector>
#include <functional>
#include <iostream>

int main() {
    std::priority_queue<int> maxHeap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    maxHeap.push(3); maxHeap.push(1); maxHeap.push(4);
    minHeap.push(3); minHeap.push(1); minHeap.push(4);
    std::cout << "max top=" << maxHeap.top() << " min top=" << minHeap.top() << "\n";  // 4, 1
    return 0;
}

실행 결과: max top=4 min top=1 이 한 줄 출력됩니다.

실전 예시: K번째 큰 수 (nth_element 대안)

// N개 중 K번째로 큰 수: 최소 힙 크기 K로 유지
#include <queue>
#include <vector>

int kthLargest(const std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    for (int x : nums) {
        pq.push(x);
        if (pq.size() > static_cast<size_t>(k)) pq.pop();
    }
    return pq.top();  // O(1)
}

실전 예시: 다익스트라 (최소 힙)

// (거리, 정점) 쌍을 최소 힙에 넣어 가장 가까운 정점부터 처리
#include <queue>
#include <vector>

using Pair = std::pair<int, int>;  // (거리, 정점)

void dijkstra(const std::vector<std::vector<Pair>>& graph, int start,
              std::vector<int>& dist) {
    std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair>> pq;
    pq.push({0, start});
    dist[start] = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (const auto& [w, v] : graph[u]) {
            int nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push({nd, v});
            }
        }
    }
}

stack, queue

컨테이너기본 내부주요 연산시간복잡도
stackdequepush, pop, topO(1)
queuedequepush, pop, front, backO(1)
// DFS: stack 사용
#include <stack>
#include <vector>

void dfs(const std::vector<std::vector<int>>& graph, int start) {
    std::stack<int> st;
    std::vector<bool> visited(graph.size());
    st.push(start);
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int v : graph[u]) {
            if (!visited[v]) st.push(v);
        }
    }
}

4. 반복자(Iterator) 치트시트

반복자 종류와 지원 연산

반복자컨테이너/알고리즘지원 연산
Random Accessvector, deque, arrayit + k, it - k, it[k], it1 < it2
Bidirectionallist, map, set++it, --it
Forwardforward_list++it 만

반복자 사용 예시

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5};

    // 1. begin/end로 순회
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    // 2. reverse_iterator 사용 (역순)
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        std::cout << *it << " ";
    }

    // 3. distance로 범위 길이 계산
    auto it = std::find(v.begin(), v.end(), 4);
    if (it != v.end()) {
        size_t pos = std::distance(v.begin(), it);  // O(1) for random access
    }

    // 4. next, prev (C++11)
    auto mid = std::next(v.begin(), v.size() / 2);
    auto prev_it = std::prev(v.end(), 1);

    return 0;
}

반복자 무효화 규칙

컨테이너무효화되는 경우
vector, dequeinsert, erase, push_back(재할당 시)
list, map, set삭제된 요소를 가리키는 반복자만 무효화
unordered_*rehash 발생 시
// ❌ 위험: vector erase 후 it++ 사용
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it);  // it 무효화! 다음 ++it는 UB
    }
}

// ✅ 안전: erase 반환값 사용
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);  // 다음 유효 반복자 반환
    } else {
        ++it;
    }
}

5. 주요 알고리즘 시간복잡도

알고리즘 치트시트 표

알고리즘시간복잡도비고
std::sortO(n log n)일반 정렬
std::stable_sortO(n log n)동일 값 순서 유지
std::partial_sortO(n log k)상위 k개만 정렬
std::nth_elementO(n) 평균k번째 원소만 맞는 위치로
std::findO(n)선형 검색
std::find_ifO(n)조건 검색
std::binary_searchO(log n)정렬된 범위에서
std::lower_bound / upper_boundO(log n)정렬된 범위, 반복자 반환
std::mergeO(n+m)두 정렬 구간 병합
std::inplace_mergeO(n log n)인접 정렬 구간 병합
std::reverseO(n)뒤집기
std::uniqueO(n)연속 중복 제거 (정렬 후 사용)
std::accumulateO(n)합/곱 등 축소
std::min_element / max_elementO(n)최소/최대 위치
  • 정렬되지 않은 벡터에서 검색 → find O(n).
  • 정렬된 벡터에서 검색 → binary_search / lower_bound O(log n).

실전 예시: 정렬 vs nth_element

// 전체 정렬이 필요 없을 때: k번째 원소만 맞으면 됨
#include <algorithm>
#include <vector>

// ❌ 나쁜 예: 전체 정렬 O(n log n)
int kthBad(std::vector<int> v, int k) {
    std::sort(v.begin(), v.end());
    return v[k - 1];
}

// ✅ 좋은 예: nth_element O(n) 평균
int kthGood(std::vector<int> v, int k) {
    std::nth_element(v.begin(), v.begin() + (k - 1), v.end());
    return v[k - 1];
}

실전 예시: lower_bound로 정렬된 배열 검색

// 정렬된 배열에서 "x 이상인 첫 위치" → O(log n)
#include <algorithm>
#include <vector>

int countGreaterOrEqual(const std::vector<int>& sorted, int x) {
    auto it = std::lower_bound(sorted.begin(), sorted.end(), x);
    return std::distance(it, sorted.end());
}

bool exists(const std::vector<int>& sorted, int x) {
    return std::binary_search(sorted.begin(), sorted.end(), x);
}

실전 예시: partial_sort, accumulate

#include <algorithm>
#include <numeric>
#include <vector>

// 상위 3개만 정렬 (나머지는 무순서)
void topK(std::vector<int>& v, int k) {
    std::partial_sort(v.begin(), v.begin() + k, v.end());
}

// 합계, 곱 등
int sum = std::accumulate(v.begin(), v.end(), 0);
long long product = std::accumulate(v.begin(), v.end(), 1LL, std::multiplies<>());

알고리즘 선택 플로우

flowchart TD
  A[검색이 필요한가?] --> B{정렬되어 있나?}
  B -->|아니오| C["find: O(n)"]
  B -->|예| D["lower_bound / binary_search..."]
  E[k번째 원소 필요?] --> F{한 번만?}
  F -->|예| G["nth_element: O(n)"]
  F -->|여러 번| H["priority_queue: O(log k) pe..."]
  I[전체 정렬 필요?] --> J["sort: O(n log n)"]

6. 상황별 컨테이너 선택 표

상황추천이유
일반 배열처럼 쓰기, 인덱스 접근 많음vectorO(1) 접근, 캐시 친화
앞뒤 삽입/삭제 많음deque앞뒤 O(1)
키로 값 조회, 순서 불필요unordered_map평균 O(1)
키 순서·범위 쿼리 필요mapO(log n), 정렬 유지
중복 없이 존재 여부만unordered_setO(1) 평균
최대/최소 반복 추출priority_queueO(log n) push/pop
정렬된 상태 유지하며 삽입/삭제set / mapO(log n)

한 줄 요약

  • 기본 시퀀스: vector.
  • 키→값 매핑, 순서 상관 없음: unordered_map.
  • 정렬/범위 필요: map·set.
  • 최대/최소 반복: priority_queue.

실전 시나리오: 문제 유형별 추천 조합

문제 유형추천 STL 조합이유
DP, 그리디 (인덱스 접근)vectorO(1) 접근, reserve로 재할당 방지
BFS/DFS (큐/스택)deque + vector앞뒤 삽입/삭제, 인접 리스트
해시 (두 수의 합, 빈도)unordered_mapO(1) 검색
정렬된 구조 (범위 쿼리)map/setlower_bound, k번째 키
다익스트라, 이벤트 스케줄priority_queue최소/최대 O(log n) 추출
k번째 원소 (일회성)nth_elementO(n) 평균
k번째 원소 (동적 쿼리)priority_queue 크기 KO(n log k)

7. 자주 하는 실수와 해결법

실수 1: vector 앞쪽에 반복 삽입

증상: “맨 앞에 추가” 문제에서 시간 초과.

원인: vector::insert(begin(), x)는 O(n). N번 반복 시 O(n²).

해결:

// ❌ 나쁜 예
std::vector<int> v;
for (int i = 0; i < n; ++i) {
    v.insert(v.begin(), a[i]);
}

// ✅ 좋은 예 1: deque
std::deque<int> d;
for (int i = 0; i < n; ++i) {
    d.push_front(a[i]);
}

// ✅ 좋은 예 2: 뒤에 넣고 나중에 reverse
std::vector<int> v;
for (int i = 0; i < n; ++i) v.push_back(a[i]);
std::reverse(v.begin(), v.end());

실수 2: 정렬된 배열인데 find 사용

증상: 이진 탐색 문제인데 선형 탐색으로 풀어 시간 초과.

원인: std::find는 O(n). 정렬된 범위에서는 lower_bound가 O(log n).

해결:

// ❌ 나쁜 예
auto it = std::find(v.begin(), v.end(), x);  // O(n)

// ✅ 좋은 예
auto it = std::lower_bound(v.begin(), v.end(), x);  // O(log n)
if (it != v.end() && *it == x) { /* 찾음 */ }

실수 3: map을 “존재 여부”만 쓸 때 사용

증상: 키 존재 여부만 확인하는데 map 사용 → 불필요한 O(log n).

원인: 순서가 필요 없으면 unordered_map/unordered_set이 평균 O(1).

해결:

// ❌ 나쁜 예: 순서 불필요한데 map
std::map<int, bool> seen;
if (seen.count(x)) { ... }  // O(log n)

// ✅ 좋은 예
std::unordered_set<int> seen;
if (seen.count(x)) { ... }  // O(1) 평균

실수 4: priority_queue에 커스텀 비교자 잘못 지정

증상: 최소 힙이 필요한데 최대 힙이 됨.

원인: 기본 std::less는 최대 힙. 최소 힙은 std::greater 필요.

해결:

// 최대 힙 (기본): top()이 최대
std::priority_queue<int> maxHeap;

// 최소 힙: std::greater 사용
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

실수 5: reserve/resize 미사용으로 재할당

증상: vector에 push_back만 하는데도 느림.

원인: 크기 예측 가능한데 reserve를 안 하면 재할당 발생.

해결:

// ✅ 요소 개수를 미리 알 때
std::vector<int> v;
v.reserve(n);
for (int i = 0; i < n; ++i) {
    v.push_back(read());
}

실수 6: 빈 컨테이너에 top/front/back 접근

증상: 런타임 크래시 또는 undefined behavior.

원인: priority_queue::top(), vector::front() 등은 빈 상태에서 호출하면 UB.

해결:

// ❌ 위험
int x = pq.top();  // pq가 비어있으면 UB

// ✅ 안전
if (!pq.empty()) {
    int x = pq.top();
}

실수 7: erase-while-iterate 시 반복자 무효화

증상: 순회 중 삭제 시 크래시 또는 무한 루프.

원인: vector::erase 후 기존 반복자 무효화.

해결:

// ✅ erase 반환값 사용
for (auto it = v.begin(); it != v.end(); ) {
    if (condition(*it)) {
        it = v.erase(it);
    } else {
        ++it;
    }
}

실수 8: unordered_map에 커스텀 타입 키 사용 시 해시/비교 미정의

증상: 컴파일 에러.

원인: unordered_map은 키에 대해 hash와 operator== 필요.

해결:

struct Point {
    int x, y;
    bool operator==(const Point& o) const {
        return x == o.x && y == o.y;
    }
};

struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

std::unordered_map<Point, int, PointHash> m;

8. 베스트 프랙티스

1. const 참조로 전달

// ❌ 값 복사 (큰 컨테이너에 비효율)
void process(std::vector<int> v);

// ✅ const 참조
void process(const std::vector<int>& v);

2. 범위 기반 for와 auto

// ✅ 읽기 전용
for (const auto& x : v) { ... }

// ✅ 복사 필요 시
for (auto x : v) { ... }

// ✅ 인덱스 필요 시
for (size_t i = 0; i < v.size(); ++i) { ... }

3. 구조화된 바인딩 (C++17)

for (const auto& [k, v] : map) {
    std::cout << k << " -> " << v << "\n";
}

4. 알고리즘 + 람다 활용

// 조건에 맞는 요소 개수
int cnt = std::count_if(v.begin(), v.end(),  { return x > 0; });

// 조건 만족하는 첫 위치
auto it = std::find_if(v.begin(), v.end(),  { return x % 2 == 0; });

5. 초기화 리스트 활용

std::vector<int> v = {1, 2, 3, 4, 5};
std::map<std::string, int> m = {{"a", 1}, {"b", 2}};

9. 프로덕션 패턴

패턴 1: 슬라이딩 윈도우 + deque (최대/최소 유지)

// 구간 [i, i+k) 내 최대값을 O(n)에 구하기
#include <deque>
#include <vector>

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
    std::deque<int> dq;  // 인덱스 저장, 내림차순 유지
    std::vector<int> result;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) result.push_back(nums[dq.front()]);
    }
    return result;
}

패턴 2: LRU 캐시 (map + list)

// get/put O(1): map으로 조회, list로 사용 순서 유지
#include <list>
#include <unordered_map>

class LRUCache {
    int capacity;
    std::list<std::pair<int, int>> cache;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> key2it;

public:
    int get(int key) {
        auto it = key2it.find(key);
        if (it == key2it.end()) return -1;
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }
    void put(int key, int value) {
        auto it = key2it.find(key);
        if (it != key2it.end()) {
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        if (cache.size() == static_cast<size_t>(capacity)) {
            key2it.erase(cache.back().first);
            cache.pop_back();
        }
        cache.emplace_front(key, value);
        key2it[key] = cache.begin();
    }
};

패턴 3: Top-K 빈도 (unordered_map + vector + partial_sort)

// 빈도 상위 k개 원소
#include <unordered_map>
#include <vector>
#include <algorithm>

std::vector<int> topKFrequent(const std::vector<int>& nums, int k) {
    std::unordered_map<int, int> freq;
    for (int x : nums) ++freq[x];

    std::vector<std::pair<int, int>> pairs(freq.begin(), freq.end());
    std::partial_sort(pairs.begin(), pairs.begin() + k, pairs.end(),
         { return a.second > b.second; });

    std::vector<int> result;
    for (int i = 0; i < k; ++i) result.push_back(pairs[i].first);
    return result;
}

패턴 4: 이벤트 기반 스케줄링 (priority_queue)

// (시간, 이벤트) 최소 힙으로 가장 빠른 이벤트부터 처리
#include <queue>
#include <vector>

void processEvents(std::vector<std::pair<int, int>> events) {
    std::priority_queue<std::pair<int, int>,
        std::vector<std::pair<int, int>>,
        std::greater<>> pq(events.begin(), events.end());
    while (!pq.empty()) {
        auto [t, id] = pq.top();
        pq.pop();
        // 처리...
    }
}

10. 성능 최적화 팁

팁 1: vector는 reserve로 재할당 최소화

std::vector<int> v;
v.reserve(100000);  // 한 번에 할당
for (int i = 0; i < 100000; ++i) v.push_back(i);

팁 2: 정렬된 범위에서는 이진 탐색

작업비정렬정렬됨
존재 여부find O(n)binary_search O(log n)
첫 위치-lower_bound O(log n)
마지막 다음 위치-upper_bound O(log n)

팁 3: k번째 원소만 필요하면 nth_element

// 전체 정렬 O(n log n) 대신
std::nth_element(v.begin(), v.begin() + k, v.end());  // O(n) 평균

팁 4: 중복 제거 후 정렬은 unique + erase

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

팁 5: emplace_back으로 임시 객체 생성 최소화

// push_back: 임시 객체 생성 후 이동
v.push_back(MyClass(1, 2));

// emplace_back: 인자만 전달해 컨테이너 내부에서 직접 생성
v.emplace_back(1, 2);

팁 6: 반복자 무효화 주의

vector에서 insert/erase 후에는 기존 반복자가 무효화될 수 있습니다. 삭제하면서 순회할 때는 erase가 반환하는 다음 유효 반복자를 사용하세요.

// ✅ 올바른 erase-while-iterate 패턴
for (auto it = v.begin(); it != v.end(); ) {
    if (condition(*it)) {
        it = v.erase(it);  // erase가 다음 유효 반복자 반환
    } else {
        ++it;
    }
}

팁 7: unordered_map reserve

std::unordered_map<int, int> m;
m.reserve(10000);  // rehash 최소화

11. 구현 체크리스트

코테 전 STL 선택 체크리스트:

  • 시퀀스: 기본은 vector. 앞 삽입 많으면 deque.
  • 키 검색: 순서 불필요하면 unordered_map/unordered_set.
  • 정렬/범위 쿼리: map/set.
  • 최대/최소 반복: priority_queue (최소 힙은 std::greater).
  • 정렬된 검색: lower_bound/binary_search, find 금지.
  • k번째 원소: nth_element 또는 priority_queue 크기 K 유지.
  • vector 크기 예측 가능: reserve 호출.
  • 반복 중 삭제: erase 반환값으로 다음 반복자 사용.
  • 빈 컨테이너 접근 전: empty() 체크.

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

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

  • C++ 컨테이너 선택 가이드 | vector/list/deque/map/set 상황별 선택과 성능 최적화
  • C++ map/unordered_map | “해시맵” 완벽 정리 [성능 비교]
  • C++ 코딩 테스트 | “백준·프로그래머스” 알고리즘 유형별 STL 활용법

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

STL 치트시트, 시간복잡도, vector map unordered_map, priority_queue 등으로 검색하시면 이 글이 도움이 됩니다.

빠른 참조: 연산별 대표 함수

목적추천 함수/컨테이너복잡도
끝에 추가vector::push_backO(1) amort
앞에 추가deque::push_frontO(1)
키 존재 여부unordered_set::countO(1) 평균
정렬된 검색lower_bound, binary_searchO(log n)
k번째 원소nth_elementO(n) 평균
최소/최대 추출priority_queue::top + popO(1) + O(log n)

정리

구분컨테이너/알고리즘핵심 복잡도
시퀀스vector접근 O(1), 끝 추가 O(1)
시퀀스deque앞뒤 추가/삭제 O(1)
연관map, set삽입/검색 O(log n), 정렬 유지
연관unordered_map, set삽입/검색 O(1) 평균
어댑터priority_queuepush/pop O(log n), top O(1)
알고리즘sortO(n log n)
알고리즘binary_search, lower_boundO(log n), 정렬된 범위

코테에서는 vector + unordered_map + priority_queue 조합이 자주 쓰이고, “정렬된 키”가 필요할 때만 map/set을 넣으면 됩니다. 10번 시리즈의 STL 내용을 성능 관점에서만 이 표로 압축해 두었다고 보면 됩니다.

자주 묻는 질문 (FAQ)

Q. vector와 list 중 뭘 써야 하나요?

A. 코테에서는 거의 항상 vector가 맞습니다. list는 중간 삽입/삭제가 매우 많고 인덱스 접근이 전혀 없을 때만 고려합니다. 앞쪽 삽입이 많다면 deque를 쓰세요.

Q. map과 unordered_map 중 뭘 써야 하나요?

A. 키 정렬이나 범위 쿼리(lower_bound, k번째 키 등)가 필요하면 map. “존재 여부”나 “값 조회”만 필요하면 unordered_map이 평균적으로 더 빠릅니다.

Q. priority_queue에서 최소 힙은 어떻게 만들죠?

A. 세 번째 템플릿 인자에 std::greater<int>를 넣습니다: std::priority_queue<int, std::vector<int>, std::greater<int>>.

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

A. vector vs list, map vs unordered_map, priority_queue 등 STL 연산별 시간복잡도와 어떤 상황에 어떤 자료구조를 쓸지 표로 정리합니다. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

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

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

Q. 더 깊이 공부하려면?

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

실전 체크리스트

실무에서 이 개념을 적용할 때 확인해야 할 사항입니다.

코드 작성 전

  • 이 기법이 현재 문제를 해결하는 최선의 방법인가?
  • 팀원들이 이 코드를 이해하고 유지보수할 수 있는가?
  • 성능 요구사항을 만족하는가?

코드 작성 중

  • 컴파일러 경고를 모두 해결했는가?
  • 엣지 케이스를 고려했는가?
  • 에러 처리가 적절한가?

코드 리뷰 시

  • 코드의 의도가 명확한가?
  • 테스트 케이스가 충분한가?
  • 문서화가 되어 있는가?

이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.

한 줄 요약: STL 컨테이너·알고리즘 시간복잡도를 알면 코테에서 자료구조 선택이 쉬워집니다. 다음으로 가상 함수·vtable(#33-1)를 읽어보면 좋습니다.

이전 글: C++ 코테 압축 #32-2: 문자열 파싱

다음 글: [C++ 면접 #33-1] 가상 함수(Virtual Function)와 vtable의 동작 원리

관련 글

  • C++ 백준/프로그래머스 C++ 세팅과 입출력 최적화 한 번에 정리 [#32-1]
  • C++ 문자열 파싱 완벽 가이드 | stringstream·getline·제로카피·성능 벤치마크
  • C++ 메모리 풀 완벽 가이드 | 객체 풀·슬랩·아레나·std::pmr 실전 [#32-2]
  • C++ map vs unordered_map 심층 비교 |
  • C++ 코딩 테스트 |