Problem Solving/Algorithm Concepts

[알고리즘] 우선순위 큐, 힙 & 백준(최대 힙, 최소 힙, 가운데를 말해요, 카드 정렬하기)

대범하게 2022. 10. 3. 21:51
반응형

우선순위 큐란,

데이터 삽입은 어떤 순서로 해도 상관없지만 데이터를 삭제할 때는 우선순위에 맞춰 더 높은 우선순위를 갖는 데이터를 먼저 삭제하는 큐를 말한다. 우선순위 큐는 힙을 통해 구현할 수 있다. 힙이란 완전 이진트리의 일종으로 대표적으로 최대 힙과 최소 힙이 있다.

- 최대 힙: 루트 노드가 가장 큰 값을 가지며, 부모 노드는 항상 자식 노드보다 큰 값을 갖는다.

- 최소 힙: 루트 노드가 가장 작은 값을 가지며, 부모 노드는 항상 자식 노드보다 작은 값을 갖는다.

힙에서의 삭제는 항상 루트 노드를 먼저 삭제하며 노드 변동 시 힙의 성질을 만족하도록 힙을 변동시킨다. 이러한 힙의 특징을 이용하여 우선순위 큐를 구현하는 것이다. 사실상 우선순위 큐를 구현하는 것은 힙을 구현하는 것이다.

최대 힙 구현

완전 이진 트리를 1차원 배열로 구현하기 위해, 다음과 같은 방법을 사용할 수 있다.

- 첫번째 index(root 노드)는 1부터

- 부모노드 index = 자식노드 index // 2

- 왼쪽자식노드 index = 부모노드 index * 2

- 오른쪽 자식노드 index = 부모노드 index * 2 + 1

push()

최대 힙에 값 num을 저장하는 방법

- 배열의 끝에 num을 저장한다.

- 부모 노드와 num을 비교하여, num이 부모 노드의 값보다 더 크면 위치를 바꾼다.

- '2번'을 반복하다가, num이 부모 노드의 값 이하이거나 root 노드에 도달하면 멈춘다.

* 여기서 부모노드를 계속 root 노드라고 착각해서 헷갈렸던 것이었다. 부모노드와 자식노드는 index마다 바뀐다.

max_heap = [None] * (n)
max_heap[0] = 999999999999
last_index = 0

def push(num):
    global max_heap
    global last_index

    # push를 통해 값이 들어오니깐 !
    # 배열의 끝에 값을 저장하기 위해 현재까지 기록된 마지막 index를 1 증가시킨다.
    last_index += 1

    # 증가된 마지막 index에 저장할 값을 넣어준다.
    max_heap[last_index] = num

    # 부모 노드와 값을 비교하며 위치를 결정한다.
    cur = last_index
    while cur != 0:
        # index 0 사용하지 않는다.
        # 저장한 값이 부모 노드보다 작을 때까지 반복한다.
        if cur//2 != 0 and max_heap[cur//2] < max_heap[cur]:
            max_heap[cur], max_heap[cur//2] = max_heap[cur//2], max_heap[cur]
            cur //= 2
        # root 노드에 도달하거나 부모 노드의 값보다 작으면 멈춘다.    
        else:
            break

pop()

최대 힙에서 가장 큰 값은 root 노드(1번 index)에 있다.

값을 꺼내고 삭제하면 힙을 유지하기 위해 다시 값을 정렬해줘야 한다.

값을 꺼낸 뒤 힙을 정렬시키는 과정은 다음과 같다.

 

- 마지막 index에 저장된 n을 index 1에 저장한다.

- max(왼쪽 자식 노드 key값, 오른쪽 자식 노드 key값)이 n보다 작다면 서로 위치를 바꿔준다.

- 위를 반복하다가, n이 두 자식 노드의 key값보다 크거나, 마지막 index에 도달해서 더 이상 진행할 수 없다면 중단한다.

 

* last_index의 경우에도 왜 last_index의 초기값을 0으로 잡았는지에 대한 의문이 있었는데, 값이 있는 max_heap을 구하는게 아니라 max_heap을 만들어나가는 과정이기 때문에 last_index는 push()나 pop()이 될 때마다 바뀐다.

max_heap = [None] * (n)
max_heap[0] = 999999999999
last_index = 0

def pop():
    global max_heap
    global last_index

    if last_index == 0:
        return 0
    else:
        top = max_heap[1]
        # cur은 root 노드이다.
        cur = 1
        # 마지막 index에 저장된 n을 index 1에 저장한다.
        max_heap[cur] = max_heap[last_index]
        # 마지막 index에는 None을 넣어주어 없앤다.
        max_heap[last_index] = None
        # n을 index 1에 넣어주었기 때문에 index를 하나 줄여준다.
        last_index -= 1
        # cur 즉, index 1에서 마지막 index일 때까지 반복하고, 
        # 그 전에 max_heap[cur] 값이 두 자식 노드의 값보다 크면 break
        while cur <= last_index:
            # 왼쪽 자식 노드 index
            left = cur * 2
            # 오른쪽 자식 노드 index
            right = cur * 2 + 1

            next_idx = get_next(cur, left, right)
            if max_heap[next_idx] > max_heap[cur]:
                max_heap[next_idx], max_heap[cur] = max_heap[cur], max_heap[next_idx]
                cur = next_idx
            else:
                break
    return top

def get_next(cur, left, right):
    global last_index
    global max_heap

    if right <= last_index:
        return left if max_heap[left] > max_heap[right] else right
    elif left <= last_index:
        return left
    else:
        return cur

# def get_next(cur, left, right)는 반복문 내부 조건문을 줄이기 위해 임의로 만들어준 함수로, 
# 좌, 우 자식 노드의 index가 마지막 index보다 작은지 확인하고, 
# 조건에 부합하는 index를 return 해준다.
# 조건문을 모두 통과하면 현재 n의 index를 돌려주어 반복문 내부 조건에 의해 반복문이 종료된다.

1. 11279: 최대 힙

문제
널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

import sys
sys.stdin = open('input.txt', 'r')
n = int(sys.stdin.readline().rstrip())

max_heap = [None] * (n)
max_heap[0] = 999999999999
last_index = 0

def push(num):
    global max_heap
    global last_index

    last_index += 1
    max_heap[last_index] = num
    cur = last_index
    while cur != 0:
        if cur//2 != 0 and max_heap[cur//2] < max_heap[cur]:
            max_heap[cur], max_heap[cur//2] = max_heap[cur//2], max_heap[cur]
            cur //= 2
        else:
            break

def pop():
    global max_heap
    global last_index

    if last_index == 0:
        return 0
    else:
        top = max_heap[1]
        cur = 1
        max_heap[cur] = max_heap[last_index]
        max_heap[last_index] = None
        last_index -= 1
        while cur <= last_index:
            left = cur * 2
            right = cur * 2 + 1
            next_idx = get_next(cur, left, right)
            if max_heap[next_idx] > max_heap[cur]:
                max_heap[next_idx], max_heap[cur] = max_heap[cur], max_heap[next_idx]
                cur = next_idx
            else:
                break
    return top

def get_next(cur, left, right):
    global last_index
    global max_heap

    if right <= last_index:
        return left if max_heap[left] > max_heap[right] else right
    elif left <= last_index:
        return left
    else:
        return cur


while n > 0:
    inputs = int(sys.stdin.readline().rstrip())

    if inputs == 0:
        x = pop()
        sys.stdout.write(f'{x}\n')
    else: 
        push(inputs)
    n -= 1

heapq를 통한 구현

heapq는 리스트를 힙처럼 사용할 수 있게 해주는 모듈이다.

heapq 모듈은 이진트리(binary tree)기반의 최소 힙(min heap) 자료구조를 제공한다.

 

  • heapq.heappush(heap, item) : item을 heap에 추가
  • heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
  • heapq.heapify(x) : 기존 리스트 x를 heap으로 변환함 (in linear time, O(N) )

삽입은 heapq.heappush(리스트, 데이터)이고, 삭제는 heapq.heappop(리스트)이다.

기본적으로 heapq는 최소 힙을 제공한다. 그러므로 heapq를 최대 힙으로 구현하기 위해서는 삽입할 때 튜플 구조를 통해 우선순위를 지정해줘야 한다. 이렇게 되면 heap에 튜플 구조 자체로 삽입된다. (튜플 구조라는 것을 인지해야함) 그러므로 삭제 시 출력하기 위해서는 index 1 위치에 접근해야 한다. 우선 순위로 -x를 사용하는 이유는 우선순위 값이 작을수록 더 높은 우선순위를 갖기 때문이다.

# 11279: 최대 힙
import sys
import heapq	# 기본적으로 최소 힙 제공
heap = []

n = int(sys.stdin.readline().rstrip())
for i in range(n):
    i = int(sys.stdin.readline().rstrip())
    if i == 0:
        if len(heap) == 0:
            print(0)
        else:
        # 튜플에서 key 값이 아닌 value 값을 꺼내야하기 때문에 index 1 위치에 접근
            print(heapq.heappop(heap)[1])	
    else:
    	# 우선순위 -i를 사용하는 이유는 최소 힙이 아닌 최대 힙을 구할 것이기 때문에 key 값을 반대로 갖도록 함.
        heapq.heappush(heap, (-i, i))

PriorityQueue를 통한 구현

heapq와 달리 아예 새로운 자료구조를 제공해주며 PriorityQueue()를 통해 생성할 수 있다.

삽입은 put, 삭제는 get이며 heapq와 같이 삽입할 때 튜플을 통한 우선순위를 지정할 수 있다. 

# 11279: 최대 힙
from queue import PriorityQueue
if __name__ == "__main__":
    heap = PriorityQueue
    n = int(input())
    for i in range(n):
        x = int(input())
        if x == 0:
            if heap.empty() :
                print(0)
            else:
                print(heap.get()[1])
        else:
            heap.put((-x, x))

2. 1927: 최소 힙

문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

기본적으로 구현한 최대 힙에서 부등호의 방향을 바꿔주면 된다.

더 쉬운 방법으로는 heapq 모듈을 사용하면 되고, heapq 모듈은 기본적으로 최소 힙을 제공하기 때문에 튜플 구조를 통해 우선순위를 설정해주지 않아도 최소 힙을 구현할 수 있다.

# 50015770: 최소 힙
import sys
import heapq	# 기본적으로 최소 힙 제공하기 때문에 튜플을 통해 key값의 우선순위 바꾸지 않아도 됨.
heap = []
n = int(sys.stdin.readline().rstrip())
for i in range(n):
    i = int(sys.stdin.readline().rstrip())
    if i == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap))	
    else:
        heapq.heappush(heap, i)

3. 1927: 가운데를 말해요

문제
백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다.
백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다.
만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

나는 처음에 최대 힙만 이용해서 중간값을 구하려고 했는 로직 과정 자체에서 어려움이 있었다.

[풀이]

왼쪽 힙은 최대 힙으로 정렬하고, 오른쪽 힙은 최소 힙으로 정렬하면 왼쪽 힙의 첫 번째 요소는 항상 중앙값이 된다.

 

left = 최대 힙(내림차순), right = 최소 힙(오름차순)

- 왼쪽 힙의 첫번째 요소는 최대 힙에서 가장 큰 값
- 오른쪽 힙의 첫번째 요소는 최소 힙에서 가장 작은 값

 

  1. 왼쪽 힙과 오른쪽 힙의 길이가 같으면 (요소 * -1)을 왼쪽 힙에 삽입한다. 
    1-1. 그렇지 않으면 오른쪽 힙에 삽입한다.
  2. 왼쪽 힙과 오른쪽 힙에 요소가 존재하고, 왼쪽 힙의 (첫번째 요소 *  -1) 가 오른쪽 첫번째 요소보다 클 때
    2-1. 왼쪽 힙의 첫번째 요소와 오른쪽 힙의 첫번째 요소를 바꿔준다.
  3. 왼쪽 힙의 (첫번째 요소 * -1)를 출력한다.

ex) [1, 5, 2, 10, -99, 7, 5]
num = 1 👉🏻 left = [-1] / right = [] => import heapq를 이용하여 최대 힙을 구하기 때문에 -1을 붙여 최대 힙을 구현한다.
num = 5 👉🏻 left = [-1], right = [5]
num = 2 👉🏻 left = [-2,-1], right = [5]
num = 10 👉🏻 left = [-2,-1], right = [5,10]
num = -99 👉🏻 left = [-2,-1,99], right = [5,10]
num = 7 👉🏻 left = [-2,-1,99], right = [5,7,10]
num = 5 👉🏻 left = [-5,-2,-1,99], right = [5,7,10] => 여기서 heappop을 하게 되면 -1을 곱해서 5가 나오게 된다.

# 11279: 최대 힙

import sys
import heapq
sys.stdin = open('input.txt', 'r')
n = int(sys.stdin.readline().rstrip())
left = []   # 최대 힙
right = []  # 최소 힙

while n > 0:
    num = int(sys.stdin.readline().rstrip())
    if len(left) == len(right):
        heapq.heappush(left, -num)
    else:
        heapq.heappush(right, num)
	
    # left와 right에 요소가 존재하면서, left의 최댓값이 right의 최솟값보다 크면 요소를 바꿔줘야한다.
    # 부등호의 방향이 달라서 계속 틀렸었다.. 
    if left and right and left[0] * -1 > right[0]:
        max_value = heapq.heappop(left)
        min_value = heapq.heappop(right)
    
        heapq.heappush(left, min_value * -1)
        heapq.heappush(right, max_value * -1)

    print(left[0] * -1)
    n -= 1

분명 정답 풀이를 보고 코드를 작성했는데 계속 틀렸습니다가 나와서 다시 찬찬히 뜯어보니, 부등호가 잘못 적혀있었다.

import sys
import heapq
sys.stdin = open('input.txt', 'r')
n = int(sys.stdin.readline().rstrip())
max_heap, min_heap = [], []

for i in range(n):
    num = int(sys.stdin.readline().rstrip())
    if i % 2 == 0:
        heapq.heappush(max_heap, num * -1)
    else:
        heapq.heappush(min_heap, num)

    if max_heap and min_heap and max_heap[0] * -1 > min_heap[0]:
        temp = heapq.heappop(max_heap)* -1
        heapq.heappush(max_heap, heapq.heappop(min_heap) * -1)
        heapq.heappush(min_heap, temp)

    print(max_heap[0] * -1)

https://github.com/jaehyeonkim2358/W02_teamB7/blob/main/1655/1655_cdb.py

 

GitHub - jaehyeonkim2358/W02_teamB7

Contribute to jaehyeonkim2358/W02_teamB7 development by creating an account on GitHub.

github.com

4. 1715: 카드 정렬하기

문제
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다.
예를 들어 10장, 20장, 40장의 묶음이 있다면
(10 + 20) + (30 + 40) = 100번의 비교 필요
(10 + 40) + (50 + 20) = 120 번의 비교 필요 =>덜 효율적인 방법
N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

 

[풀이]

0. cards에 값이 1이면 비교횟수가 0이기 때문에 예외사항으로 print(0)을 출력한다.

1. 현재의 카드 묶음(cards) 중 가장 작은 2개의 카드를 꺼낸다.

=> plus = heapq.heappush(cards) + heapq.heappush(cards) 가 가능하다 !!! 바로 빼지고, 또 빼짐

2. plus를 누적 값을 계산할 result에 넣어준다. 

3. 두 개를 더한 값(plus)을 다시 카드 더미 안(cards)에 넣어준다.

4. 1~4 과정을 cards의 남은 갯수가 1이 되기 전까지 해준다.

import sys
# heapq는 리스트를 힙처럼 사용할 수 있게 해주는 모듈이다.
import heapq
sys.stdin = open('input.txt', 'r')
N = int(sys.stdin.readline())   # 최소 비교 횟수

# 각 묶음의 카드의 수 A, B => 두 묶음을 합쳐서 하나로 만드는데 A+B번 비교
# N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지 구함 !
result = 0
cards = []

for i in range(N):
    heapq.heappush(cards, int(sys.stdin.readline().strip()))

# cards의 갯수가 1이면 비교가 필요없기 때문에 0을 출력
if len(cards) == 1:
    print(0)
else:
    while len(cards) > 1:
        # 오름차순으로하고, 작은 수부터 2개씩 묶어서 더해줘야 가장 효율적인 방법 => 그리디
        # plus에 최소 힙에서 뽑은 가장 작은 원소 하나, 또 하나를 더해준다.
        plus = heapq.heappop(cards) + heapq.heappop(cards)
        # 누적이기 때문에 plus를 result에 넣어준다.
        result += plus
        # plus가 다시 cards에 들어가야하기에 push해서 넣어준다.
        heapq.heappush(cards, plus)

    print(result)

공부 참고 블로그:

From 우리조 JH(교수님🤗): https://velog.io/@jaehyeonkim2358/TIL-22.90.30

백준 우선순위 큐 (최대 힙) 여러 풀이: https://jinyes-tistory.tistory.com/14

힙큐에 대한 자세한 설명: https://www.daleseo.com/python-heapq/

가운데를 말해요 풀이: https://wiselog.tistory.com/158

 

저작자표시