우선순위 큐 (priority_queue)
우선순위 큐를 비유하자면, 가장 중요한 일이 제일 먼저 처리되는 대기열이라고 할 수 있다.
우선순위 큐의 간단한 특징
- 내부적으로 힙(Heap) 자료구조를 사용.
- 삽입, 삭제(pop)은 항상
O(log N)이고, top()(가장 우선순위 높은 원소 조회)은O(1)이다. - 가장 큰/작은 원소를 순식간에 추출해야 하는 문제에 최적.
C++ STL에서priority_queue는 기본적으로 가장 큰 원소가 먼저 나오는(최대 힙)구조이다. 즉, 우선순위가 높다는 것은 값이 크다는 것을 의미.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(5);
pq.push(2);
pq.push(8);
pq.push(3);
// top() : 가장 우선순위가 높은 원소(여기선 가장 큰 값)를 반환
cout << "현재 top: " << pq.top() << endl; // 8
pq.pop(); // top(8) 제거
cout << "새로운 top: " << pq.top() << endl; // 5
}- 가장 큰 값부터 꺼내는 구조 (최대 힙)
push(),pop(): 삽입/삭제 연산은 모두 평균O(log n)top(): 가장 우선순위가 높은(가장 큰) 원소 조회,O(1)
위에서 말한 것 처럼 기본적으로 최대 힙 구조지만, 최소 힙도 가능하다. 바로 세 번째 템플릿 인자를 greater<자료형>로 주면 된다.
//최소 힙
priority_queue<int, vector<int>, greater<int>> minPq;
minPq.push(10);
minPq.push(5);
minPq.push(20);
cout << minPq.top() << endl; // 5여기서 세 번째 인자로 넣는 compare operator에 greater<int>를 넣어줌으로서 비교 기준을 세우는 것이다. 즉, 여기서는 "더 큰 것이 우선순위가 더 낮다"라는 의미로 쓰인다.
원래, 우선순위 큐는 내부적으로 벡터를 이용해서 생략을 해도 되지만 세 번째 템플릿 인자를 줘야하는 이슈가 있어서 두 번째 인자(vector<int>)도 그냥 명시적으로 써준 것이라고 보면 된다.
만약, 객체(예: 구조체)들이 특정 기준으로 우선순위를 가져야 한다면 사용자 정의 비교 함수를 넣어줄 수 있다.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
// 예시: 이름(name)과 점수(score)를 담은 구조체
struct Student {
string name;
int score;
};
// 점수가 높은 순으로 우선순위가 결정되게 하고 싶다면
struct Compare {
bool operator()(const Student &a, const Student &b) {
return a.score < b.score;
// a < b면 true → a 우선순위가 낮다고 판단
// 즉, score 큰게 먼저 나오게 (내림차순)
}
};
int main() {
// 이제 여기에 세번째 인자로 커스텀 오퍼레이터를 넣음
priority_queue<Student, vector<Student>, Compare> pq;
pq.push({"tom", 95});
pq.push({"goong", 80});
pq.push({"rtan", 99});
cout << pq.top().name << " " << pq.top().score << endl; // rtan 99
}순열
순열(Permutation) 관련 문제를 만났을 때 next_permutation / prev_permutation 을 쓰면 된다! next_permutation은 주어진 범위를 사전순(lexicographical)으로 다음 순열로 바꿔주고요. prev_permutation은 주어진 범위를 사전순으로 이전 순열로 바꿔준다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3};
// 현재 순열 출력
for(int x : v) cout << x << " "; // 1 2 3
cout << endl;
// 다음 순열 한 번만 구하기
next_permutation(v.begin(), v.end());
// 바뀐 순열 출력
for(int x : v) cout << x << " "; // 1 3 2
cout << endl;
}다만, 모든 순열을 구하고 싶다면 아래처럼 할 수 있다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> v = {1, 2, 3};
do {
for (int x : v) cout << x << " ";
cout << endl;
} while (next_permutation(v.begin(), v.end())); // 다음 순열이 존재하는 한 계속 탐색
}실행 코드
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 K번째 값 찾기
코딩 테스트를 하다보면 K번째 값을 찾아야 되는 요구사항도 은근히 많다. 이럴 때는 nth_element 를 사용할 수 있다. 이 친구는 파티션(pivot) 기반으로 n번째로 작은 원소를 배열의 n번째 위치로 보낸 뒤, 그 왼쪽은 n번째보다 작은 원소들, 오른쪽은 n번째보다 큰 원소들 이런 식으로 반정렬을 해준다.
nth_element는 평균 시간복잡도가 O(n) 다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> v = {9, 1, 4, 7, 2, 6};
nth_element(v.begin(), v.begin() + 2, v.end());
cout << "3번째로 작은 원소: " << v[2] << endl;
}