[항해99 취업 리부트 코스 학습일지] Day 14 - 알고리즘 : 힙

[학습 내용]

오늘은 힙에 대해서 학습했다.

1. 힙

힙은 완전 이진 트리의 일종으로 부모 자식 노드 사이에 특정 조건을 만족하는 자료구조를 말한다. 완전 이진 트리란 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 리프 노드를 제외한 모든 노드가 완전히 채워져 있는 구조를 말한다. 힙은 기준점에 따라서 최소 힙과 최대 힙으로 나눌 수 있는데, 다음과 같은 특징이 있다.

• 최대 힙은 모든 부모 노드가 그 자식 노드보다 크거나 같은 값을 가지는 특성을 가지고 있어 루트 노드는 전체 힙에서 가장 큰 값을 가지고 있다.
• 반대로 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 특성을 가지기 때문에 루트 노드가 전체 힙에서 가장 작은 값을 가진다.
• 파이썬에서는 heapq 라이브러리를 활용해서 생성 가능하며, heapq는 기본적으로 최소 힙을 기준으로 한다.
• 자바에서는 PriorityQueue를 사용해서 구현 가능하다.

중요한 건 파이썬에서 최대 힙을 쓰려면 약간의 조작이 필요하다, 다음 코드를 보면서 차이를 느껴보자.

백준 : 1927 최소 힙, 11279 최대 힙

from heapq import *
from sys import stdin

input = stdin.readline

n = int(input().rstrip())
num_heap = []
answer = []
for i in range(n):
    x = int(input().rstrip())

    if x:
        heappush(num_heap, x) # 만약 최대힙이면 -x

    else:
        if num_heap:
            answer.append(heappop(num_heap)) # 최대힙이면 -heappop(num_heap)
        else:
            answer.append(0)


print(*answer, sep='\n')

최소힙일 경우에는 그냥 값을 넣어주고 빼주면 되지만, 최대힙일 경우에는 -를 추가해서 음수로 했을 때 가장 작은 값을 기준으로 힙을 만들면 출력 시에 양수로 만들면 그게 가장 큰 값이 된다. 

---

힙을 사용하는 것까지는 좋았지만, 내부적으로 어떤 구조로 어떻게 정렬을 하고 로직이 이루어지는지에 대한 이해가 짧아 아쉽다. 후에 트리와 그래프에 대해서 학습하고 난 뒤에 가능하다면, 힙 구조를 코드로 직접 구현해보는 것도 학습에 도움이 많이 될 것 같다.

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠입니다.

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지

태그 옮기기 : #개발자포트폴리오 #개발자이력서 #개발자취업 #개발자취준 #코딩테스트 #항해99 #취리코 #취업리부트코스