우선순위 큐(Priority Queue)와 그리디 알고리즘(Greedy) 파이썬, 백준 1715 파이썬

우선순위 큐

개요

우선순위를 가지는 queue. 정해진 우선순위가 높은 개체가 먼저 Get.

위 그림은 이해를 돕기위한 그림.

구현 방법 1. 일반적인 pq사용

from queue import PriorityQueue

# 생성 방법
myque = PriorityQueue()     # myqueue를 우선순위 큐로 생성

# 기본 함수
put(data)                   # 원소 추가
get()                       # 큐에서 데이터 꺼내기
qsize()                     # 큐 사이즈 가져오기
empty()                     # 큐가 비어 있는지 확인

 

put 연산의 경우 내부에 들어가는 튜플이나 리스트의 원소의 차례대로 우선순위를 가짐.

맨 앞에 있는 것으로 정렬 후 두번째 요소로 정렬 가능.

EX)

pq.put([2, 3])

pq. put([2, 1]) 

pq. get() -> [2, 1]

pq. get() -> [2, 3]

 

구현 방법 2. 기존에 리스트를 pq로 변경

import heapq

# 생성 방법
mylist = []                 # 리스트 생성
heapq.heappush(mylist, 1)   # 리스트에 데이터를 넣을 때 heappq를 이용하여 저장

# 기본 함수
heappush(mylist, data)      # data를 list(heap 자료구조) 형태로 저장
heappop(mylist)             # list(heap 자료구조)에서 데이터 꺼내기
heapify(mylist)             # 일반적인 list를 heap구조로 변환

인자에 리스트가 매번 추가되어 작성하기 불편하므로 heapq 보다는 PriorityQueue를 추천.

 

그리디

개요

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘.

구현이 쉽고 시간복잡도가 우수하지만, 항상 최적의 해를 보장하지 못한다는 단점이 있음.

따라서 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 살펴야 함.

구현 방법

다음의 3단계를 반복하면서 문제를 해결

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복.

백준 문제 1715 카드 정렬 파이썬 풀이

import sys
input = sys.stdin.readline
from queue import PriorityQueue
pq = PriorityQueue()

N = int(input())
answer = 0
for i in range(N):
    pq.put(int(input()))

while 1 != pq.qsize():
    new_card_bucket = pq.get() + pq.get()
    answer += new_card_bucket
    pq.put(new_card_bucket)

print(answer)