알고리즘 문제 풀이, 특히 경쟁 프로그래밍 환경에서는 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;
}
사용자 정의 구조체나 클래스를 정렬할 때는 다음과 같은 두 가지 방법이 주로 사용됩니다:
operator<오버로딩: 구조체 내부에operator<를 정의하면std::sort가 이 연산자를 사용하여 정렬 기준을 판단합니다. 주로 오름차순 정렬에 사용됩니다.- 사용자 정의 비교 함수 (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;
}