gksrudtlr
|2025. 2. 10. 13:05
우선순위 큐
- 우선순위 큐란?
- queue와 달리 선입 선출이 아니라 들어온 값들의 우선순위가 부여되어 우선순위 순서대로 되어있는 큐
- 특징
- 내부적으로는 힙(Heap, 메모리구조 Heap과 다름) 구조를 사용
- 삽입, 삭제는 항상 O(logN)이고, top()은 가장 우선 순위가 높은 원소 조회로 O(1)이다
- 가장 큰/작은 원소를 순식간에 추출해야 하는 문제에 최적
- 생김
- 첫번째 인자 : 자료형
- 두번째 인자 : vector형 컨테이너
- 세번째 인자 : 템플릿 함수로 Compare함수를 만들어 넣던지, greater<T>를 넣어준면 큰 값이 낮은 순위가 되는오름차순으로 된다
순열
- 순열이란?
- 순서가 정해져있는 수의 배열
- STL에 제공되는 next_permutation(사전순 순열)/prev_permutation(사전 반대순 순열)을 사용하면 편하게 값을 구할 수 있다
- 이미 정렬되어 있는 상태의 컨테이너를 사용해야 한다
K번째 값 찾기
- nth_element
- 이 값은 pivot기반으로 n번째로 작은 원소를 배열 의 n번째 위치로 보낸 뒤, 그 왼쪽은 n보다 작은 원소, 오른쪽은 큰 원소로 반 정렬 해준다
- 이는 퀵소트와 유사함
- 평균 시간 복잡도는 O(n)
- std::nth_element(Start*, pivot, End*)
