[TIL] 알고리즘&자료구조: 스택과 큐, 우선순위 큐
1. 스택 (Stack) & 큐 (Queue)
1-1. 스택 자료구조
-
먼저 들어온 데이터가 나중에 나가는 형식(선입후출)
-
입구와 출구가 동일한 형태, 상자쌓기로 시각화 가능
-
DFS 등 다양한 알고리즘에서 사용되는 자료구조
-
시간복잡도는 항상 O(1)
-
파이썬에서는 리스트 형식을 그대로 사용
📌 구현 예제
stack = []
# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack[::-1]) # 최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력
1-2. 큐 자료 구조 (a.k.a. 공평한 자료구조)
-
먼저 들어온 데이터가 먼저 나가는 형식(선입선출)
-
입구와 출구가 모두 뚫려 있는 터널과 같은 형태, 대기열로 시각화 가능
-
파이썬에서 큐를 구현할 때에는 리스트 형식을 사용하면 시간복잡도가 더 높기 때문에
deque
라이브러리 사용 -
데이터 삽입은
append()
, 데이터 삭제는popleft()
를 사용하므로 해당 메소드의 시간복잡도는 O(n)이지만 관행적으로 사용
📌 구현 예제
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
2. 우선순위 큐 (Priority Queue)
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
- 데이터를 우선순위에 따라 처리하고 싶을 때 사용
- 자료구조 비교표
자료구조 | 추출되는 데이터 |
---|---|
스택(Stack) | 가장 나중에 삽입된 데이터 |
큐(Queue) | 가장 먼저 삽입된 데이터 |
우선순위 큐(Priority Queue) | 가장 우선순위가 높으 데이터 |
-
구현 방법
- 리스트로 구현
- 힙(heap)으로 구현
-
시간 복잡도
우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(log N) O(log N) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업 = 힙 정렬
시간 복잡도: O(N log N)
👉 따라서 힙의 시간 복잡도가 리스트보다 더 낮음!
힙(Heap)의 특징
-
완전 이진 트리 자료구조
루트노드➡왼쪽 자식 노드➡오른쪽 자식 노드 차례로 데이터가 삽입되는 트리
-
항상 루트 노트(root node) 제거
-
다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에 사용된다.
-
최소 힙(min heap)
- 루트 노드가 가장 작은 값을 가진다.
- 값이 가장 작은 데이터가 우선적으로 제거된다.
-
최대 힙(max heap)
- 루트 노드가 가장 큰 값을 가진다.
- 값이 큰 데이터가 우선적으로 제거된다.
최소 힙 구성 함수: Min-Heapify()
- 상향식: 부모 노드로 거슬러 올라가며 부모보다 자신의 값이 더 작은 경우에는 부모와 자신의 위치를 교체
- 새 원소가 삽입되었을 때에는 O(log N)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.
- 힙에서 원소를 제거할 때에도 O(log N)의 시간 복잡도로 힙 성질 유지가 가능하다.
- 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.
- 루트 노드에서 하향식으로
Heapify()
진행
📌 구현 예제
import sys
import heapq # 파이썬의 힙 라이브러리
input = sys.stdin.readLine
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입 (-1을 인자에 넣으면 max heap 가능)
for value in iterable:
heapq.heappush(h, value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 (-1을 인자에 넣으면 max heap 가능)
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
n = int(input())
arr = []
for i in range(n):
arr.append(int(input()))
res = heapsort(arr)
for i in range(n):
print(res[i])
Author And Source
이 문제에 관하여([TIL] 알고리즘&자료구조: 스택과 큐, 우선순위 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minami/알고리즘자료구조-스택과-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)