알고리즘 템플릿(코테용)

1) 정렬 + 커스텀 비교

기본 문법	특징	대표 상황
sort(v.begin(), v.end());	빠른 정렬, 안정성 없음	일반 정렬
stable_sort(v.begin(), v.end());	안정 정렬 → 입력 순서 유지	입력 순서 유지 필요시
partial_sort(v.begin(), v.begin()+k, v.end());	앞쪽 k개만 정렬	Top-k 문제
nth_element(v.begin(), v.begin()+k, v.end());	k번째 원소 위치, 나머지 정렬 X	중앙값, 순위 구하기
reverse(v.begin(), v.end());	순서 뒤집기	내림차순, 뒤집기 용도
sort(arr, arr+n);	C 배열 정렬	배열 정렬 시 사용
sort(v.begin(), v.end(), greater<int>());	내림차순 정렬	내림차순 정렬 필요할 때

커스텀 비교 (람다)

sort(vec.begin(), vec.end(), [](auto &a, auto &b){
    if (a.first == b.first) return a.second < b.second;
    return a.first < b.first;
});

2) 그리디 + 정렬

int N;
cin >> N;
vector<pair<int,int>> arr(N); // {기준값1, 기준값2}

for (int i = 0; i < N; i++) {
    cin >> arr[i].first >> arr[i].second;
}

// 기준 정렬
sort(arr.begin(), arr.end(), [](auto &a, auto &b) {
    if (a.first == b.first) return a.second < b.second; // tie-breaker
    return a.first < b.first; // 기본 정렬 기준
});

// 탐욕적 선택
int result = 0, last = 0;
for (int i = 0; i < N; i++) {
    if (조건) {  // ex: arr[i].first >= last
        result++;
        last = arr[i].second;
    }
}
cout << result;

3) BFS (최단거리)

queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

4) 이분탐색

int lo=0, hi=n-1, ans=-1;
while (lo<=hi) {
    int mid = (lo+hi)/2;
    if (arr[mid] >= target) { ans = mid; hi = mid-1; }
    else lo = mid+1;
}