[3부] 10장 데크, 우선순위 큐
큐 (Queue)
- 한쪽 끝 (rear) 에서는 삽입 연산만 이루어지고, 다른 한쪽 끝 (front) 에서는 삭제 연산만 이루어지는 유한 순서 리스트
FIFO (First In First Out) 구조
큐에서 데이터를 넣는 것은 put, 데이터를 꺼내는 것은 get 이라고 함.
front 는 데이터를 get 할 수 있는 위치, rear 은 데이터를 put 할 수 있는 위치를 의미함.
queue큐의 다른 형식
- Circular Queue (원형 큐) => 9장 25번 문제 (원형 큐 디자인)
- Priority Queue (우선 순위 큐) => 10장 27번 문제
- Deque (Double-Ended Queue) => 10장 26번 문제 (원형 데크 디자인, 이중 연결 리스트 문제)
데크 (Deque)
- Double-Ended Queue
- 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형 (ADT). 즉, 양쪽에서 삭제와 삽입을 모두 처리할 수 있음.
- 스택과 큐의 특징을 모두 가지고 있음.
- 데크 추상 자료형의 구현은 배열이나, 연결 리스트 모두 가능하며, 이중 연결 리스트 (Doubly Linked List)로 구현하는 편이 가장 잘 어울림.
파이썬은 데크 자료형을 collections 모듈에서 deque 라는 이름으로 지원.
이중 연결 리스트를 이용해 데크 자료형 구현하기 (26번 문제)
| no | title | leedcode | status |
| 26 | 원형 데크 디자인 | 리트코드 641 | O |
| 27 | k개 정렬 리스트 병합 | 리트코드 23 | O |
No.26 원형 데크 디자인
본 문제는 이중 연결 리스트를 이용해 데크 자료형을 직접 구현함.
그러나, 원형 데크를 연결 리스트로 구현하는 것은 원형의 이점을 전혀 살릴 수 없음.
- 연결 리스트는 애초에 빈 공간이라는 개념이 존재하지 않기 때문에 원형이 아무런 의미가 없음.
- 또한 데크의 연산은 맨 처음과 맨 끝의 값을 추출할 뿐, 맨 끝의 다음 값을 추출하는지 등의 연산은 존재하지 않기 때문에 서로 연결되어 있을 필요도 없음.
이 문제는 데크를 소개하면서, 이중 연결 리스트로 구현이 가능하다는 것을 보여주기 위한 구현. tail과 head가 서로 이중 연결 리스트로 연결되어 있으며, 단순히 풀이를 위해 구현된 셈. 실제로 원형의 이점을 살리기 위해서라면 연결 리스트가 아닌 배열로 풀이해야 함.
MySolution) 이중 연결 리스트를 이용한 데크 구현
76ms, 15.4MB
# class ListNode:
# def __init__(self, val=0, right=None, left=None):
# self.val = val
# self.right = right
# self.left = left
class MyCircularDeque:
def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the deque to be k.
"""
self.maxSize = k
self.count = 0
self.head, self.tail = ListNode(None), ListNode(None)
self.head.right = self.tail
self.tail.left = self.head
def insertFront(self, value: int) -> bool:
"""
Adds an item at the front of Deque. Return true if the operation is successful.
"""
if self.count == self.maxSize:
return False
tmp = self.head.right
newNode = ListNode(value)
tmp.left = newNode
newNode.right = tmp
newNode.left = self.head
self.head.right = newNode
self.count += 1
return True
def insertLast(self, value: int) -> bool:
"""
Adds an item at the rear of Deque. Return true if the operation is successful.
"""
if self.count == self.maxSize:
return False
tmp = self.tail.left
newNode = ListNode(value)
tmp.right = newNode
newNode.left = tmp
newNode.right = self.tail
self.tail.left = newNode
self.count += 1
return True
def deleteFront(self) -> bool:
"""
Deletes an item from the front of Deque. Return true if the operation is successful.
"""
if self.count == 0:
return False
tmp = self.head.right.right
self.head.right = tmp
tmp.left = self.head
self.count -= 1
return True
def deleteLast(self) -> bool:
"""
Deletes an item from the rear of Deque. Return true if the operation is successful.
"""
if self.count == 0:
return False
tmp = self.tail.left.left
tmp.right = self.tail
self.tail.left = tmp
self.count -= 1
return True
def getFront(self) -> int:
"""
Get the front item from the deque.
"""
if self.count == 0:
return -1
return self.head.right.val
def getRear(self) -> int:
"""
Get the last item from the deque.
"""
if self.count == 0:
return -1
return self.tail.left.val
def isEmpty(self) -> bool:
"""
Checks whether the circular deque is empty or not.
"""
return self.count == 0
def isFull(self) -> bool:
"""
Checks whether the circular deque is full or not.
"""
return self.count == self.maxSize우선순위 큐 (Priority Queue)
- 데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬의 Priority Queue
- 아직 heap 자료구조에 대해서 공부하기 전이기 때문에 우선순위 큐에 대해서 개념적으로 간단하게 알아봄!
우선순위 큐는 데이터를 추가한 순서대로 제거하는 FIFO 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거할 때는 가장 작은 값을 제거하는 특성을 지닌 자료구조.
- 어떤 특정한 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형
이는 내부적으로 데이터를 정렬된 상태로 보관하는 매커니즘이 있다는 뜻이고, 구체적으로 이야기하면 heapq 모듈을 통해 구현되어 있음.
- PriorityQueue 클래스
- heapq 모듈
PriorityQueue 클래스
PriorityQueue 클래스는 queue 내장 모듈에서 제공되기 때문에 별다른 추가 설치 없이 임포트 할 수 있음.
우선순위 큐 생성
PriorityQueue() 생성자를 이용해서 비어있는 우선순위 큐를 초기화 할 수 있음.
- 우선순위 큐의 디폴트 사이즈는 무한대. 만약 특정 최대 크기를 가진 우선순위 큐가 필요하다면 maxsize를 넘기면 됨.
우선순위 큐에 원소 추가 - put()
PriorityQueue 클래스의 put() 메서드를 이용하여 우선순위 큐에 원소를 추가할 수 있음.
우선순위 큐에 원소 삭제 - get()
PriorityQueue 클래스의 get() 메서드를 이용하여 우선순위 큐에 원소를 삭제할 수 있음.
get() 메서드는 삭제된 원소를 리턴하기 때문에, 위와 같이 출력을 해보면, 크기 순서대로 원소가 삭제됨을 알 수 있음.
정렬 기준 변경
만약 단순 오름차순이 아닌 다른 기준으로 원소가 정렬되기를 원한다면, (우선순위, 값)의 튜플의 형태로 데이터를 추가하고 제거하면 됨.
내부적으로 heap 모듈을 사용하는 PriorityQueue 클래스의 put(), get() 함수는 O(log n) 의 시간 복잡도를 가짐.
heapq 모듈
우선순위 큐는 우선 순위가 가장 높은 자료(data)를 가장 먼저 꺼낼 수 있는 자료 구조.
파이썬에서는 heapq 라는 내장 (built-in) 모듈로 제공이 되기 때문에, 추가적인 연산이 필요 없다면 내장 모듈을 사용하는 편이 좋음.
Heap 이란 자료구조 중 하나로서 우선순위 큐를 위해 만들어진 구조
최솟값, 최댓값을 계속해서 호출해야 하는 상황인 경우 Heap 구조를 이용하여 구현하면 시간 측면에서 굉장히 효율적인 구현이 가능.
기본적으로 Min-Priority-Queue 구조를 가짐. (파이썬의 heapq 모듈은 최소 힙을 지원)
기존 배열을 heap 구조로 변환 - heapify()
Heap에 요소 추가하기 - heappush(배열이름, 요소)
Heap 요소 삭제하기 - heappop(배열이름)
| PriorityQueue | heapq |
| 파이썬에서 우선순위 큐는 queue 모듈의 priorityQueue 클래스를 이용할 수 있음. 그러나 우선순위 큐는 heap을 사용해 주로 구현하며, 파이썬의 PriorityQueue 조차 내부적으로는 heapq를 사용하도록 구현되어 있음. |
|
| 스레드 세이프 (Thread-Safe) 보장 | 스레드 세이프 (Thread-Safe) 보장하지 않음. |
스레드 세이프 (Thread-Safe)
- 멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제가 없는 것.
- 즉, 하나의 함수가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 그 함수를 호출하여 동시에 함게 실행되더라도 각 스레드에서의 함수의 수행 결과가 올바르게 나오는 것.
- 멀티 스레드에도 안전한 프로그래밍 개념. 만약 스레드 세이프 하지 않은 경우 1번 스레드의 값이 2번 스레드에서 변경될 수 있어 문제 발생.
- 파이썬은 GIL의 특성상 멀티 스레딩이 거의 의미가 없기 때문에, PriorityQueue 모듈의 멀티 스레딩 지원은 사실 큰 의미가 없음. 또한 스레드 세이프를 보장한다는 이야기는 내부적으로 락킹(Locking)을 제공한다는 의미이므로, 락킹 오버헤드(Locking Overhead) 가 발생해 성능에 영향을 끼침.
- 따라서 굳이 멀티 스레드로 구현할 게 아니라면 PriorityQueue 모듈은 사용할 필요가 없음.
- 실무에서도 우선순위 큐는 대부분 heapq로 구현하고 있음.
GIL (Global Interpreter Lock)
- 하나의 스레드가 자원을 독점하는 형태.
- 파이썬에서는 스레드를 여러 개 생성한다고해서, 여러 개의 스레드가 동시에 실행되는 것은 아님. 정확히 말하면 두 개의 스레드가 동시에 실행되는 것처럼 보일 뿐, 특정 시점에서는 여러 개의 스레드 중 하나의 스레드만 실행됨.
- CPython은 개발 초기에 번거로운 동시성 관리를 편리하게 하고, 스레드 세이프하지 않은 CPython의 메모리 관리를 쉽게 하기 위해, GIL로 파이썬 객체에 대한 접근을 제한하는 형태로 설계함.
No.27 k개 정렬 리스트 병합
My Solution)
108ms, 18.3MB
시간 복잡도: O(n^2)
- 연결 리스트 => 리스트로 변환
- 리스트 정렬
- 리스트 => 연결 리스트로 변환
책 풀이
Solution 1) 우선순위 큐를 이용한 리스트 병합
이해 못함..
