취약점 극복하기 : 힙

자료구조 - 힙 (heap) : 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진트리. (Heap Tree)

영어단어 heap은 쌓아올린 더미를 의미한다.

 

상위 노드의 값은 항상 하위 노드보다 크거나 작아야하는 규칙이 있다.

클 경우 -> 최대 힙 (Max Heap)

작을 경우 -> 최소 힙(Min Heap)

 

이런 특성은, 우선순위 큐 (priority queue)를 만드는데 주로 사용된다.

 

데이터의 삽입과 삭제의 시간복잡도가 O ( log N ) 인 만큼 최댓값, 최솟값 탐색에 유용하게 사용된다.

 

힙을 직접 구현하는 작업도 언젠가 필요한 일이지만

당장에 다음주 주말 코딩테스트가 급하기 때문에 지금은 

python 라이브러리를 활용한 방법을 중심으로 알아보자.

 

파이썬 라이브러리 이름은 heapq이다. heap을 활용해 que를 구현했다는 의미로 받아들이면 좋다.

https://docs.python.org/ko/3/library/heapq.html?highlight=heapq#module-heapq 

heapq — 힙 큐 알고리즘 — Python 3.10.2 문서

 

heapq는 기본적으로 최소힙이다.

 

#1927번 최소 힙 https://www.acmicpc.net/problem/1927

1927번: 최소 힙

import heapq
import sys
input = sys.stdin.readline
heap = []
for _ in range(int(input())):
    n = int(input())
    if n == 0:
        # 0 -> pop
        print(heapq.heappop(heap) if len(heap) > 0 else 0)
    else:
        # 자연수 -> 저장
        heapq.heappush(heap, n)

heapq라이브러리는 collections내부의 다른 자료구조들처럼 직접 선언하여 사용하는 형태가 아니다.

리스트를 기본으로 사용하되 메소드 형태로 제공된다.

 

하지만 heapq는 최소힙이기 때문에, 최대 힙을 구현하기 위해서는 약간의 기교가 필요하다.

 

#11279번 최대 힙 https://www.acmicpc.net/problem/11279

import heapq
import sys
input = sys.stdin.readline
heap = []
for _ in range(int(input())):
    n = int(input())
    n = -n
    if n == 0:
        # 0 -> pop
        result = heapq.heappop(heap) if len(heap) > 0 else 0
        print(-result)
    else:
        # 자연수 -> 저장
        heapq.heappush(heap, n)

heapq에서 제공하는 최소 힙을 그대로 이용하기 위해서 저장하는 값에 -를 붙여서 저장한다. 그럼 가장 큰 값이 최상위 노드로 (물론 음수인 형태로) 저장된다.

그 뒤 heappop을 진행할 때, return된 값을 다시 부호를 반전시켜 사용한다.

 

이렇게 파이썬 라이브러리 heapq를 활용해 최소 힙과 최대 힙을 구현했다.

 

다음은 응용을 해보자.

 

#7662번 이중 우선순위 큐 https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

응용을 하자는 식으로 이 문제를 제안했지만 사실 꽤 어려운 문제이다. (아니 그냥 존나어렵다.)

 

import heapq
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    # 두 개의 힙을 사용해 효율성을 높인다.
    minH = []
    maxH = []
    # 서로 다른 두 힙의 동기화를 위해 플래그 리스트를 사용.
    visited = [False]*(1000001)
    # for 문의 i를 각 입력값의 id로 활용한다.
    # 힙에 저장될 땐, 리스트 형태로 저장되고 힙은 2차원 리스트가 된다.
    for i in range(int(input())):
        cmd, num = input().split()
        num = int(num)

        if cmd == "I":  # 삽입
            heapq.heappush(minH, (num, i))
            heapq.heappush(maxH, (-num, i))
            visited[i] = True   # True인 경우가 두 힙에 동시에 존재하는 경우를 의미한다.

        elif num == 1:  # 제일 먼저 조건문에서 I 여부를 판단했다. 여기까지 도달하는 모든 경우는 D인 경우이다.
            # 두 힙 모두에 존재하는 값이 나올 때 까지 전부 제거한다.
            while maxH and not visited[maxH[0][1]]:
                heapq.heappop(maxH)
            # 그 후 존재하는 첫 번째 값이 최댓값이 된다.
            if maxH:
                # 값을 제거하기 때문에 False로 기록한다.
                visited[maxH[0][1]] = False
                heapq.heappop(maxH)
        else:  # cmd == "D" and num == -1
            while minH and not visited[minH[0][1]]:  # 위와 같은 논리이다.
                heapq.heappop(minH)
            if minH:
                visited[minH[0][1]] = False
                heapq.heappop(minH)

    while maxH and not visited[maxH[0][1]]:  # 두 힙 모두에 존재하는 값이 나올 때 까지 전부 제거한다.
        heapq.heappop(maxH)
    while minH and not visited[minH[0][1]]:
        heapq.heappop(minH)
    print(" ".join(map(str, [-maxH[0][0], minH[0][0]]))
          if maxH and minH else "EMPTY")

논리 자체는 어렵지않다. 단지 구조적 문제로 코드가 길어질 뿐이다.

 

힙 두개를 이용한다. 최솟값 연산과 최댓값 연산을 동시에 진행하기 때문이다.

하지만 이 두개의 힙이 독립적으로 동작하지 않게, 동시에 같은 상태를 유지할 수 있게 (동기적) 설계해야 한다.

 

그렇게 추가된 코드가 i를 id처럼 사용하고, visitied리스트에서 기록하는 형태이다.

두 개의 힙에 동시에 저장된 상태에선 True로 유지하되, 하나의 힙에서 삭제한다면 False로 변경한다. 그 뒤 각각의 힙에서 삭제연산을 진행할 때에는 True인 값이 나올 때까지 False인 값들을 모두 삭제하고 진행하면 된다.

 

마지막으로 정답을 출력하기 전에도 동일한 방법이 사용된다.

 

굉장히 어려워 보였지만 막상 하고 나니까 별거아니라는 느낌을 받았다.

 

즐거웠다!

 

[코드 참조]

https://neomindstd.github.io/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/boj7662/

[백준/파이썬] 7662번 이중 우선순위 큐 풀이