💯챌린지반 복습 노트(3)

우선순위 큐

선입선출이지만 우선 출이며, 가장 중요한 일이 제일 먼저 처리되는 대기열이라고 생각하면 된다.
우선 순위 큐의 간단한 특징

• 내부적으로 힙(heap) 자료구조를 사용한다
• 삽입 삭제는 항상 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);
    
    //top() 가장 우선순위가 높은 원소를 반환
    cout<<"현재 top"<<pq.top()<<endl; //8
    
    pq.pop; //top(8) 제거
}

최소 힙도 가능한데 세 번째 템플릿 인자를 greater<자료형>으로 주면 된다.

priority_queue<int, vector<int>, greater<int>> minPq;
minPq.push(10);
minPq.push(5);

cout<<minPq.top()<<endl; // 5

---

순열

순열과 관련한 문제를 만났을 때는 next_permutation/ prev_permutation을 쓰면 된다. next_permutation은 주어진 범위를 사전순으로 다음 순열로 바꿔주고 prev_permutation은 주어진 범위를 사전순으로 이전 순열로 바꿔주는 것이다

원본 데이터는 정렬 상태여야 한다. "주어진 순열의 모든 순열 생성", "사전 순으로 특정 순열 찾기"와 같은 문제를 만났을 대 유용하다.

int main()
{
	vector<int> v= {1,2,3};
   	for(int x: v) cout<<x<<" "; //123
    cout<<endl;
    
    next_permutation(v.begin(), v.end()));//132
    
    for(int x: v) cout<<x<< " ";
    cout<<endl;
}

k번째 값 찾기

nth_element를 사용하면 된다 이것은 파티션 기반으로 n번째로 작은 원소를 배열의 n번째 위치로 보낸 뒤 그 왼쪽은 n보다 작은 원소를, 오른쪽은 n번째보다 큰 원소들로 반정렬을 한다

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