📝힙의 개념
- 완전이진트리의 한 종류
- 우선순위 큐(가장 먼저 들어온 데이터가 나가는 일반 큐가 아니라, 우선순위가 가장 높은 큐가 먼저 나간다)를 위해 만들어졌다
힙의 종류
최대 힙
부모 노드가 가진 Key의 값이 자식 노드의 Key값보다 크거나 같은 완전 이진 트리
최소 힙
부모 노드가 가진 Key의 값이 자식 노드의 Key값보다 작거나 같은 완전 이진 트리
🤷♂️힙은 어디에 사용될까?
- 네트워크 트래픽 제어
- OS 스케쥴링
문제풀이
- [S2]11279]최대 힙
파이썬에서 지원하는 heapq모듈을 사용하여 풀이를 진행하였다. import를 시켜주고 지원하는 함수를 통하여 짧은 코드로 쉽게 문제를 해결이 가능했다.
heapq는 최소힙을 지원하여 부모 노드는 자식 노드보다 값이 작거나 같은 이진트리 구조 + 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.
#힙큐 응용
- heapq.heappush(heap, item) : item을 heap에 추가
- heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨
문제가 있는 것이 해당 모듈은 최소힙을 지원하는데 우리는 최대 힙을 사용하고 싶다는 것이다. 이를 위해서는 최소힙을 기본 동작하게 하면서 눈에 보이는 출력은 최댓값만 나오게 하면 되기 때문에 음수값으로 push를 하고 pop을 할 때는 -기호를 한 번 더 붙여주어 양수값으로 나오게 해주었다.
import sys
import heapq
heap = []
n = int(input())
for i in range(n):
k = int(sys.stdin.readline())
if(k == 0):
try:
print(-1 * heapq.heappop(heap))
except:
print(0)
else:
#heapq는 최소힙을 기본으로 동작, 값을 음수로 만들어줘서 최대힙처럼 사용
heapq.heappush(heap, (-k))
- [S2]2075]N번째 큰 수
실패한 코드 : 메모리 초과
import sys
import heapq
heap = []
n = int(input())
for i in range(n):
k = list(map(int, input().split()))
for j in range(n):
heapq.heappush(heap, -k[j])
for m in range(n):
if(m == n-1):
print(-1 * heapq.heappop(heap))
else:
heapq.heappop(heap)
사실 문제를 풀면서 메모리 초과로 실패한 적이 처음이라 적지 않게 당황을 했다. 메모리 초과라는 것이 변수나 리스트를 문제 요구보다 과도하게 사용했다는 것이니까 그럼 입력 받는 배열을 다르게 받아야 하는건가 하는 생각이 가장 먼저 들었지만, 입력 받는 배열은 다른 방법이 떠오르지도 않거니와 배열 5개 정도는 괜찮을 것 같았다. 가장 크기가 많이 생기는 것이 heap인데 그냥 받은대로 다 힙에 갖다 넣어두니 25개가 힙에 들어가 있었고 이것을 해결하는 것이 맞아보였다.
힙의 크기를 줄이기 위한 방법으로 고민한 것이 힙에 바로 넣지 않고 크기를 비교해 값이 가장 큰 5개만 남기는 것과, 힙을 넣더라도 값이 더 큰 게 존재하면 그 값을 빼내고 넣는 방법을 생각하였고 해당 방법으로 해결할 수 있었다.
import sys
import heapq
heap = []
n = int(input())
for i in range(n):
k = list(map(int, input().split()))
if(heap):
for j in k:
if(heap[0] < j):
heapq.heappop(heap)
heapq.heappush(heap, j)
else:
for j in k:
heapq.heappush(heap, j)
print(heapq.heappop(heap))- [S1]11286]절댓값 힙
처음에는 클래스를 만들어 숫자를 기록함과 동시에 해당 숫자가 음수였음을 표기하는 방식으로 문제를 풀려고 했었다.
class Num:
def __self__(self, value):
if(value < 0):
self.value = -value
self.sign = 1
else:
self.value = value
self.sign = 0
그러나 당연하게도 heapq는 내 클래스의 구성까지 파악해서 자동으로 정렬해주는 함수일 수는 없음으로 해당 생각을 접고 다른 방식을 찾아야했다. 힙을 사용하면서도 절댓값에 원래 기호를 파악할 수 있는 방법이 이 방법이 맞는 것 같은데 혹시나 heapq 내장 함수중에 활용할 수 있는 게 있을까 찾아보던 중 heapq.heappush(heap, item)에서 집어 넣는 item 자체가 하나만 들어갈 수 있는 것이 아니라 배열 형식으로 여러 개가 들어갈 수 있으며, 첫 인자만을 보고 힙 정렬이라는 것을 알게 되었다. 그래서 첫 인자는 절댓값, 두번째 인자는 원래 해당 값을 넣어서 부호 상태, 절댓값 상태를 동시에 저장하여 문제를 해결할 수 있었다.
import sys
import heapq
heap = []
n = int(sys.stdin.readline())
for i in range(n):
m = int(sys.stdin.readline())
if(m == 0):
try:
print(heapq.heappop(heap)[1])
except:
print(0)
else:
heapq.heappush(heap, (abs(m), m))- [G2]1655]가운데를 말해요
