알고리즘 문제 해결을 위한 C++ STL 핵심 가이드

알고리즘 문제 풀이, 특히 경쟁 프로그래밍 환경에서는 C++ 표준 라이브러리(STL)를 효율적으로 활용하는 것이 매우 중요합니다. STL은 다양한 자료구조와 알고리즘을 제공하여 코드를 간결하고 빠르게 작성할 수 있도록 돕습니다. 여기서는 알고리즘 문제 해결에 필수적인 STL 요소들을 살펴보겠습니다.

STL 핵심 요소

#include <algorithm>

std::sort()

std::sort 함수는 배열이나 컨테이너의 특정 범위를 정렬할 때 사용됩니다. 시간 복잡도는 일반적으로 O(N log N)입니다.

  • 기본 사용법: sort(begin, end)
  • begin: 정렬을 시작할 요소의 주소 (또는 이터레이터)
  • end: 정렬을 끝낼 요소의 다음 위치 주소 (또는 이터레이터)

예시: 정수 배열 오름차순 정렬

#include <iostream>
#include <vector>
#include <algorithm> // std::sort

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};
    std::sort(numbers.begin(), numbers.end()); // 오름차순 정렬 (기본)

    for (int num : numbers) {
        std::cout << num << " "; // 출력: 1 2 5 8 9
    }
    std::cout << std::endl;
    return 0;
}

내림차순 정렬은 std::greater<Type>() 객체를 세 번째 인자로 전달하여 수행할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // std::greater

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};
    std::sort(numbers.begin(), numbers.end(), std::greater<int>()); // 내림차순 정렬

    for (int num : numbers) {
        std::cout << num << " "; // 출력: 9 8 5 2 1
    }
    std::cout << std::endl;
    return 0;
}

사용자 정의 구조체나 클래스를 정렬할 때는 다음과 같은 두 가지 방법이 주로 사용됩니다:

  1. operator< 오버로딩: 구조체 내부에 operator<를 정의하면 std::sort가 이 연산자를 사용하여 정렬 기준을 판단합니다. 주로 오름차순 정렬에 사용됩니다.
  2. 사용자 정의 비교 함수 (Comparator): 별도의 함수나 람다식을 작성하여 std::sort의 세 번째 인자로 전달합니다. 이는 더 유연하며, 오름차순/내림차순 뿐만 아니라 복잡한 조건으로 정렬할 때 유용합니다.

예시: 구조체 정렬 (사용자 정의 비교 함수)

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

struct Item {
    int id;
    double value;

    // operator< 오버로딩 (기본적으로 id 기준 오름차순)
    // bool operator<(const Item& other) const {
    //     return id < other.id;
    // }
};

// 사용자 정의 비교 함수: value를 기준으로 내림차순 정렬
bool compareItemsDesc(const Item& a, const Item& b) {
    return a.value > b.value; // a의 value가 b보다 크면 a를 먼저 둔다 (내림차순)
}

// 사용자 정의 비교 함수: id를 기준으로 오름차순 정렬
bool compareItemsAsc(const Item& a, const Item& b) {
    return a.id < b.id; // a의 id가 b보다 작으면 a를 먼저 둔다 (오름차순)
}


int main() {
    std::vector<Item> items = {{1, 10.5}, {3, 5.2}, {2, 12.1}};

    // value 기준 내림차순 정렬
    std::sort(items.begin(), items.end(), compareItemsDesc);
    std::cout << "Value desc sort: " << std::endl;
    for (const auto& item : items) {
        std::cout << "ID: " << item.id << ", Value: " << item.value << std::endl;
    }
    // 예상 출력: {2, 12.1}, {1, 10.5}, {3, 5.2}

    // id 기준 오름차순 정렬 (람다 사용)
    std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.id < b.id;
    });
    std::cout << "\nID asc sort (lambda): " << std::endl;
    for (const auto& item : items) {
        std::cout << "ID: " << item.id << ", Value: " << item.value << std::endl;
    }
    // 예상 출력: {1, 10.5}, {2, 12.1}, {3, 5.2}

    return 0;
}

#include <vector>

std::vector는 동적 배열 역할을 하는 컨테이너입니다. 크기가 자동으로 조절되며, 마지막 요소에 대한 삽입/삭제가 효율적입니다.

std::vector의 주요 멤버 함수:

  • .size(): 현재 저장된 요소의 개수를 반환합니다.
  • .empty(): 벡터가 비어있는지 확인합니다 (true/false).
  • .clear(): 벡터의 모든 요소를 제거하여 비웁니다.
  • .begin(): 첫 번째 요소를 가리키는 이터레이터를 반환합니다.
  • .end(): 마지막 요소의 다음 위치를 가리키는 이터레이터를 반환합니다.
  • .front(): 첫 번째 요소에 대한 참조를 반환합니다.
  • .back(): 마지막 요소에 대한 참조를 반환합니다.
  • .push_back(value): 벡터의 끝에 value를 추가합니다.
  • .pop_back(): 벡터의 마지막 요소를 제거합니다.

예시: std::vector 사용

#include <iostream>
#include <vector>
#include <string>

int main() {
    std::vector fruits; // 문자열을 저장하는 벡터 선언

    fruits.push_back("Apple");
    fruits.push_back("Banana");
    fruits.push_back("Cherry");

    std::cout << "Vector size: " << fruits.size() << std::endl; // 출력: 3

    if (!fruits.empty()) {
        std::cout << "First fruit: " << fruits.front() << std::endl;  // 출력: Apple
        std::cout << "Last fruit: " << fruits.back() << std::endl;   // 출력: Cherry
    }

    // 인덱스를 이용한 순회
    std::cout << "Fruits (index): ";
    for (size_t i = 0; i < fruits.size(); ++i) {
        std::cout << fruits[i] << " ";
    }
    std::cout << std::endl;

    // 이터레이터를 이용한 순회
    std::cout << "Fruits (iterator): ";
    for (std::vector::iterator it = fruits.begin(); it != fruits.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 범위 기반 for 루프를 이용한 순회 (C++11 이상)
    std::cout << "Fruits (range-based for): ";
    for (const std::string& fruit : fruits) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;

    fruits.pop_back(); // "Cherry" 제거
    std::cout << "After pop_back, size: " << fruits.size() << std::endl; // 출력: 2

    fruits.clear(); // 모든 요소 제거
    std::cout << "After clear, empty: " << std::boolalpha << fruits.empty() << std::endl; // 출력: true

    return 0;
}

#include <queue>

std::queue와 std::priority_queue는 데이터를 특정한 순서로 관리하는 데 사용됩니다.

std::queue (선입선출, FIFO)

std::queue는 먼저 삽입된 요소가 먼저 제거되는 (First-In, First-Out) 자료구조입니다. 덱(deque)을 기반으로 구현됩니다.

  • .push(value): 큐의 뒤에 요소를 삽입합니다.
  • .pop(): 큐의 앞에서 요소를 제거합니다.
  • .front(): 큐의 맨 앞 요소를 참조합니다. (제거하지 않음)
  • .back(): 큐의 맨 뒤 요소를 참조합니다. (제거하지 않음)
  • .empty(): 큐가 비어있는지 확인합니다.
  • .size(): 큐에 있는 요소의 개수를 반환합니다.

예시: std::queue 사용

#include <iostream>
#include <queue>

int main() {
    std::queue<int> myQueue;

    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);

    std::cout << "Queue front: " << myQueue.front() << std::endl; // 출력: 10
    std::cout << "Queue back: " << myQueue.back() << std::endl;   // 출력: 30
    std::cout << "Queue size: " << myQueue.size() << std::endl;   // 출력: 3

    myQueue.pop(); // 10 제거
    std::cout << "After pop, front: " << myQueue.front() << std::endl; // 출력: 20

    while (!myQueue.empty()) {
        std::cout << "Popping: " << myQueue.front() << std::endl;
        myQueue.pop();
    }
    // 출력: Popping: 20, Popping: 30

    return 0;
}

std::priority_queue (우선순위 큐)

std::priority_queue는 힙(heap) 자료구조를 기반으로 하여, 삽입된 요소들 중에서 가장 우선순위가 높은(기본적으로 가장 큰) 요소를 항상 맨 위에 유지합니다. std::queue와 달리 명시적인 clear() 함수는 없지만, 요소를 모두 pop()하거나 새롭게 생성하여 비울 수 있습니다.

  • .push(value): 우선순위 큐에 요소를 삽입합니다.
  • .pop(): 가장 우선순위가 높은(맨 위) 요소를 제거합니다.
  • .top(): 가장 우선순위가 높은(맨 위) 요소를 참조합니다. (제거하지 않음)
  • .empty(): 우선순위 큐가 비어있는지 확인합니다.
  • .size(): 우선순위 큐에 있는 요소의 개수를 반환합니다.

기본적으로 std::priority_queue는 std::less<Type>를 사용하여 가장 큰 요소가 우선순위가 높도록 설정됩니다 (최대 힙, Max-Heap).

#include <iostream>
#include <queue> // std::priority_queue
#include <vector> // priority_queue의 내부 컨테이너로 사용될 수 있음
#include <functional> // std::greater

int main() {
    // 최대 힙 (Max-Heap): 가장 큰 값이 top
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(50);
    max_pq.push(20);

    std::cout << "Max-Heap top: " << max_pq.top() << std::endl; // 출력: 50
    max_pq.pop(); // 50 제거
    std::cout << "Max-Heap top after pop: " << max_pq.top() << std::endl; // 출력: 20

    // 최소 힙 (Min-Heap): std::greater<Type>을 사용하여 가장 작은 값이 top
    std::priority_queue min_pq;
    min_pq.push(10);
    min_pq.push(50);
    min_pq.push(20);

    std::cout << "Min-Heap top: " << min_pq.top() << std::endl; // 출력: 10
    min_pq.pop(); // 10 제거
    std::cout << "Min-Heap top after pop: " << min_pq.top() << std::endl; // 출력: 20

    return 0;
}

사용자 정의 구조체를 std::priority_queue에 사용하려면, 해당 구조체에 대해 비교 연산자 (operator<)를 오버로딩하거나 사용자 정의 비교 함수/객체를 제공해야 합니다. operator<를 오버로딩하면 std::priority_queue는 operator<가 true를 반환하는 요소가 "더 작다"고 판단하여, 기본적으로 operator< 기준 가장 큰 요소가 top이 됩니다. 따라서 최대 힙을 만들려면 '크다고 판단되는 조건'을 operator<에 정의하고, 최소 힙을 만들려면 std::greater와 유사한 커스텀 비교 객체를 사용해야 합니다.

예시: 구조체와 priority_queue (최대 힙)

#include <iostream>
#include <queue>
#include <string>

struct Player {
    std::string name;
    int score;

    // operator< 오버로딩: score가 클수록 우선순위가 높다고 판단 (최대 힙)
    bool operator<(const Player& other) const {
        return score < other.score; // 현재 객체의 score가 other보다 작으면 우선순위 낮음
    }
};

int main() {
    std::priority_queue<Player> players; // 기본: Player::operator< 에 따른 최대 힙

    players.push({"Alice", 1500});
    players.push({"Bob", 2000});
    players.push({"Charlie", 1800});

    std::cout << "Highest score player: " << players.top().name << " (" << players.top().score << ")" << std::endl;
    // 출력: Bob (2000)

    players.pop(); // Bob 제거
    std::cout << "Next highest score player: " << players.top().name << " (" << players.top().score << ")" << std::endl;
    // 출력: Charlie (1800)

    return 0;
}

태그: C++ STL algorithm DataStructure CompetitiveProgramming

10월 26일 12:10에 게시됨