(TIL) 20210612

📕Facts(한 것)

---

• 알고리즘 복습
• 프로그래머스 문제 풀기
• 수업듣기
• 학교 과제

📕Findings(배운 것)

---

huffman code관련해서 복습을 진행했다.

복습을 하던 도중 heap관련 내용이 나왔는데,

공부도 너무 지겨워서 프로그래머스 heap관련 문제를 풀었다.

 

'더 맵게' 라는 문제인데, 우선순위큐를 이용해서 풀 수 있다.

 

우선순위 큐에 대해서 간략히 얘기하자면, 우선순위 큐는 힙의 성질과 큐의 성질을 합쳐놓았다고 보면 된다.

힙에는 max heap과 min heap 두 종류가 있다.

 

max heap은 트리 가장 상단의 노드가 즉, 루트노드가 그 트리에서 가장 큰 값이고

부모 노드의 자식 노드는 부모 노드보다 작아야 한다.

 

min heap은 정반대이다. 가장 산단의 노드가 그 트리에서 가장 작은 값이고

부모 노드의 자식 노드는 부모 노드보다 커야한다.

 

그리고 이러한 heap 자체를 큐에 넣으면 우선순위 큐가 탄생하는데,

일반적인 큐와는 다르게, front(), back()이 아닌 top()을 사용한다.

힙의 성질을 이해하면 이해가 가는 부분이다.

 

아래는 문제 '더 맵게'의 C++ 코드이다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int food = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(auto i : scoville) {
        pq.push(i);
    }
    while(pq.top() < K) {
        if(pq.size() < 2) {
            return -1;
        }
        food += pq.top(); pq.pop();
        food += 2 * pq.top(); pq.pop();
        pq.push(food);
        food = 0;
        answer++;
    }
    return answer;
}

 

📕Feeling(느낀 점)

---

날짜 개념 없이 지내다가 어느순간 보니 벌써 12일이다.

시험이 3일 앞으로 다가오니 점점 실감이 난다.

열심히 복습해야겠다.

📕Affirmation(자기 선언)

---

• 日日新又日新
• 순간에 최선을

 

📕여담

---