페이지 3: 필수 알고리즘 및 자료 구조

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;
}

• 그리디 (Greedy): 각 단계에서 현재 최적의 선택을 하는 방식입니다. 항상 전체 최적해를 보장하지는 않지만, 특정 문제에서 효과적입니다. (예: 거스름돈 주기, 활동 선택 문제)
• 이진 탐색 (Binary Search): 정렬된 데이터에서 특정 값을 효율적으로 찾는 알고리즘입니다. O(log N)의 시간 복잡도를 가집니다. (예: 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) 구현에 보조적으로 사용될 수 있습니다.