스택
데이터를 임시 저장하기 위한 자료구조로, 데이터를 후입선출(LIFO) 방식으로 처리
- 구조: 쌓아 올린 더미처럼, 데이터를 아래부터 차례로 쌓고 나중에 들어온 데이터부터 꺼냄.
- 장점: 단순한 구조, 빠른 데이터 저장과 읽기.
- 단점: 저장 공간 낭비가 발생할 수 있으며, 미리 최대 저장 개수를 정해야 함.
- 오류: 스택에 데이터를 초과하여 삽입하면 스택 버퍼 오버플로(stack buffer overflow)가 발생.
예시)
뒤로가기(웹 페이지 방문시 URL이 스택에 푸시가 됌, 뒤로 가기를 선택하면 가장 마지막 URL이 팝됌)
재귀함수(함수 호출을 스택에 쌓고, 각 호출이 완료되면 스택에서 제거하면서 최종 결과 계산함)
DFS(스택을 사용하여 그래프 or 트리의 노드를 탐색).
함수의 매개변수를 저장하기 위해 스택을 사용하는 경우가 있다.
주요 연산
push : 데이터를 스택에 삽입.
pop : 스택에서 데이터를 꺼냄.
peek : 스택의 맨 위 항목을 조회.
isEmpty : 스택이 비어 있는지 확인
파이썬 구현
파이썬에서는 리스트 자료형으로 스택을 구현할 수 있으며, append()로 데이터를 넣고, pop()으로 데이터를 꺼냄.
stack = []
stack.append(1) # push
stack.append(2) # push
stack.pop() # pop시간 복잡도
O(1) : 삽입/삭제는 상수 시간에 처리 (맨 위에서 처리).
O(n) : 특정 데이터를 찾기 위해서는 스택의 모든 요소를 확인해야 함.
큐
선입선출(FIFO) 방식의 자료구조로, 입구와 출구가 따로 있음
구조: 데이터가 앞쪽으로 들어오고 뒤쪽으로 나감.
예시: 티켓팅, 은행 업무, 마트 계산대 줄 기다리기
큐는 여러 변형된 형태(deque, 우선순위 큐)로도 사용됨.
주요 연산
put (enqueue) : 데이터를 큐에 삽입.
get (dequeue) : 가장 먼저 삽입된 데이터를 큐에서 꺼냄.
파이썬 구현
파이썬에서는 deque 모듈을 사용해 큐를 효율적 구현 가능.
from collections import deque
queue = deque()
queue.append(1) # enqueue
queue.append(2) # enqueue
queue.popleft() # dequeue시간 복잡도
- O(1): 삽입과 삭제는 상수 시간에 처리.
덱(Deque)
정의 : 양방향 큐의 약자로, 양쪽으로 데이터를 삽입/삭제할 수 있는 큐.
장점 : 스택과 큐의 장점을 모두 갖춤.
사용 : 파이썬으로 BFS 풀 때 deque 사용.
파이썬 구현
파이썬의 collections 모듈에서 제공하는 deque로 구현.
from collections import deque
deque_example = deque()
deque_example.append(1) # 오른쪽 추가
deque_example.appendleft(2) # 왼쪽 추가
deque_example.popleft() # 왼쪽 제거
deque_example.pop() # 오른쪽 제거시간 복잡도
- O(1): 양쪽에서 삽입과 삭제를 상수 시간에 처리.
우선순위 큐
각 데이터에 우선순위를 부여하여 우선순위가 높은 데이터가 먼저 나가는 자료구조
구현: 힙(Heap) 자료구조를 사용하여 구현.
힙(Heap)
- 사용 이유: 배열에서 최대값 또는 최소값을 찾는 데 O(n) 시간이 걸리지만, 힙을 사용하면 O(log n) 시간에 처리가능.
배열 vs 힙을 비교해보자.
배열 (O(n))
- 정렬되지 않은 배열에서 최대값/최소값을 찾으려면 모든 요소를 하나 하나 비교해야 함
- 시간 복잡도는 O(n) → 데이터가 많아질수록 선형적으로 느려짐
- 삽입은 끝에 추가하면 되므로 빠르지만, 삭제나 우선순위 접근은 비효율적이다.
힙 (O(log n))
- 힙은 완전 이진 트리 기반의 자료구조
- 최대 힙은 루트에 최대값, 최소 힙은 루트에 최소값이 위치
- 따라서 최대/최소값 탐색은 O(1)이다.
- 다만, 삽입/삭제 시 트리의 구조를 유지하기 위한 정렬 작업(Heapify) 이 필요 힙의 높이는 log n이므로 → 삽입/삭제는 O(log n)
왜 힙이 우선순위 큐에 적합하지?
- 우선순위 큐는 삽입과 삭제가 빈번한 구조이다.
- 배열로 구현하면 삭제나 우선순위 탐색 시마다 전체를 확인해야 해서 O(n)
- 반면, 힙은 루트에서 바로 꺼낼 수 있고, 정렬도 log n 이내로 처리되어 효율적
- 예를 들어, 100만 개 데이터일 경우: 배열: 최악의 경우 100만 번 비교 힙: 최대 20번 이내 비교로 처리 가능
결론
- 배열 : 단순하지만 우선순위 처리에 비효율적 (O(n))
- 힙 : 약간의 구조적 비용은 있지만 훨씬 효율적 (O(1), O(log n))
- 그래서 대부분의 우선순위 큐는 힙 기반으로 동작함 (Heap Priority Queue)
주요 연산
삽입 : 새로운 노드를 추가한 후, 부모와 비교하여 정렬함.
삭제 : 루트 노드를 삭제한 후, 마지막 노드를 루트로 올리고 자식과 비교하여 재정렬.
파이썬 구현
파이썬의 heapq 모듈을 사용하여 최소 힙을 쉽게 구현한다.
import heapq
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
smallest = heapq.heappop(heap)
min_element = heapq.heappop(heap) # 가장 작은 값 제거시간 복잡도
- 삽입: O(log n)
- 삭제: O(log n)
이진 탐색 트리(BST)
각 노드의 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큰 값을 가지는 이진 트리
장점: 이진 탐색의 효율적인 탐색 능력을 유지하면서도 자료의 삽입과 삭제가 가능.
활용 예시: B+트리, B-트리, 검색 및 정렬 관련 응용(데이터가 정렬된 형태로 유지되므로, 특정 값보다 작은/큰 값 검색에 유리), 자동완성 기능
시간 복잡도
탐색, 삽입, 삭제 : O(log n) (균형이 잡힌 경우).
최종 정리: 스택 / 큐 / 우선순위 큐 / 힙
스택 (Stack)
- LIFO(후입선출) 구조. 마지막에 넣은 데이터를 가장 먼저 꺼낸다.
- push, pop 연산은 O(1) 로 빠르게 처리 가능.
큐 (Queue)
- FIFO(선입선출) 구조. 먼저 들어온 데이터가 먼저 나감.
- enqueue, dequeue 연산 모두 O(1) 시간 복잡도이다.
우선순위 큐 (Priority Queue)
- 데이터마다 우선순위를 부여하여 우선순위가 높은 것부터 처리함.
- 일반적으로 힙을 기반으로 구현하며, 삽입/삭제는 O(log n).
힙 (Heap)
- 완전 이진 트리 기반 자료구조.
- 최댓값/최솟값은 루트 노드에 위치해 O(1)로 조회 가능.
- 삽입/삭제 시 구조 유지를 위해 heapify 과정이 필요하며, 이때 O(log n) 소요.
