[C++] 우선 순위 큐(Priority Queue) / 힙(Heap) : 프로그래머스 스코빌 지수(Scoville) 문제 풀이
오늘의 주제는 '우선순위 큐'이다. 이는 내부적으로 '힙(Heap)' 자료구조를 구현하고 있기 때문에 함께 익혀보도록 하자. 또한 우선순위 큐를 활용한 프로그래밍 문제를 풀어보며 응용하는 시간도 가져보자. Priority Queue란? C++의 컨테이너 어댑터인 priority queue는 큐의 원소 중 가장 큰 값을 우선 순위로 두고 오름 차순으로 원소들을 배열하는 큐의 한 종류이다. 어떤 원소의 삽입(push)나 삭제(pop)가 발생할 경우 큐의 우선순위에 맞추어 정렬한다. 자료구조 Heap으로 구현되었기에 push에 의한 정렬은 O(logN)의 시간 복잡도를 가진다. 사용법과 기본 매서드는 아래와 같다. 1. priority_queue 선언 헤더 파일를 include 해준다: #include pq;..
Study/C++
2021. 10. 23. 15:37