99클럽 코테 스터디 20일차 TIL C++ Priority Queue과 multiset, std::accumulate

오늘의 학습 키워드

문제 1: Heap, Priority Queue

Take Gifts from the Richest Pile - LeetCode 문제

주어진 문제에서는 여러 개의 선물 더미 중에서 매 초마다 가장 많은 선물을 가진 더미를 선택하고, 그 선물의 정수 제곱근만큼 남기는 과정을 k번 반복한 뒤, 모든 더미에 남은 선물의 총합을 구하는 문제입니다. 이 문제를 해결하기 위해 heap과 priority_queue를 사용하여 접근해 보았습니다.

공부한 내용 본인의 언어로 정리하기

문제 1: Heap, Priority Queue

1. 우선순위 큐를 사용한 풀이

이 문제는 가장 큰 선물 더미를 빠르게 찾고 업데이트해야 하므로 우선순위 큐(priority queue)를 사용하여 해결했습니다. priority_queue는 내부적으로 최대 힙을 이용해 항상 최대값을 O(log n) 시간 복잡도로 꺼낼 수 있기 때문에 문제의 요구사항에 적합합니다.

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

class Solution {
public:
    long long pickGifts(std::vector<int>& gifts, int k) {
        std::priority_queue<int> queue_gifts(gifts.begin(), gifts.end());

        for (int i = 0; i < k; i++) {
            int maximum_number = queue_gifts.top();
            int square_number = sqrt(maximum_number);

            queue_gifts.pop();
            queue_gifts.push(square_number);
        }

        long long sum_gifts = 0;
        int size_gifts = gifts.size();
        for (int i = 0; i < size_gifts; i++) {
            sum_gifts += queue_gifts.top();
            queue_gifts.pop();
        }

        return sum_gifts;
    }
};

 

위 코드에서는 매 초마다 queue_gifts에서 가장 큰 값을 가져와 제곱근을 남기고 다시 우선순위 큐에 넣습니다. 이 과정을 k번 반복한 후, 남은 선물의 총합을 계산합니다.

2. multiset을 사용한 풀이

multiset은 중복된 값을 허용하고 모든 요소를 자동으로 정렬해 주는 자료구조입니다. 이 문제에서는 multiset을 이용해 항상 가장 큰 값을 빠르게 찾고 삭제할 수 있는 점을 활용해 보았습니다.

#include <iostream>
#include <set>
#include <vector>
#include <cmath>

class Solution {
public:
    long long pickGifts(std::vector<int>& gifts, int k) {
        std::multiset<int, std::greater<int>> gifts_set(gifts.begin(), gifts.end());

        for (int i = 0; i < k; i++) {
            auto it = gifts_set.begin(); // 가장 큰 값에 대한 iterator
            int maximum_number = *it;
            int square_number = std::sqrt(maximum_number);

            gifts_set.erase(it); // 가장 큰 값을 삭제하고
            gifts_set.insert(square_number); // 제곱근 값을 삽입
        }

        long long sum_gifts = 0;
        for (const auto& gift : gifts_set) {
            sum_gifts += gift;
        }

        return sum_gifts;
    }
};

 

multiset을 사용하면 항상 최대 값을 쉽게 찾고 삭제할 수 있으며, 삽입 또한 자동으로 정렬된 위치에 들어가기 때문에 priority_queue에 비해 코드가 간단해집니다.

성능 비교 및 결과

실제로 priority_queue와 multiset을 비교했을 때, multiset이 더 나은 성능을 보여주었습니다. 그 이유는 multiset이 이진 탐색 트리 기반으로 정렬된 상태를 유지하기 때문에 삽입과 삭제가 모두 O(log n)의 시간 복잡도를 가지며, 요소 순회도 쉽기 때문입니다. 반면, priority_queue는 내부적으로 힙(Heap) 자료구조를 사용하여 이진트리 구조를 유지합니다. 따라서 항상 최댓값을 빠르게 찾을 수 있습니다. 반면, priority_queue는 큐의 특성상 모든 요소를 순회하려면 pop()을 통해 하나씩 꺼내야 하기 때문에 불편하고 추가적인 비용이 발생합니다.

priority_queue 제출 결과

multiset 제출결과

Priority Queue vs Multiset

(1) Priority Queue 기본 사용법

• 선언하기: std::priority_queue<int> pq;
• 삽입(push): pq.push(value);
• 삭제(pop): pq.pop(); // 최댓값 삭제
• 최댓값 조회: pq.top();
• 순회하기: 순회 기능이 없으며, 모든 요소를 꺼내야 합니다. 예제 코드:

  while (!pq.empty()) {
    std::cout << pq.top() << " ";
    pq.pop();
  }

(2) Multiset 기본 사용법

• 선언하기: std::multiset<int> ms;
• 삽입(insert): ms.insert(value);
• 삭제(erase): ms.erase(iterator);
• 최댓값 조회: *ms.begin(); // 내림차순 정렬 시 가장 큰 값
• 순회하기: for (auto it : ms)로 쉽게 순회가 가능합니다. 예제 코드:

  for (auto it = ms.begin(); it != ms.end(); ++it) {
    std::cout << *it << " ";
  }

(3) 자료구조 선택 가이드

• Priority Queue는 항상 최댓값을 빠르게 찾아야 하고, 순회가 필요하지 않은 경우에 적합합니다.
• Multiset은 삽입, 삭제, 순회가 모두 필요한 경우에 유리하며, 자동 정렬된 상태로 요소를 유지해야 하는 상황에서 매우 효율적입니다.

std::accumulate

위의 풀이에서는 직접 loop를 돌아서 합산을 구했지만, 이를 지원하는 stl 함수가 있습니다.

std::accumulate는 <numeric> 헤더에 정의되어 있으며, 컨테이너의 시작 반복자와 끝 반복자를 지정하고, 초기값을 지정해 모든 요소를 합산할 수 있습니다. 이는 vector뿐만 아니라 다른 연속적인 반복자를 지원하는 컨테이너에서도 가능합니다.

priority_queue에서는 std::accumulate를 사용할 수 없습니다. std::accumulate는 반복자(iterator)를 사용하는 컨테이너에서만 동작합니다. priority_queue는 반복자를 제공하지 않기 때문에, std::accumulate와 같은 함수로 모든 요소의 합을 계산할 수 없으며, priority_queue에서 합을 구하려면 모든 요소를 pop()하여 꺼내야 합니다.

long long sum_gifts = 0;
sum_gifts = std::accumulate(gifts_set.begin(), gifts_set.end(), 0LL);

오늘의 회고

오늘은 priority_queue와 multiset을 사용해 우선순위 큐 문제를 해결하는 방법에 대해 공부했습니다. priority_queue는 최댓값을 빠르게 찾는 데 유리했지만, 순회나 삭제 후의 유지 관리가 어려웠습니다. 반면, multiset은 정렬 상태를 유지하면서 삽입과 삭제가 가능하여 더 나은 성능을 보였습니다.