서리 개인 개발 블로그

1. 힙(Heap)

- 최대값 혹은 최소값을 빠르게 찾아낼 수 있도록 고안된 완전이진트리 자료구조이다.

- 부모노드와 자식노드의 키 값 사이에 대소관계가 성립해야하는 조건을 만족해야한다.

- 부모노드의 키 값이 자식노드의 키 값보다 큰 힙을 '최대 힙', 반대를 '최소 힙'이라 부른다.

- 힙의 시간복잡도는 log n이다.

- 위키 (힙 트리)

2. 코드

※ A-star pathfind에서 OpenList의 최소 F cost를 가진 노드를 가져오기 위해 적용한 Heap tree 코드이다.

※ 유튜브 영상에 있는 소스를 수정하여 사용했는데, 기존 코드는 배열을 사용하여 맵 사이즈만큼 할당하여 힙을 사용하고 있었다.

※ 그 결과, 실제로 맵 사이즈만큼의 할당이 필요없는데도 불구하고 많은 할당이 일어나 가비지가 많이 발생되므로 List로 변경하고 Capacity를 지정해줌. (만약의 경우 추가 할당이 필요한 경우가 있을 수 있으므로 List로 구성했다.)

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public interface IHeapItem<T> : IComparable<T>
{
    int HeapIndex { get; set; }
}

public class HeapList<T> where T : class, IHeapItem<T>
{
    private List<T> m_items;
    public int Count => m_items.Count;
    public int Capacity => m_items.Capacity;

    public HeapList(int maxCapacity = 256)
    {
        m_items = new List<T>(maxCapacity);
    }

    public void Add(T item)
    {
        item.HeapIndex = m_items.Count;
        m_items.Add(item);
        SortUp(m_items[m_items.Count - 1]);
    }

    public void UpdateItem(T item)
    {
        SortUp(item);
    }

    private void SortUp(T item)
    {
        while(true)
        {
            int parentIndex = (item.HeapIndex - 1) / 2;
            T parentItem = m_items[parentIndex];

            if(item.CompareTo(parentItem) > 0)
            {
                Swap(item, parentItem);
            }
            else
            {
                break;
            }
        }
    }

    private void Swap(T itemA, T itemB)
    {
        m_items[itemA.HeapIndex] = itemB;
        m_items[itemB.HeapIndex] = itemA;

        int swapIndex = itemA.HeapIndex;
        itemA.HeapIndex = itemB.HeapIndex;
        itemB.HeapIndex = swapIndex;
    }

    public T GetRoot()
    {
        T rootItem = m_items[0];
        //List의 원소가 1개일 때 List.Count로 원소를 가져오면 에러가 발생하므로 index값을 저장한다.
        int lastIndex = m_items.Count - 1;

        m_items[0] = m_items[lastIndex];
        m_items[0].HeapIndex = 0;
        m_items.RemoveAt(lastIndex);

        SortDown(lastIndex);

        return rootItem;
    }

    private void SortDown(int lastIndex)
    {
        int currentIndex = 0;
        while(true)
        {
            int childLeft = currentIndex * 2 + 1;
            int childRight = currentIndex * 2 + 2;
            int swapIndex = currentIndex;

            //왼쪽 자식 노드 유무 확인
            if(childLeft < lastIndex)
            {
                swapIndex = childLeft;
                //오른쪽 자식 노드 유무 확인
                if(childRight < lastIndex)
                {
                    //양쪽 자식 노드가 존재하면 두 자식 노드의 값을 비교해서 swapIndex 결정
                    //FCost 비교해서 오른쪽 자식노드가 작으면 swapIndex를 childRight로 변경해준다.
                    if(m_items[childLeft].CompareTo(m_items[childRight]) < 0)
                    {
                        swapIndex = childRight;
                    }
                }

                //현재 노드와 자식노드의 값을 비교해서 Swap
                if(m_items[currentIndex].CompareTo(m_items[swapIndex]) < 0)
                {
                    Swap(m_items[currentIndex], m_items[swapIndex]);
                    currentIndex = swapIndex;
                }
                else
                {
                    return;
                }
            }
            else
            {
                return;
            }
        }
    }

    public bool Contains(T item)
    {
        return item.HeapIndex >= m_items.Count ? false : Equals(m_items[item.HeapIndex], item);
    }
}

• GetRoot()로 루트노드를 힙에서 빼면 말단노드를 Root로 이동 후, 정렬(Sort down)한다.
• 노드를 추가하면, 말단노드에 추가한 뒤 정렬(Sort up)해서 노드의 위치를 지정해준다.

2-1) 힙을 사용하는 노드의 코드 (CompareTo() 구현)

public class Node : IHeapItem<Node>
{
    private int m_hCost;
    private int m_gCost;
    private int m_heapIndex;
    public int HeapIndex { get => m_heapIndex; set => m_heapIndex = value; }
    public int FCost => m_hCost + m_gCost;

    //Heap tree용 compare구현
    public int CompareTo(Node other)
    {
        int compare = FCost.CompareTo(other.FCost);
        if (compare == 0)
        {
            compare = m_hCost.CompareTo(other.m_hCost);
        }

        //힙에서 작은수가 루트로 올라가야하므로 -를 붙여서 반환한다.
        return -compare;
    }
}

※ 참고 유튜브 (맵 사이즈 만큼 배열을 할당하는 힙)

https://youtu.be/3Dw5d7PlcTM

풀이 코드

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

using namespace std;

#define FAIL -1

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(auto it : scoville)
    {
        pq.push(it);
    }

    while(pq.size() > 1 && pq.top() < K)
    {
        int less_1 = pq.top();
        pq.pop();
        int less_2 = pq.top();
        pq.pop();

        int mixScoville = less_1 + less_2 * 2;
        answer++;

        pq.push(mixScoville);
    }

    if(pq.top() < K)
    {
        answer = FAIL;
    }

    return answer;
}

기타

- 코드 작성은 쉬웠는데, 제발 테스트 케이스가 조금 많았으면 좋겠다 ㅠㅠ.. (1개는 너무한거 아닌가)

- C#에서는 우선순위 큐를 직접 구현해서 사용했었는데, C++에서는 그냥 제공되서 작성에 편했다.

- 다른 사람 풀이를 보니 아래와 같이 작성해서 for문 돌려서 값을 넣을 필요 없이 바로 값을 넣을 수 있었다.

priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());

풀이 코드

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int[] prices) {
        List<int> list = new List<int>(prices.Length);

        for(int i = 0; i < prices.Length; i++)
        {
            list.Add(GetSeconds(prices, i));
        }

        return list.ToArray();
    }

    private int GetSeconds(int[] prices, int startIndex)
    {
        int returnValue = 0;
        for(int j = startIndex + 1; j < prices.Length; j++, returnValue++)
        {
            if(prices[startIndex] > prices[j])
            {
                returnValue++;
                break;
            }
        }

        return returnValue;
    }
}

기타

- 이 문제가 왜 스택/큐와 관련이 있는지 잘 모르겠다. 스택을 사용한사람 풀이를 봐도 이걸 이렇게까지 해서 스택을 사용해야 싶기도 하고..

- 바로 직전에 푼 '다리를 지나는 트럭' 문제하고 난이도 차가 너무 나서 풀면서도 의심스러웠다.

- 결국 가독성 좋고, 간단하게 작성하는 법을 선택했는데, 스택/큐에 정신이 사로잡혀서 list를 사용하는 실수를 저질렀다.

- 그냥 배열로 사용해서 'if(prices[startIndex] > prices[j])' 조건문에서 배열 원소에 증가연산자 사용하면 결과 반환할 때, array 변환도 안해도 되고 가독성도 좀 더 올라갔을것 같다. (효율성 테스트에서도 list 사용 여부에 따라 1ms 차이가 났다.)

풀이 코드

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    //first : 트럭 무게
    //second : 다리 진입 시간
    queue<pair<int, int>> bridgeQueue;
    int sec = 1;
    int totWeight = 0;

    for(int i = 0; i < truck_weights.size(); i++, sec++)
    {
        if(bridgeQueue.size() != 0)
        {
            //경과시간이 선두 트럭 통과 시간보다 크면 이미 통과한 트럭이므로 디큐
            if(sec >= bridgeQueue.front().second + bridge_length)
            {
                totWeight -= bridgeQueue.front().first;
                bridgeQueue.pop();
            }
			
            //트럭 무게가 다리 하중을 넘으면 선두 트럭을 디큐하고 선두 트럭 기준으로 시간을 다시 계산한다.
            while(weight < truck_weights[i] + totWeight)
            {
                sec = bridgeQueue.front().second + bridge_length;
                totWeight -= bridgeQueue.front().first;
                bridgeQueue.pop();
            }
        }

        bridgeQueue.push(make_pair(truck_weights[i], sec));
        totWeight += truck_weights[i];
    }

    return bridgeQueue.back().second + bridge_length;
}

기타

- 이번 문제는 지문이 너무 불친절해서 지문 이해하는데 오래걸렸다. (지문이 이해가 안간다는 말들이 보이는거 보면 내가 한글을 못하는건 아닌거같다..)

풀이코드

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

using namespace std;

int GetAnswer(const vector<int>&, int);

int solution(vector<int> priorities, int location) {
    int answer = GetAnswer(priorities, location);
    return answer;
}

int GetAnswer(const vector<int>& priorities, int location)
{
    int result = 0;
    queue<pair<int, int>> iQueue;
    priority_queue<int> pQueue;
    for(int i = 0; i < priorities.size(); i++)
    {
        iQueue.push(make_pair(i, priorities[i]));
        pQueue.push(priorities[i]);
    }

    while(!iQueue.empty())
    {
        if(iQueue.front().second == pQueue.top())
        {
            pQueue.pop();
            result++;

            if(iQueue.front().first == location)
            {
                break;
            }
        }
        else
        {
            iQueue.push(iQueue.front());
        }
        iQueue.pop();
    }

    return result;
}

• vector의 값을 queue<pair<int, int>와 priority_queue<int>에 넣어준다.
• 그 뒤, 큐의 priority값과 우선순위 큐의 값을 비교해서 같으면 result를 증가시키고 다르면 큐의 첫번째 값을 맨 뒤로 옮겨준다.
• priority 값이 같을 때, location값을 비교하는데 location 값이 같으면 내가 요청한 문서를 찾은것이니 반복문을 나와 result 값을 반환한다.

기타

- 인수로 들어오는 vector 값으로 해결해보려고 했는데, 기본 케이스는 통과가 되나 제출 시의 테스트 케이스에서 불합격이 나는바람에 포기했다. (어떤 케이스에서 안되는지 알고싶은데 그걸 모르니 답답함...)