스택, 큐, 해시 테이블
스택, 큐, 해시 테이블
핵심 개념
요약 스택(LIFO)과 큐(FIFO)는 “제한된 접근 규칙을 가진 인터페이스”로서 O(1) 연산을 보장한다. 해시 테이블은 제약 조건 없이도 O(1) 삽입/검색/삭제가 가능한 가장 효율적인 자료구조이며, 파이썬에서 dict/set으로 구현된다.
주요 내용
1. 스택 (Stack) - LIFO
- 개념: 맨 위(top)에서만 데이터가 들어오고 나가는 구조
- LIFO (Last In, First Out): 마지막에 들어온 것이 먼저 나감
- 비유: 접시 쌓기, 백스페이스 키
기본 오퍼레이션 | 연산 | 설명 | 복잡도 | |——|——|——–| | push(x) | top에 x 추가 | O(1) | | pop() | top에서 제거하고 반환 | O(1) | | peek() | top 값 확인 (제거 X) | O(1) | | isEmpty() | 비어있는지 확인 | O(1) |
구현: 배열 기반(top 인덱스 관리) 또는 링크드 리스트 기반(head를 top으로 사용)
팁 스택 활용 – 괄호 짝 검사 (Balanced Braces)
- 문자열을 왼쪽부터 스캔
- 여는 괄호 -> 스택에
push- 닫는 괄호 -> 스택에서
pop하여 짝 확인- 스캔 완료 후 스택이 비어 있으면 balanced
2. 큐 (Queue) - FIFO
- 개념: 먼저 들어온 데이터가 먼저 나가는 구조
- FIFO (First In, First Out): 줄 서기처럼 처음 들어간 것이 먼저 나감
- 비유: 줄 서기, 우유 진열대
기본 오퍼레이션 | 연산 | 설명 | 복잡도 | |——|——|——–| | enqueue(x) | 뒤(rear)에 x 추가 | O(1) | | dequeue() | 앞(front)에서 제거 반환 | O(1) | | peek() | 맨 앞 데이터 확인 | O(1) | | isEmpty() | 비어있는지 확인 | O(1) |
구현: 링크드 리스트 기반으로 first(head)와 last(tail) 포인터를 함께 관리하면 인큐/디큐가 O(1)
3. 해시 테이블 (Hash Table)
- 핵심: 키(key)를 이용해 곧바로 저장 위치(주소/인덱스)를 계산 -> 처음부터 끝까지 훑지 않아도 됨
- 해시 함수 = “서치 키를 어디에 저장할지 계산하는 주소 계산기(Address Calculator)”
- 제약 조건 없이 삽입/검색/삭제를 O(1)에 수행 가능
Collision(충돌) 해결 | 방식 | 설명 | |——|——| | Open Addressing | 충돌 시 다른 빈 칸을 찾아 분산 저장 (Probing) | | Separate Chaining | 같은 주소에 연결 구조(체이닝)로 묶어 관리 |
- Load Factor (alpha = n/m): 해시 테이블이 얼마나 붐비는지. 커질수록 충돌 가능성 증가
4. 파이썬에서의 해시: dict와 set
- dict (딕셔너리): key:value 페어로 저장.
d[key]로 값 접근 - set (셋/집합): 키만 있고 값은 없음. 중복 제거/멤버십 체크에 강점
집합 연산
- 차집합:
A - B - 합집합:
A | B - 교집합:
A & B - 대칭차(XOR):
A ^ B
연결된 개념
- 스택 - LIFO 자료구조, 괄호 검사/백트래킹에 활용
- 큐 - FIFO 자료구조, BFS 탐색에 활용
- 해시-테이블 - dict/set의 백엔드, O(1) 연산
- DFS - 스택 기반 깊이 우선 탐색
- BFS - 큐 기반 너비 우선 탐색