알고리즘 대회에서의 C++ STL 효율적 활용 가이드

STL 의 기본 개념과 구성 요소

C++ 표준 템플릿 라이브러리 (Standard Template Library, 이하 STL) 는 다양한 자료 구조와 알고리즘을 범용적으로 제공하는 템플릿 클래스 모음입니다. 개발자의 재구성을 최소화하고 코드의 가독성과 실행 속도를 향상시키는 데 핵심적인 역할을 합니다. 특히 알고리즘 경시대회에서 STL 은 수작업으로 구현하던 복잡한 자료 구조들을 몇 줄의 코드 내로 대체하여 시간 제한을 효율적으로 관리할 수 있게 해줍니다.

STL 은 크게 세 가지 핵심 요소로 나뉩니다. 데이터를 저장하는 컨테이너, 컨테이너 내부 요소를 순회하는 이터레이터, 그리고 데이터 처리를 담당하는 알고리즘입니다. 이 중 알고리즘 대회에서는 주로 앞세 개가 가장 빈번하게 사용됩니다.

이터레이터 (Iterator)

정의 및 역할

이터레이터는 컨테이너 내의 특정 요소에 접근하는 스마트 포인터와 유사한 객체입니다. 이를 통해 배열 인덱싱 없이도 각 요소를 순차적으로 탐색하거나 조작할 수 있습니다.

선언 방식

컨테이너 종류에 따라 특화된 이터레이터 타입이 존재합니다.

  • Normal Iterator: 정방향 순회 (typename Container::iterator)
  • Reverse Iterator: 역방향 순회 (typename Container::reverse_iterator)
  • Const Iterator: 읽기 전용 접근 (typename Container::const_iterator)
std::vector<int> vecData;
// auto 키워드를 활용하면 타입 추론이 가능합니다.
for(auto it = vecData.begin(); it != vecData.end(); ++it) {
    // *it 를 통해 현재 위치 값을 참조
}

메모리 할당 컨테이너

벡터 (Vector)

벡터는 동적으로 크기가 조정되는 배열처럼 동작합니다. 인덱스로 직접 접근이 가능하며, 메모리 부족 시 자동으로 확장이 이루어집니다. 고정된 크기보다 유연성이 필요할 때 적합하며, `vector` 헤더 파일이 필요합니다.

#include <vector>

std::vector<int> numbers;
numbers.push_back(10);      // 끝에 요소 추가
numbers.insert(numbers.begin() + 1, 20); // 중간 삽입
int val = numbers.back();   // 마지막 값 조회
numbers.pop_back();         // 마지막 제거

스트링 (String)

문자열은 단순한 문자 배열 이상의 기능을 가진 객체입니다. C 스타일 문자 배열보다 안전하게 길이를 관리하고 연산이 가능합니다.

#include <string>

std::string text = "Hello";
text += " World";           // 문자열 결합
text.replace(0, 5, "Hi");   // 특정 위치 치환
if(text.find("World") != std::string::npos) {
    // 부분 문자열 검색 성공
}

리스트 (List)

양방향 연결 리스트로 구현되어 있어 임의 지점의 삽입과 삭제가 벡터보다 효율적입니다. 인덱스 접근은 불가능하며 순차 액세스에 최적화됩니다.

#include <list>

std::list<int> linkedData;
linkedData.push_front(1);   // 앞에 추가
linkedData.push_back(2);    // 뒤에 추가
linkedData.erase(linkedData.begin()); // 첫 번째 제거

덱 (Deque)

두 طرف 끝 모두에서 원소의 삽입과 삭제를 지원하는 양방향 큐입니다. 스택과 큐의 기반이 되며, 인덱스 접근도 지원합니다.

#include <deque>

std::deque<int> doubleEndQ;
doubleEndQ.push_front(100);
doubleEndQ.push_back(200);
doubleEndQ.pop_front();     // 앞에 있는 것 삭제
doubleEndQ.pop_back();      // 뒤에 있는 것 삭제

컨테이너 어댑터

스택 (Stack)

LIFO(Last In First Out) 규칙을 따르며, 마지막에 들어온 요소를 먼저 꺼냅니다. `stack` 헤더를 포함해야 합니다.

#include <stack>

std::stack<int> myStack;
myStack.push(50);           // 푸시
int topVal = myStack.top(); // 피크
myStack.pop();              // 팝
bool isEmtpy = myStack.empty();

큐 (Queue)

FIFO(First In First Out) 방식이며, 대기열을 모델링할 때 유용합니다.

#include <queue>

std::queue<int> myQueue;
myQueue.push(1);            // 엔키 (대기열 맨 뒤)
int frontVal = myQueue.front(); // 프론트 조회
myQueue.pop();              // 디큐 (맨 앞 제거)

우선순위 큐 (Priority Queue)

요소의 우선순위에 따라 자동으로 정렬되는 큐입니다. 기본적으로 최대 힙 (큰 순) 을 사용하지만, 최소 힙 설정이 가능합니다. 삽입 및 삭제 복잡도는 로그 시간입니다.

#include <queue>
#include <vector>
#include <functional>

// 큰 값이 위쪽에 있는 기본값
std::priority_queue<int> maxHeap;
maxHeap.push(10);

// 작은 값이 위쪽에 오게 하는 최소 힙 설정
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(5);

사용자 정의 소트 기준

구조체나 객체를 우선순위 큐에 저장할 경우 비교 연산을重载해야 합니다.

struct Task {
    int id;
    int priority;
    
    // 우선순위가 높은 것이 앞에 오도록 정의 (최대 힙 기준 반전)
    bool operator<(const Task& other) const {
        return priority < other.priority; 
    }
};

std::priority_queue<Task> taskQueue;

연관 컨테이너

맵 (Map)

Key-Value 형태의 데이터를 쌍으로 저장하며, 키(Key) 에 따라 자동 정렬됩니다. 내부적으로 레드 - 블랙 트리를 사용하므로 대수 로그 시간복잡도를 가집니다.

#include <map>

std::map<std::string, int> scoreBoard;
scoreBoard["PlayerA"] = 100;       // 자동 생성 및 삽입
scoreBoard.insert({"PlayerB", 200}); // pair 로 삽입

// 탐색
auto it = scoreBoard.find("PlayerA");
if(it != scoreBoard.end()) {
    cout << it->second; // 값 가져오기
}

참고로 기존 키에 대한 `insert` 는 중복 시 무시되지만, 대괄호 연산자 `[]` 를 사용하면 값이 갱신됩니다.

unordered_map

정렬되지 않은 맵으로, 해시 테이블 기반입니다. 평균 상수 시간 \\(O(1)\\) 에 탐색이 가능하나 최악의 경우에 성능 저하가 발생할 수 있으며, 범위查询는 지원되지 않습니다.

#include <unordered_map>

std::unordered_map<int, std::string> dataMap;
dataMap[1] = "One";
dataMap.count(1); // 1 과 같은 키 존재 확인

셋 (Set) 와 멀티셋 (Multiset)

중복된 값을 허용하지 않는 집합과 허용하는 다중집합입니다. 내부 요소는 키 기준으로 항상 정렬되어 있습니다.

#include <set>

std::set<int> uniqueNumbers;
uniqueNumbers.insert(5);
uniqueNumbers.insert(5); // 중복 무시

auto pos = uniqueNumbers.lower_bound(3); // 3 이상인 첫 번째 요소 위치 찾기

알고리즘 틸리티

STL 은 별도의 헤더 파일인 `<algorithm>` 에서 다양한 범용 알고리즘을 제공합니다. 이는 반복문을 없애고 코드를 간결하게 만듭니다.

정렬 (Sort)

특정 범위의 원소를 정렬합니다. 전역 정렬 함수와 유사하게 사용되나 더 안전합니다.

#include <algorithm>
std::vector<int> nums = {3, 1, 4, 1, 5};
std::sort(nums.begin(), nums.end());        // 오름차순
std::sort(nums.rbegin(), nums.rend());      // 내림차순

검색 (Search)

  • find: 선형 검색으로 요소가 있는지 확인합니다.
  • binary_search: 정렬된 범위 내에서 이진 검색을 수행하여 존재 여부만 반환합니다.
// vector 는 이미 정렬되었다고 가정
bool exists = std::binary_search(nums.begin(), nums.end(), 4);
auto foundIt = std::find(nums.begin(), nums.end(), 3);

변환 및 복사

범위 내 모든 요소를 다른 값으로 교체하거나 두 컨테이너의 내용을 교환할 수 있습니다.

std::replace(nums.begin(), nums.end(), 1, 99); // 1 을 99 로 변경
std::swap(vecA, vecB);                         // 벡터 전체 교환
std::reverse(nums.begin(), nums.end());        // 배열 순서 역전

경계 값 탐색

정렬된 컨테이너에서 특정 값의 경계를 찾는 함수들입니다.

  • lower_bound: 지정된 값 이상이 되는 첫 번째 위치
  • upper_bound: 지정된 값보다 큰 첫 번째 위치
auto lb = std::lower_bound(nums.begin(), nums.end(), 5);
auto ub = std::upper_bound(nums.begin(), nums.end(), 5);

태그: C++ STL data-structures algorithms competitive-programming

9월 13일 03:33에 게시됨

인기 태그

©2026 괴물 클럽