Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 파이썬 알고리즘 풀기
- leetcode 풀기
- 잇츠디모
- 릿코드풀이
- 릿코드 풀기
- python zip_longest
- 릿코드 파이썬
- LeetCode
- python sorted
- 파이썬릿코드
- 파이썬알고리즘풀기
- 파이썬 릿코드
- 코틀린기초
- python priority queue
- 알고리즘풀기
- 상가수익률계산기
- 릿코드
- python xor
- 알고리즘풀이
- 릿코드풀기
- 파이썬 알고리즘
- 파이썬 프로그래머스
- leetcode풀이
- binary search
- 파이썬릿코드풀기
- 파이썬알고리즘
- python 릿코드
- leetcode풀기
- python 알고리즘
- python Leetcode
Archives
- Today
- Total
소프트웨어에 대한 모든 것
[파이썬] 우선순위큐(PriorityQueue) 사용법 본문
반응형
Queue는 FIFO(Fist in First Out) 자료구조입니다.
FIFO에서는 처음에 추가된 아이템이 처음으로 빠져나옵니다.
우선순위큐는 큐의 스페셜 타입입니다.
큐는 큐인데 조금 더 특별한 기능(우선순위)을 제공하는 큐라고 생각합니다.
큐는 FIFO이지만, 우선순위큐는 우선순위 기반해서 아이템이 제거됩니다. 즉, 최고 우선순위를 가진 아이템이 먼저 제거됩니다. 우선순위큐의 put(), get() 함수는 O(nlogn) 시간복잡도를 갖습니다.
사용법1) put(), get()
PriorityQueue 객체를 생성하고 put()으로 아이템을 넣으면 내부적으로 오름차순 정렬을 합니다.
get() 함수를 통해서 원소를 가져옵니다.
from queue import PriorityQueue
# 우선순위 큐 객체 생성
q = PriorityQueue()
# 숫자 아이템 추가
q.put(5)
q.put(1)
q.put(10)
q.put(8)
q.put(3)
while not q.empty():
print(q.get(), end=' ')
출력
1 3 5 8 10
사용법2) tuple 오브젝트 저장
우선순유큐는 tuples처럼 오브젝트도 저장할 수 있습니다.
from queue import PriorityQueue
# 우선순위 큐 객체 생성
q = PriorityQueue()
# 튜플 객체 저장
q.put((20, 'james'))
q.put((49, 'adele'))
q.put((15, 'jack'))
q.put((30, 'michael'))
while not q.empty():
print(q.get(), end=' ')
출력
(15, 'jack') (20, 'james') (30, 'michael') (49, 'adele')
사용법3) 클래스 및 대소비교 함수
우선순위 큐에 클래스도 put() 할 수 있습니다.
클래스 내부에는 대소비교 함수 __lt__()를 구현해야 합니다.
lt는 less than의 약어입니다. 우선순위 큐는 내부적으로 __lt__()를 호출해서 대소비교를 합니다.
from queue import PriorityQueue
class Student:
def __init__(self, name, age):
self.name = name
self.age = age
# 대소 비교 메소드 구현
def __lt__(self, other):
return self.age < other.age
# 우선순위 큐 객체 생성
q = PriorityQueue()
# 학생 객체 생성 및 추가
# 학색 클래스의 __lt__(대소비교메소드)를 통해서 age 오름차순 정렬이된다.
q.put(Student('kyle', 22))
q.put(Student('gupy', 21))
q.put(Student('adele', 22))
q.put(Student('melo', 26))
q.put(Student('jack', 22))
while not q.empty():
student = q.get()
print(student.name, student.age)
출력
gupy 21
adele 22
jack 22
kyle 22
melo 26
반응형
'파이썬' 카테고리의 다른 글
[파이썬] isdecimal(), isdigit(), isnumeric() 차이 (0) | 2022.03.02 |
---|---|
[파이썬] map 사용하기 (0) | 2022.02.28 |
[파이썬] sorted() 정렬 함수 파헤치기 (0) | 2022.02.24 |
[파이썬] dict to list 변환 (딕셔너리 to 리스트) (0) | 2022.02.23 |
[파이썬] zip, zip_longest 사용법 (0) | 2021.12.28 |
Comments