25.02.20 코드카타

오늘의 문제를 보고 든 생각은 벡터 공간을 하나 만들어주고 거기에 다 넣으면서 k개가 넘을때마다 제일 작은 값을 빼줌과동시에 발표점수 즉 answer vector에 넣어주면 되겠다 싶었다 그래서 sort로 맨앞값을 작은값으로 하면 되나? 싶었는데 그래서 gpt에게 효율적으로 가장 작은 값을 빼는 방법을 물어봤다.그러다 완전이진트리구조를 가진 힙 자료구조를 알게 되었다.

🔹 최소 힙 (Min Heap)란?

**최소 힙(Min Heap)**은 완전 이진 트리(Complete Binary Tree) 구조를 가지며, 부모 노드가 항상 자식 노드보다 작거나 같은 값을 가지는 자료구조입니다.

📌 즉, 루트 노드(root)가 가장 작은 값을 유지하며, 힙에서 요소를 제거하면 항상 가장 작은 값부터 나오게 됨.

---

🔹 최소 힙의 특징

1. 부모 노드의 값 ≤ 자식 노드의 값
   → 항상 최소값이 루트에 위치.
2. 완전 이진 트리 구조 유지
   → 왼쪽에서 오른쪽, 위에서 아래 방향으로 채워짐.
3. 삽입/삭제 연산의 시간 복잡도: O(log N)
   • 요소 추가 시, 부모와 비교하며 올라감 (heapify-up)
   • 요소 제거 시, 마지막 요소를 루트로 이동 후 내려감 (heapify-down)

#include <iostream>
#include <queue> // 힙 자료구조 포함

using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> minHeap; // 최소 힙 선언

    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);

    cout << "최소 힙의 최솟값: " << minHeap.top() << endl; // 항상 가장 작은 값이 나옴

    minHeap.pop(); // 최솟값 제거
    cout << "최솟값 제거 후 최솟값: " << minHeap.top() << endl;

    return 0;
}

최소 힙의 최솟값: 5
최솟값 제거 후 최솟값: 10

 

🔹 C++의 priority_queue

C++에서 기본적으로 제공하는 priority_queue는 **기본적으로 최대 힙(Max Heap)**으로 동작합니다.
최소 힙을 만들려면 greater<int>를 사용해야 합니다.

✅ 최대 힙 (기본)

priority_queue<int> maxHeap; // 기본적으로 가장 큰 값이 먼저 나옴

✅ 최소 힙

priority_queue<int, vector<int>, greater<int>> minHeap; // 가장 작은 값이 먼저 나옴

🔹 최소 힙이 유용한 경우

1. 상위 k개 유지
   • k개만 유지하면서, 새로운 값이 들어올 때 가장 작은 값을 유지해야 할 때
2. 최소값을 빠르게 찾고 삭제해야 할 때
   • 예: 다익스트라 알고리즘 (최단 경로 찾기).
3. 데이터를 정렬하면서 관리할 때
   • 우선순위 큐로 활용하여 정렬된 상태 유지.

 

이를 활용하여 나온 코드이다.

 

#include <string>
#include <vector>
#include <queue> // 최소 힙 사용
#include <algorithm>

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int>> Hall; // 최소 힙 선언

    for (int i = 0; i < score.size(); i++) {
        Hall.push(score[i]); // 새로운 점수 추가

        // k개 초과 시 가장 낮은 점수 제거
        if (Hall.size() > k) {
            Hall.pop();
        }

        // 현재 명예의 전당에서 가장 낮은 점수 저장
        answer.push_back(Hall.top());
    }

    return answer;
}