3. 필수 알고리즘 및 자료 구조
USACO 문제 해결 능력은 다양한 알고리즘과 자료 구조에 대한 깊은 이해에 달려 있습니다. 다음은 기본적으로 알아야 할 내용입니다.
3.1. 기본 알고리즘
- 완전 탐색 (Brute Force): 모든 가능한 경우의 수를 시도하여 해답을 찾는 방법입니다. N의 크기가 작을 때 유용합니다. (예: N <= 20인 순열, N <= 1000인 단순 반복)
// 1부터 N까지의 합 계산 (완전 탐색 예시)
long long sum = 0;
for (int i = 1; i <= N; ++i) {
sum += i;
}
std::lower_bound, std::upper_bound 함수 사용)// 정렬된 벡터에서 값 찾기 (이진 탐색 예시)
std::vector<int> arr = {1, 3, 5, 7, 9};
int target = 5;
bool found = std::binary_search(arr.begin(), arr.end(), target); // true
3.2. 기본 자료 구조
- 배열 (Arrays) / 벡터 (Vectors): 가장 기본적인 선형 자료 구조입니다.
std::vector는 동적 크기 조절이 가능하여 더 유연합니다. - 맵 (Maps) / 셋 (Sets):
std::map<Key, Value>: 키를 통해 값에 빠르게 접근합니다. (예: 특정 요소의 빈도수 세기)std::set<Value>: 중복을 허용하지 않는 고유한 요소들의 집합을 저장합니다. (예: 방문한 노드 기록)
- 큐 (Queues) / 스택 (Stacks):
std::queue: FIFO (First-In, First-Out) 구조로, 너비 우선 탐색 (BFS)에 사용됩니다.std::stack: LIFO (Last-In, First-Out) 구조로, 깊이 우선 탐색 (DFS) 구현에 보조적으로 사용될 수 있습니다.