C++ priority_queue 완전 정복: 우선순위 큐 구현과 커스텀 비교자까지 한눈에!

C++ priority_queue 완전 정복: 우선순위 큐 구현과 커스텀 비교자까지 한눈에!

🚀 다익스트라부터 A*까지, C++ 우선순위 큐를 활용한 알고리즘 설계법

안녕하세요. 😊
알고리즘 문제를 풀다 보면 자연스럽게 만나게 되는 자료구조 중 하나가 바로 priority_queue입니다.
특히 C++에서 제공하는 STL은 이 우선순위 큐를 손쉽게 다룰 수 있도록 다양한 기능을 제공하는데요.
단순히 큰 값을 먼저 꺼내는 힙 구조를 넘어서, 커스텀 비교자를 지정하거나 다익스트라와 같은 대표적인 탐색 알고리즘에 활용하는 실전 활용도까지 익혀두면 큰 도움이 됩니다.
이번 포스팅에서는 C++ priority_queue의 개념부터 사용법, 그리고 커스터마이징과 알고리즘 적용까지 하나하나 친절하게 정리해드릴게요.
초보자분들도 충분히 따라오실 수 있도록 쉽게 설명드리니 걱정 마세요!

C++의 priority_queue는 내부적으로 힙(Heap) 자료구조를 기반으로 동작하며, 기본적으로는 최댓값이 먼저 나오는 최대 힙 형태입니다.
하지만 상황에 따라 최솟값을 먼저 꺼내는 최소 힙으로 바꾸거나, 사용자 정의 객체를 기반으로 우선순위를 마음대로 설정할 수도 있다는 점이 정말 매력적인데요.
이 글에서는 STL에서 제공하는 priority_queue의 기본 구조는 물론, 커스텀 정렬 기준 설정법, 실전 예제로는 다익스트라(Dijkstra)와 A* 알고리즘에 어떻게 활용되는지도 함께 살펴보겠습니다.
코딩 테스트를 준비하시거나, 실무에서 성능 좋은 자료구조를 찾고 계신 분들께도 유용한 내용이니 꼭 끝까지 읽어보세요!

🔗 priority_queue란?

C++의 priority_queue는 표준 템플릿 라이브러리(STL)에서 제공하는 컨테이너 어댑터 중 하나로, 내부적으로 힙(heap) 자료구조를 기반으로 동작합니다.
이 구조는 일반적인 큐(Queue)와는 달리 삽입된 요소들 중에서 가장 우선순위가 높은 요소를 먼저 꺼낼 수 있는 특수한 형태입니다.

기본적으로는 최댓값이 가장 높은 우선순위를 가지며, 따라서 큐에서 pop을 할 경우 항상 가장 큰 값이 먼저 제거됩니다.
이는 최대 힙(Max-Heap) 구조로 구현되어 있기 때문입니다.

💬 priority_queue는 내부적으로 make_heap, push_heap, pop_heap 등의 알고리즘을 활용하여 자동으로 힙 속성을 유지합니다.

자료구조의 입장에서 보면, 삽입과 삭제 연산은 모두 O(log N)의 시간 복잡도를 가지기 때문에 효율적입니다.
이는 탐색 알고리즘이나 시뮬레이션 문제 등에서 빠르게 최대값 또는 최소값을 처리해야 하는 상황에서 매우 유용하죠.

이러한 특징 덕분에 다익스트라(Dijkstra), A* 알고리즘, 그리디 알고리즘 등의 구현에서 필수적인 역할을 하며, 특정 상황에서는 BFS보다도 더 빠르고 효율적인 경로 탐색이 가능합니다.

🛠️ 기본 사용법과 특징

C++에서 priority_queue를 사용하려면 #include <queue> 헤더 파일을 포함해야 합니다.
기본적인 사용법은 매우 간단하며, 기본적으로는 내림차순 정렬(최대 힙) 형태로 작동합니다.

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(5);
    pq.push(1);
    pq.push(10);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}
// 출력 결과: 10 5 1

위 예제에서 보듯이 가장 큰 수가 먼저 출력되는 구조입니다.
이는 자동으로 힙 정렬이 적용되기 때문인데요.
실제 정렬 과정을 신경 쓰지 않아도 되므로 매우 편리하게 사용할 수 있습니다.

• 🧱기본 컨테이너는 vector이며, 내부에서 make_heap 방식으로 관리됩니다
• 📈가장 큰 값이 top()으로 접근됩니다
• 🧩push, pop은 O(log N)의 시간 복잡도
• 🚫임의 접근은 지원되지 않음

이처럼 priority_queue는 정렬된 데이터를 빠르게 관리해야 할 때 유용합니다.
다만, 인덱스 접근은 허용되지 않으므로 단순한 배열처럼 사용하는 것은 적합하지 않다는 점도 기억해 두셔야 합니다.

⚙️ 최소 힙으로 바꾸는 방법

기본적으로 C++의 priority_queue는 최대 힙 구조로 작동합니다.
하지만 상황에 따라 최솟값을 먼저 꺼내야 하는 경우도 많기 때문에, 이를 위해 비교자를 지정해 최소 힙(min-heap)으로 바꿔줄 수 있습니다.

방법은 매우 간단합니다.
priority_queue 선언 시 다음과 같이 세 가지 템플릿 인자를 지정하면 됩니다:

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    minHeap.push(10);
    minHeap.push(3);
    minHeap.push(7);

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }
    return 0;
}
// 출력 결과: 3 7 10

위 코드에서 핵심은 std::greater<int>를 세 번째 인자로 전달한 부분입니다.
이렇게 하면 내부 정렬 기준이 오름차순으로 변경되어 가장 작은 값부터 먼저 pop됩니다.

이러한 방식은 다익스트라 알고리즘처럼 가장 짧은 거리부터 탐색이 필요한 알고리즘에서 매우 유용하게 활용됩니다.
따라서 최소 힙 설정은 필수적으로 익혀두셔야 할 테크닉이에요.

🔌 사용자 정의 비교자 설정법

priority_queue는 단순한 int 타입뿐 아니라 구조체나 클래스를 요소로 담을 수도 있습니다.
이때 중요한 것은 우선순위를 판단할 수 있는 기준을 사용자 정의해야 한다는 점인데요.
C++에서는 함수 객체(Functor) 또는 람다 표현식을 통해 비교자를 설정할 수 있습니다.

📌 구조체 비교자 활용 예시

#include <iostream>
#include <queue>
#include <vector>

struct Task {
    int priority;
    std::string name;
};

struct Compare {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority; // 작은 값이 먼저
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, Compare> pq;

    pq.push({3, "Low"});
    pq.push({1, "High"});
    pq.push({2, "Mid"});

    while (!pq.empty()) {
        std::cout << pq.top().name << " ";
        pq.pop();
    }
    return 0;
}
// 출력 결과: High Mid Low

위 예제에서는 priority가 낮을수록 먼저 처리되는 구조로 커스터마이징했습니다.
이처럼 operator()를 오버라이드하면 원하는 기준대로 우선순위를 정할 수 있습니다.

📌 람다 표현식으로 더 간단하게

C++11 이상에서는 람다 표현식을 사용하여 비교자를 더 간단하게 정의할 수 있습니다.

auto cmp = [](const Task& a, const Task& b) {
    return a.priority > b.priority;
};

std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq(cmp);

이런 방식으로 비교자만 잘 정의하면, 다양한 객체 타입과 우선순위 기준을 유연하게 적용할 수 있어서 실무에서도 자주 사용됩니다.

💡 다익스트라와 A* 알고리즘 활용 예시

priority_queue는 단순 정렬용이 아니라 탐색 알고리즘의 핵심 자료구조로도 널리 사용됩니다.
그 대표적인 예가 바로 다익스트라(Dijkstra)와 A* (에이스타) 알고리즘입니다.

📌 다익스트라 알고리즘에서의 활용

다익스트라는 최단 경로를 구할 때 가장 많이 쓰이는 알고리즘 중 하나이며, 매 단계마다 가장 비용이 작은 노드를 꺼내야 하므로 최소 힙이 필요합니다.

using pii = std::pair<int, int>; // {비용, 노드 번호}
priority_queue<pii, vector<pii>, greater<pii>> pq;

위와 같이 greater<> 비교자를 사용해 최소 비용 노드부터 처리하도록 구현합니다.
이를 통해 전체 시간 복잡도는 O(E log V)로 최적화됩니다.

📌 A* 알고리즘에서의 활용

A* 알고리즘은 휴리스틱을 이용해 목적지까지의 예상 비용을 고려한 경로 탐색을 진행합니다.
이 경우에도 priority_queue를 통해 현재까지의 비용 + 예상 비용(f-score)이 가장 작은 노드를 우선적으로 처리합니다.

struct Node {
    int f, x, y;
};

struct Compare {
    bool operator()(const Node& a, const Node& b) {
        return a.f > b.f; // f-score 기준 최소 힙
    }
};

priority_queue<Node, vector<Node>, Compare> openSet;

결론적으로 priority_queue는 알고리즘 문제 풀이의 성능과 효율성을 좌우할 수 있는 핵심 도구라고 할 수 있습니다.
문제 유형에 따라 적절히 커스터마이징해서 사용하는 연습이 중요합니다.

❓ 자주 묻는 질문 (FAQ)

📌 priority_queue는 알고리즘을 바꾸는 핵심 도구입니다

이번 글에서는 C++의 priority_queue를 활용하는 다양한 방법에 대해 살펴보았습니다.
기본적인 최대 힙 구조부터 시작해, 최소 힙으로 전환하는 방법, 사용자 정의 객체를 비교자로 사용하는 고급 기법까지 하나하나 따라오셨다면 이제 웬만한 상황에서는 자유롭게 사용할 수 있을 거예요.
특히 다익스트라, A* 알고리즘처럼 우선순위 큐가 핵심이 되는 문제에서 priority_queue의 중요성은 이루 말할 수 없습니다.

기본 동작 방식, 시간 복잡도, STL 템플릿 구성 등은 물론, 실전에서 자주 접하는 문제 유형에서 어떻게 응용할 수 있는지도 예제로 안내해드렸습니다.
만약 여러분이 알고리즘 성능 향상이나 코딩 테스트 준비를 하고 계신다면, 반드시 익혀야 할 자료구조임이 분명합니다.

지금 바로 간단한 문제부터 직접 구현해 보세요.
코드는 손에 익을수록 강력한 무기가 됩니다! 💪

🏷️ 관련 태그:priority_queue, C++ 자료구조, 알고리즘 성능, 최소 힙, 최대 힙, 다익스트라 알고리즘, A* 알고리즘, C++ STL, 힙 정렬, 코딩 테스트 준비