99클럽 코테 스터디 23일차 TIL C++ 우선순위 큐(priority_queue와 multiset), 포인터와 참조변수(*it과 &it)

1. 우선순위 큐란?

우선순위 큐는 일반적인 큐와는 달리, 각 요소가 우선순위를 가지고 있어 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조입니다. 예를 들어, 긴급 상황에서 긴급도가 높은 환자가 먼저 치료받는 병원의 대기열과 같은 개념을 생각할 수 있습니다.

C++에서는 우선순위 큐를 구현할 수 있는 여러 가지 방법이 있으며, 여기서는 priority_queue와 multiset 두 가지를 중심으로 살펴보겠습니다.

2. priority_queue를 사용한 최대 힙과 최소 힙 구현

C++의 priority_queue는 기본적으로 최대 힙으로 구현되어 있어, 큰 값이 먼저 나오도록 정렬됩니다. 즉, 기본 설정에서는 큰 값이 높은 우선순위를 가지게 됩니다. 하지만 최소 힙을 만들고자 한다면 다음과 같이 설정할 수 있습니다:

• 최대 힙: priority_queue<int>
• 최소 힙: priority_queue<int, vector<int>, greater<int>>

예제 코드: 최소 힙을 사용한 스코빌 지수 문제 풀이

아래는 priority_queue를 사용하여 최소 힙으로 스코빌 지수 문제를 해결하는 코드입니다:

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

using namespace std;

int solution(vector<int> scoville, int K) {
    // 최소 힙을 만들기 위한 priority_queue 선언
    priority_queue<int, vector<int>, greater<int>> queue(scoville.begin(), scoville.end());

    int answer = 0;

    // 모든 원소가 K 이상이 될 때까지 반복
    while (queue.top() < K) {
        // 원소가 2개 이상 있어야 섞을 수 있음
        if (queue.size() < 2) {
            return -1; // 섞을 수 없는 경우, 목표 도달 불가능
        }

        // 두 개의 최소 원소를 꺼내서 섞음
        int top1 = queue.top();
        queue.pop();
        int top2 = queue.top();
        queue.pop();

        // 새로운 스코빌 지수를 계산하고 다시 힙에 넣음
        int new_item = top1 + (top2 * 2);
        queue.push(new_item);

        // 섞는 횟수를 증가시킴
        answer++;
    }

    return answer;
}

위 코드는 priority_queue를 사용해 최소 힙을 구성하고, 가장 작은 두 값을 꺼내어 새로운 값을 만들어 다시 힙에 삽입하는 과정을 반복합니다.

priority_queue의 커스텀 우선순위 설정

priority_queue에서는 세 번째 인자로 커스텀 비교 함수를 전달하여 우선순위를 변경할 수 있습니다. 예를 들어, 사용자 정의 구조체를 우선순위 큐에 넣고자 할 때 다음과 같은 방식으로 커스텀 우선순위를 지정할 수 있습니다:

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

using namespace std;

struct Task {
    int priority;
    string description;
};

// 비교 함수 정의 (우선순위가 높은 순으로 정렬)
struct CompareTask {
    bool operator()(Task const& t1, Task const& t2) {
        return t1.priority < t2.priority; // 우선순위가 높을수록 먼저 처리됨
    }
};

int main() {
    priority_queue<Task, vector<Task>, CompareTask> taskQueue;

    taskQueue.push({3, "Low priority task"});
    taskQueue.push({1, "High priority task"});
    taskQueue.push({2, "Medium priority task"});

    while (!taskQueue.empty()) {
        Task t = taskQueue.top();
        cout << t.description << " (Priority: " << t.priority << ")" << endl;
        taskQueue.pop();
    }

    return 0;
}

위 코드에서 CompareTask 구조체는 operator()를 오버로드하여 priority_queue가 요소들을 정렬하는 방식에 대한 커스텀 규칙을 정의합니다. 이렇게 하면 사용자 정의 구조체나 복잡한 데이터 타입에 대해서도 우선순위를 유연하게 설정할 수 있습니다.

3. multiset을 사용한 우선순위 큐 구현

multiset은 C++ STL의 컨테이너로, 중복된 값을 허용하면서 항상 오름차순으로 정렬된 상태를 유지합니다. 이를 통해 우선순위 큐와 유사한 기능을 구현할 수 있으며, 특히 최솟값을 쉽게 꺼내는 작업에 유리합니다.

예제 코드: multiset을 사용한 스코빌 지수 문제 풀이

아래는 multiset을 사용하여 동일한 문제를 해결하는 코드입니다:

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

int solution(vector<int> scoville, int K) {
    // multiset 선언, 자동으로 오름차순 정렬됨
    multiset<int> scovilleSet(scoville.begin(), scoville.end());

    int answer = 0;

    // 모든 원소가 K 이상이 될 때까지 반복
    while (*scovilleSet.begin() < K) {
        // 원소가 2개 이상 있어야 섞을 수 있음
        if (scovilleSet.size() < 2) {
            return -1; // 섞을 수 없는 경우, 목표 도달 불가능
        }

        // 두 개의 최소 원소를 꺼내서 섞음
        auto it = scovilleSet.begin();
        int top1 = *it;  // 포인터를 사용하여 iterator가 가리키는 값을 참조합니다.
        scovilleSet.erase(it);
        it = scovilleSet.begin();
        int top2 = *it;  // 마찬가지로 포인터를 사용하여 값을 가져옵니다.
        scovilleSet.erase(it);

        // 새로운 스코빌 지수를 계산하고 다시 multiset에 넣음
        int new_item = top1 + (top2 * 2);
        scovilleSet.insert(new_item);

        // 섞는 횟수를 증가시킴
        answer++;
    }

    return answer;
}

int main() {
    vector<int> scoville = {1, 2, 3, 9, 10, 12};
    int K = 7;
    cout << solution(scoville, K) << endl; // 결과값은 2가 되어야 함
    return 0;
}

multiset을 사용하면 자동으로 오름차순으로 정렬된 상태를 유지하므로 최솟값을 찾는 작업이 간편해집니다. 또한 중복된 값들도 자연스럽게 관리할 수 있습니다.

*it과 &it의 차이

• *it: iterator가 가리키는 값을 참조합니다. 예를 들어, multiset<int>::iterator가 특정 원소를 가리킬 때 *it는 그 원소의 값을 반환합니다. 이를 통해 iterator가 가리키는 실제 데이터를 접근하고 사용할 수 있습니다. 일반적으로 값을 읽거나 수정할 때 *it을 사용합니다.
• &it: iterator 자체의 주소를 의미합니다. &는 참조 연산자이므로, it 자체의 메모리 주소를 가리키게 됩니다. 이는 일반적으로 사용되지 않으며, 주로 iterator 변수 자체의 위치가 필요할 때 사용될 수 있지만 대부분의 경우 사용하지 않습니다.

따라서, iterator가 가리키는 값을 참조해야 할 때는 *it를 사용하고, iterator 자체의 주소가 필요할 때는 &it를 사용합니다.

multiset의 커스텀 우선순위 설정

multiset 역시 커스텀 비교 함수를 통해 우선순위를 설정할 수 있습니다. 커스텀 비교 함수를 사용하려면 multiset 선언 시 다음과 같이 비교 함수 객체를 전달하면 됩니다:

#include <set>
#include <iostream>

using namespace std;

struct Compare {
    bool operator()(const int& a, const int& b) const {
        return a > b; // 내림차순으로 정렬
    }
};

int main() {
    multiset<int, Compare> customSet = {1, 5, 3, 9, 7};

    for (int num : customSet) {
        cout << num << " "; // 출력: 9 7 5 3 1
    }
    cout << endl;

    return 0;
}

위 코드에서는 Compare 구조체를 통해 multiset이 내림차순으로 정렬되도록 설정했습니다. 이와 같이 multiset에 커스텀 비교 함수를 제공하여 원하는 순서로 요소들을 정렬할 수 있습니다.

4. priority_queue vs multiset

• **priority_queue**는 최대 힙 또는 최소 힙을 쉽게 구현할 수 있으며, 삽입과 삭제의 시간 복잡도가 **O(log N)**입니다. 기본적으로 가장 큰 값을 빠르게 접근할 수 있는 최대 힙으로 구현되어 있어 최대 우선순위 요소를 찾는 데 유리합니다.
• **multiset**은 중복 값을 허용하며, 항상 정렬된 상태로 유지합니다. 삽입과 삭제 역시 **O(log N)**의 시간 복잡도를 가지지만, priority_queue에 비해 모든 요소가 정렬된 상태로 유지된다는 점에서 더 유연하게 사용할 수 있습니다.

두 자료구조 모두 우선순위 큐를 구현하는 데 유용하지만, 상황에 따라 적합한 것을 선택하는 것이 중요합니다. 예를 들어, 중복된 값을 다루거나 특정 정렬된 순서를 유지해야 한다면 multiset이 더 적합할 수 있습니다. 반면에, 특정한 우선순위에 따라 요소를 빠르게 추출해야 한다면 priority_queue를 사용하는 것이 좋습니다.

5. 오늘의 회고

오늘 학습을 통해 priority_queue와 multiset을 사용하여 우선순위 큐를 구현하는 방법에 대해 깊이 이해하게 되었습니다. multiset은 중복된 값을 쉽게 처리하고 항상 정렬 상태를 유지할 수 있다는 점에서 유용하지만, 삽입 및 삭제의 성능 면에서는 priority_queue와 약간의 차이가 있을 수 있습니다.