오늘의 주제
- 스택/큐 구조와 연산
- 힙과 우선순위 큐
- 덱(Deque)
스택(Stack) / 큐(Queue)
스택(Stack)
- LIFO (Last In First Out)
- 주요 연산: push, pop, peek
- 함수 호출 스택, 되돌리기(Undo), 괄호 검사 등에 활용됨
큐(Queue)
- FIFO (First In First Out)
- 주요 연산: enqueue, dequeue
- 대기열 처리, BFS, 작업 스케줄링 등에 활용됨
힙(Heap)
그림과 같이, 스택이나 큐가 선형적인 순서를 전제로 한 자료구조라면
힙은 데이터의 전체 순서를 유지하기 위한 자료구조는 아니다.
힙의 핵심 목적은 데이터를 순서대로 나열하는 것이 아니라,
가장 큰 값 또는 가장 작은 값을 빠르게 찾는 것에 있다.
힙의 특징
- 완전 이진 트리(perfect binary tree) 구조
- 부모 노드와 자식 노드 사이의 대소 관계만 보장
- 전체 데이터가 정렬되어 있지는 않음
참고: full, complete, perfect binary tree
complete, Perfect Binary Tree => 왼쪽부터 참
힙의 종류
최소 힙 (Min Heap)
- 부모노드의 값이 자식노드의 값보다 항상 작다
- 루트에 항상 최솟값 위치
최대 힙 (Max Heap)
- 부모노드의 값이 자식노드의 값보다 항상 크다
- 루트에 항상 최댓값 위치
힙 연산
힙 구현시 인덱스
힙 추가
- 가장 마지막 리프 노드로 삽입한다.
- 부모 노드와 대소 비교
- 대소관계가 깨졌다면 루트쪽으로 이동 (
sift-up)
힙 삭제
- 루트 노드만을 삭제할 수 있다.
- 루트 노드 삭제시, 가장 마지막 리프 노드를 루트로 올린다.
- 자식 노드들과 대소 비교
- 대소관계가 맞을때까지 아래방향으로 반복적으로
sift-down한다.
시간 복잡도
- 최댓값/최솟값 조회:
O(1) - 삽입:
O(log n) - 삭제:
O(log n)
힙은 정렬보다 느슨하지만
“지금 가장 중요한 값 하나”를 빠르게 다뤄야 할 때 최적화된 구조라고 이해할 수 있다.
우선순위 큐(Priority Queue)
우선순위 큐는 자료구조라기보다는 ‘동작 방식(추상 개념)’ 에 가깝다.
일반 큐가 먼저 들어온 데이터가 먼저 나가는 FIFO 구조 라면,
우선순위 큐는 우선순위가 높은 데이터가 먼저 나가는 구조 인 것
여기서 중요한 점은 다음과 같다.
우선순위 큐는 “무엇을 먼저 꺼낼 것인가”에 대한 규칙이고,
힙은 그 규칙을 효율적으로 구현하기 위한 수단이다.
구현 방법
대부분의 언어에서 우선순위 큐는 힙을 이용해 구현된다.
- 최소 힙 → 우선순위가 낮은 값이 먼저 나감
- 최대 힙 → 우선순위가 높은 값이 먼저 나감
주로 활용되는 문제
- 작업 스케줄링
- 다익스트라 알고리즘
- 가장 큰 값 / 가장 작은 값 반복 추출
- 상위 K개 요소 유지
덱(Deque, Double Ended Queue)
덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.
- 슬라이딩 윈도우
- 특정 조건에서 앞/뒤를 선택적으로 처리해야 하는 문제
- BFS 변형 문제
등에서 활용된다.
문제풀이
백준 11279: 최대 힙
최대 힙을 직접 구현해보는 의의
class MaxHeap:
def __init__(self):
self.heap = []
# 리프노드 맨 마지막 값으로 삽입
def append(self, value):
self.heap.append(value)
self.sift_up(len(self.heap)-1)
# 가장 위 노드 (최댓값) 삭제
def pop(self):
if len(self.heap) == 0 :
return 0
elif len(self.heap) == 1:
return_val = self.heap.pop()
else:
return_val = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return return_val
# 위로 올라가며 비교
def sift_up(self, idx):
while idx > 0:
old_idx = (idx-1) // 2
if self.heap[idx] > self.heap[old_idx]:
self.heap[idx], self.heap[old_idx] = self.heap[old_idx], self.heap[idx]
idx = old_idx
else:
break
# 밑으로 내려가며 비교
def sift_down(self, idx):
size = len(self.heap)-1
while True:
left = idx * 2 + 1
right = idx * 2 + 2
parent = idx
if left <= size and self.heap[left] > self.heap[parent]:
parent = left
if right <= size and self.heap[right] > self.heap[parent]:
parent = right
if parent == idx:
break
self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
idx = parent
import sys
input = sys.stdin.readline
n = int(input())
lst = MaxHeap()
return_lst = []
for _ in range(0, n):
value = int(input())
if value == 0:
return_lst.append(lst.pop())
else:
lst.append(value)
for i in return_lst:
print(i)백준 2696: 중앙값 구하기
위 문제에서 만든 최대힙 + 최소힙을 활용하는 문제
import sys
input = sys.stdin.readline
n = int(input())
for _ in range(0, n):
m = int(input())
case_lst = []
small_lst = MaxHeap()
big_lst = MinHeap()
return_lst = []
while len(case_lst) < m:
case_lst.extend(map(int, input().split()))
for (idx, i) in enumerate(case_lst):
if small_lst.count() == 0 or i <= small_lst.head():
small_lst.append(i)
else:
big_lst.append(i)
if small_lst.count() > big_lst.count() + 1:
big_lst.append(small_lst.pop())
elif big_lst.count() > small_lst.count():
small_lst.append(big_lst.pop())
if idx % 2 == 0:
return_lst.append(small_lst.head())
print(len(return_lst))
for i in range(0, len(return_lst), 10):
print(" ".join(map(str, return_lst[i:i+10])))
정체되지 않는 성장