백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 우선순위 큐 1번~4번을 파이썬으로 풀어보았다.우선순위 큐 4문제 모두 깃허브에 올려놓았다.
우선순위 큐 단계
우선순위 큐를 응용하여 중앙값을 빠르게 찾는 문제
www.acmicpc.net
tomy9729/Algorithm
🐗 내가 직접 작성한 내 코드 🐗. Contribute to tomy9729/Algorithm development by creating an account on GitHub.
github.com
0. 우선 순위 큐
우선순위 큐란
우선 순위 큐란 데이터 삽입은 어떤 순서로 해도 상관없지만 데이터를 삭제할 때는 우선순위에 맞춰 더 높은 우선순위를 갖는 데이터를 먼저 삭제하는 큐를 말한다. 우선순위 큐는 힙을 통해 구현할 수 있다. 힙이란 완전 이진트리의 일종으로 대표적으로 최대 힙과 최소 힙이 있다.
- 최대 힙 : 루트 노드가 가장 큰 값을 가지며, 부모 노드는 항상 자식 노드보다 큰 값을 갖는다.
- 최소 힙 : 루트 노드가 가장 작은 값을 가지며, 부모 노드는 항상 자식 노드보다 작은 값을 갖는다.
힙에서의 삭제는 항상 루트 노드를 먼저 삭제하며 노드 변동 시 힙의 성질을 만족하도록 힙을 변동시킨다. 이러한 힙의 특징을 이용하여 우선순위 큐를 구현하는 것이다. 사실상 우선순위 큐를 구현하는 것은 힙을 구현하는 것이다.
힙이라는 자료구조는 보통 배열을 통해서 구현한다. 부모 노드의 index가 n일 때 자식 노드의 index는 2n과 2n+1이며 이는 힙이 완전 이진트리이기에 가능한 성질이다. 부모와 자식 간의 비교를 통해 swap 할지 안 할지 결정하여 삽입과 삭제를 한다. 자세한 구현은 아래 1번 문제에서 다뤄본다.
우선순위 큐를 배열과 연결 리스트로 구현하지 않는 이유
배열로 구한다고 가정해보자. 배열에 가장 앞에 우선순위가 가장 높은 데이터가 있다면 삭제 시에는 O(1)만큼 걸린다. 그러나 삽입할 때는 삽입하는 데이터의 위치를 찾아야 하기 때문에 최악의 경우 O(n)의 시간이 걸린다.
연결 리스트로 구현한다고 가정해보자. 제일 처음 노드에 우선순위가 높은 데이터가 있다면 삭제 시에는 배열과 마찬가지로 O(1)만큼 걸린다. 그러나 삽입할 때 또한 배열과 마찬가지로 삽입하는 데이터의 위치를 찾아야 하기 때문에 최악의 경우 O(n)만큼 걸린다.
힙으로 구현할 경우 삭제와 삽입 모두 부모와 자식 간에만 비교를 하기 때문에 삽입, 삭제 모두 최악의 경우 O(log2n)의 시간이 걸린다. 비록 배열과 연결 리스트로 구현 시 삭제하는 부분에서 O(1)이 걸리지만 삭제하는 시간이 훨씬 많기 때문에 힙을 통해서 구현하는 것이다.
추가로 힙은 배열로 구현하게 되는데 단순한 호기심으로 힙을 실제 트리구조로 구현해봤다. 예상으로는 같은 시간이 걸릴줄 알았으나 트리구조로 만든 힙이 더 느렸다. 관련 내용을 찾아봐도 잘 나오지 않았으며 원래 그런 것인지 아니면 내가 잘못 구현한 건지 몰라서 일단은 그냥 넘어갔다.
1. 11279번 최대 힙
문제
널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
파이썬에서는 힙을 구현하는 데 세 가지 방법이 있다. 첫 번째는 당연히 직접 구현하는 것이다. 힙의 삽입, 삭제 과정을 공부하기 위해서 한 번쯤은 반드시 직접 구현해보기를 권장한다. 두 번째는 heapq 모듈을 사용하는 것이다. heapq 모듈은 파이썬의 리스트를 힙처럼 사용할 수 있도록 해주는 모듈이다. 개인적으로 이 방법이 제일 쉽고 좋아 보였다. 세 번째는 PriorityQueue 모듈을 사용하는 것이다. 세 방법으로 모두 코드를 구현해 봤다. 지금부터 하나씩 살펴보자.
최대 힙을 구현해야한다. 최대 힙은 루트가 가장 큰 값을 가지며, 부모 노드가 자식 노드보다 큰 값을 갖는 힙을 말한다.
삽입
heap에 x를 삽입해야한다. x의 크기와 상관없이 우선 heap의 마지막에 x를 삽입한다. 다음으로 x의 위치를 찾아야 한다. 현재 x와 x의 부모 노드를 비교하여 만약 x가 부모 노드보다 크다면 x와 부모 노드의 위치를 바꾼다. 이 과정을 x가 부모 노드보다 작을 때까지, 또는 x가 루트 노드에 도달할 때까지 반복한다.
삭제
힙은 항상 루트 노드를 삭제하면 최대 힙에서 루트 노드는 최댓값이다. 우선 힙의 루트 노드를 출력하여 힙의 최댓값을 보인다. 다음 루트 노드와 힙의 마지막 데이터를 swap 한다. 여기서 마지막 데이터와 swap 하는 이유는 루트 노드를 바로 삭제하면 트리의 모양이 망가지기 때문에 트리를 유지하기 위함이다. heap의 마지막에 존재하는 최댓값은 pop을 통해 삭제한다. 여기까지 진행하면 현재 트리의 루트 노드는 최댓값이 아니므로 최대 힙의 조건에 맞지 않게 된다. 루트 노드의 위치한 데이터의 위치를 재지정해줌으로써 최대 힙의 모양을 유지해야 한다. 현재 루트 노드에 있는 데이터를 x라고 하자. x와 x의 자식 노드 중 더 큰 값과 swap 한다. 이 과정을 더 이상 자식 노드가 없거나 x가 자식 노드보다 클 때까지 반복한다.
#11279번 최대 힙
def insert(heap,x) : # 힙 삽입
heap.append(x) # 힙 마지막에 x 삽입
n = len(heap)-1
while heap[n] > heap[n//2] and n >= 2: # x의 위치 찾기, x가 x의 부모보다 크다면 부모와 swap
temp = heap[n]
heap[n] = heap[n//2]
heap[n//2] = temp
n = n//2
def delete(heap,x) : # 힙 삭제
print(heap[1]) # 현재 최댓값 출력
heap[1] = heap[-1] # 힙 가장 처음 원소에 마지막 원소 삽입
heap.pop() # 힙 길이 감소
p = 1 # 루트 노드
while True : # 가정 처음 원소로 온 값의 위치 찾기
c = 2*p # 자식 노드
if c+1 < len(heap) and heap[c] < heap[c+1] : # 왼쪽 자식과 오른쪽 자식 중 더 큰 자식 찾기
c += 1
if c >= len(heap) or heap[c] < heap[p] : # 더 이상 자식이 없거나 제 위치를 찾으면 종료
break
temp = heap[p]
heap[p] = heap[c]
heap[c] = temp
p = c
if __name__ == "__main__":
heap = [0]
n = int(input())
for i in range(n) :
x = int(input())
if x == 0 :
if len(heap) == 1 :
print(0)
else :
delete(heap,x)
else :
insert(heap,x)heapq를 통한 구현
heapq는 리스트를 힙처럼 사용할 수 있게 해주는 모듈이다. 삽입은 "heapq.heappush(리스트, 데이터)", 삭제는 "heapq.heappop(리스트)" 명령어를 통해 사용할 수 있다.
기본적으로 heapq는 최소 힙을 제공한다. 그러므로 heapq를 최대 힙으로 구현하기 위해서는 삽입할 때 튜플 구조를 통해 우선순위를 지정해줘야 한다. 이렇게 되면 heap에 튜플 구조 자체로 삽입된다. 그러므로 삭제 시 출력하기 위해서는 index 1 위치에 접근해야 한다.
추가로 우선 순위로 -x를 사용하는 이유는 우선순위 값이 작을수록 더 높은 우선순위를 갖기 때문이다.
#11279번 최대 힙
import heapq
if __name__ == "__main__":
heap = []
n = int(input())
for i in range(n) :
x = int(input())
if x == 0 :
if len(heap) == 0 :
print(0)
else :
print(heapq.heappop(heap)[1])
else :
heapq.heappush(heap, (-x,x))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. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
사실상 1번 문제와 같다고도 볼 수 있다. 1번 문제에서 부등호만 바꾸면 되기에 굳이 직접 구현하지는 않고 heapq를 통해 구현했다. heapq는 기본적으로 최소 힙으로 제공되기 때문에 그대로 사용하면 된다.
#1927번 최소 힙
import sys
input = sys.stdin.readline
import heapq
if __name__ == "__main__":
heap = []
n = int(input())
for i in range(n) :
x = int(input())
if x == 0 :
if len(heap) == 0 :
print(0)
else :
print(heapq.heappop(heap))
else :
heapq.heappush(heap,x)
3. 11286번 절댓값 힙
문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
1번, 2번 문제와 매우 유사하나 우선순위가 절댓값으로 바뀌었다. 절댓값이 작은 값을 우선적으로 출력하고 제거해야 한다. abs()를 통해 절댓값이 작을수록 더 높은 우선순위를 갖도록 할 수 있다.
#11286번 절댓값 힙
import sys
input = sys.stdin.readline
import heapq
if __name__ == "__main__":
heap = []
n = int(input())
for i in range(n) :
x = int(input())
if x == 0 :
if len(heap) == 0 :
print(0)
else :
print(heapq.heappop(heap)[1])
else :
heapq.heappush(heap,(abs(x),x))
4. 1655번 가운데를 말해요
문제
수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠 때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.
최대 힙과 최소 힙을 통해 중간값을 빠르게 구하는 문제이다. 숫자를 중간값인 mid, mid보다 작은 수들의 집합 left, mid 보다 큰 수들의 집합 right로 나눠주며 숫자가 하나씩 늘어날 때마다 left의 right의 균형을 맞춰주어 새로운 mid를 계속 갱신해줘야 한다. 그러므로 left와 right에서는 mid가 될 수도 있는 후보 숫자를 바로 추출할 수 있어야 하는데 left에서는 최댓값을 바로 알아야 하므로 최대 힙으로 구현하고, right에서는 최솟값을 바로 알아야 하므로 최소 힙으로 구현한다.
새로 삽입되는 숫자에 대해서 mid보다 크면 right에 삽입하고 mid보다 작으면 left에 삽입한다. 이때 mid는 중간값이어야 하므로 left와 right의 크기가 균형을 맞춰야 한다. 만약 전체 숫자의 개수가 홀수일 경우에는 left와 right의 크기는 같아야 하며, 짝수일 경우에는 right가 left보다 1만큼 커야 한다. left가 right보다 1 크다면 mid를 right에 삽입하고 left의 최댓값을 mid로 갱신하여 균형을 유지한다. 만약 right의 크기가 left보다 2 크다면 mid를 left에 삽입하고 right의 최솟값을 mid로 갱신하여 균형을 유지한다.
#1655번 가운데를 말해요
#import sys
#input = sys.stdin.readline
import heapq
if __name__ == "__main__":
max_heap_left = [] # 중간값보다 작은 값들 - 최대 힙(왼쪽)
min_heap_right = [] # 중간값보다 큰 값들 - 최소 힙(오른쪽)
n = int(input())
mid = int(input()) # 중간값
print(mid)
for i in range(n-1) :
x = int(input())
if x > mid : # mid보다 크다면
heapq.heappush(min_heap_right,x) # 오른쪽 힙에 삽입
if len(min_heap_right) > len(max_heap_left)+1 : # 오른쪽 힙의 개수가 왼쪽 힙보다 2개 이상 많으면
heapq.heappush(max_heap_left,(-mid,mid)) # 중간값 조정
mid = heapq.heappop(min_heap_right)
else : #mid보다 작으면
heapq.heappush(max_heap_left,(-x, x)) # 왼쪽 힙에 삽입
if len(max_heap_left) > len(min_heap_right) : #왼쪽 힙의 개수가 오른쪽 힙보다 1개 이상 많으면
heapq.heappush(min_heap_right,mid) # 중간 값 조정
mid = heapq.heappop(max_heap_left)[1]
print(mid)
'Problem Solving > 백준BOJ' 카테고리의 다른 글
| [BOJ백준] 2475번 검증수.py (0) | 2021.04.26 |
|---|---|
| [백준BOJ] 1259번 팰린드롬수.py (0) | 2021.04.26 |
| [백준BOJ] 단계별로 문제풀기 - 이분 탐색 정답 및 후기(파이썬, pyhton) (0) | 2021.04.19 |
| [백준BOJ] 단계별로 문제풀기 - 분할 정복 정답 및 후기(파이썬, python) (0) | 2021.04.09 |
| [백준BOJ] 단계별로 문제풀기 - 큐, 덱 정답 및 후기(파이썬, python) (0) | 2021.03.17 |
