코딩테스트에서 자주 쓰이는 STL 총정리

 

코딩테스트 빈출 STL 총 정리

 

오늘은 코딩테스트에서 자주 등장하는 STL들에는 어떤 것들이 있는지 알아보고 구체적인 예시를 통해 사용방법까지 정리해보겠습니다.

---

1. STL이란?

STL(Standard Template Library)은 C++에서 제공하는 표준 라이브러리로, 데이터를 관리하고 조작할 수 있는 컨테이너와 알고리즘, 그리고 이들을 연결하는 이터레이터로 구성됩니다.

 

2. STL 주요 구성 요소

• 컨테이너(Container): 데이터를 저장하고 관리하는 클래스 (e.g., vector, map, set)
• 알고리즘(Algorithm): 정렬, 탐색, 변환 등 데이터 조작을 위한 함수 모음
• 이터레이터(Iterator): 컨테이너와 알고리즘을 연결하는 역할

---

 

반응형

3. 코딩테스트에서 가장 많이 사용하는 STL

 

(1) Vector: 동적 배열

1) 특징

• 동적 배열로, 크기가 가변적입니다.
• 연속적인 메모리 구조로 인해 탐색 속도가 빠릅니다.

2) 주요 메서드

#include <vector>
vector<int> v;
v.push_back(10);  // 요소 추가
v.pop_back();     // 마지막 요소 제거
v.size();         // 크기 확인
v.clear();        // 모든 요소 제거

3) 코딩테스트 활용 예시

문제: 정수 N개를 입력받아 역순으로 출력하기

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    reverse(v.begin(), v.end());
    for (int num : v) {
        cout << num << " ";
    }
    return 0;
}

 

4) 함께 보면 좋은 글

Vector에 대한 자세한 설명 및 사용법은 아래 링크에 자세히 작성했습니다.

2024.12.23 - [STL] - [C언어/C++] STL: Vector 사용법 총 정리: 개념, 주요함수, 예제코드

[C언어/C++] STL: Vector 사용법 총 정리: 개념, 주요함수, 예제코드

 

---

 

(2) Map: 키-값 기반 자료 관리

1) 특징

• 연관 컨테이너로, 데이터를 키-값 쌍(key-value pair)으로 저장합니다.
• 자동으로 키를 정렬하며 탐색, 삽입, 삭제가 O(logN)입니다.

2) 주요 메서드

#include <map>
map<string, int> m;
m["apple"] = 3;  // 삽입
cout << m["apple"] << endl;  // 접근
m.erase("apple");  // 삭제

3) 코딩테스트 활용 예시

문제: 단어 빈도수 세기

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> wordCount;
    while (n--) {
        string word;
        cin >> word;
        wordCount[word]++;
    }
    for (auto &p : wordCount) {
        cout << p.first << ": " << p.second << endl;
    }
    return 0;
}

---

 

(3) Set: 중복 없는 집합

1) 특징

• 중복을 허용하지 않는 데이터 컨테이너입니다.
• 삽입/삭제/탐색이 O(logN)으로 처리됩니다.

2) 주요 메서드

#include <set>
set<int> s;
s.insert(10);  // 삽입
s.erase(10);   // 삭제
cout << s.count(10);  // 존재 여부 확인 (0 또는 1)

 

3) 코딩테스트 활용 예시

문제: 배열에서 중복 제거하기

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n;
    cin >> n;
    set<int> uniqueNumbers;
    while (n--) {
        int num;
        cin >> num;
        uniqueNumbers.insert(num);
    }
    for (int num : uniqueNumbers) {
        cout << num << " ";
    }
    return 0;
}

 

4) 함께 보면 좋은 글

set은 특히 코딩테스트 문제 해결시 굉장히 자주 사용합니다. 이와 관련해서 매우 자세하게 이전 글에 작성했습니다. 

2023.03.13 - [STL] - STL set 구조체활용(1) - 사용법(set은 만능이다?)

STL set 구조체활용(1) - 사용법(set은 만능이다?)

2023.03.30 - [STL] - STL set 구조체 활용 (2)- 정렬 기준 바꾸기

STL set 구조체 활용 (2)- 정렬 기준 바꾸기

2023.03.30 - [STL] - STL set 구조체 활용(3) - set에 구조체 포인터 담기

STL set 구조체 활용(3) - set에 구조체 포인터 담기

2023.04.03 - [STL] - STL set 구조체 활용(4) - 특정 원소에 빠르게 찾기

STL set 구조체 활용(4) - 특정 원소에 빠르게 찾기

---

 

(4) Priority Queue: 우선순위 큐

1) 특징

• 최대 힙(Max-Heap) 또는 최소 힙(Min-Heap) 구조로 구현됩니다.
• 기본 설정은 최대 힙으로, 내림차순 정렬된 값이 먼저 나옵니다.

2) 주요 메서드

#include <queue>
priority_queue<int> pq;          // 최대 힙
priority_queue<int, vector<int>, greater<int>> minHeap;  // 최소 힙

pq.push(5);   // 삽입
pq.pop();     // 가장 큰 값 제거
pq.top();     // 가장 큰 값 접근

3) 코딩테스트 활용 예시

문제: 가장 큰 3개의 값 출력하기

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        pq.push(num);
    }
    for (int i = 0; i < 3 && !pq.empty(); i++) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

 

4) 함께 보면 좋은 글

우선 순위 큐의 경우 STL을 사용하는 것도 좋지만, 직접 Heap을 구현해서 사용하는 경우가 더 많습니다. 왜냐하면 구현이 어렵지 않고, 실행시간 측면에서 직접 구현하는 것이 훨씬 빠르기 때문입니다. 아래 링크에 자세히 정리했습니다.

 

2023.03.12 - [자료구조] - HEAP(1) - 힙 기본 구현 (C언어 구현, index 1부터 시작)

HEAP(1) - 힙 기본 구현 (C언어 구현, index 1부터 시작)

2023.03.12 - [자료구조] - HEAP (2) - 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능)

HEAP (2) - 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능)

 

---

 

(5) Algorithm 헤더: 정렬과 탐색의 기본

1) 주요 함수

#include <algorithm>
vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end());                 // 오름차순 정렬
reverse(v.begin(), v.end());              // 내림차순 정렬
int maxVal = *max_element(v.begin(), v.end()); // 최대값
int minVal = *min_element(v.begin(), v.end()); // 최소값

2) 코딩테스트 활용 예시

문제: 배열에서 가장 큰 값과 작은 값 출력하기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    cout << "최소값: " << *min_element(v.begin(), v.end()) << endl;
    cout << "최대값: " << *max_element(v.begin(), v.end()) << endl;
    return 0;
}

---

 

4. STL을 잘 활용하는 팁

1. 시간 복잡도 이해하기
   • STL마다 동작의 시간 복잡도를 미리 외워두고 문제 상황에 맞는 STL을 선택해야 합니다.
2. 알고리즘과 결합하기
   • STL의 컨테이너와 알고리즘을 적절히 조합하면 코드의 간결성과 효율성을 극대화할 수 있습니다.
3. 자주 나오는 패턴 익히기
   • 코딩테스트에서 자주 나오는 패턴의 STL은 형태를 외워두고 시험시에 바로바로 사용할 수 있어야 제한된 시험시간내에 문제를 풀 수 있습니다.

---