4. 자료구조·알고리즘
자료구조
| 구조 | 특징·시간복잡도 |
|---|---|
| 배열 | 접근 O(1), 삽입/삭제 O(n) |
| 연결리스트 | 접근 O(n), 삽입/삭제 O(1) |
| 스택 (LIFO) | push/pop O(1). 함수 호출·역순 처리 |
| 큐 (FIFO) | enqueue/dequeue O(1). 작업 대기열 |
| 해시테이블 | 탐색 평균 O(1). 해시충돌 (체이닝·개방주소) |
| 이진탐색트리 | 탐색 평균 O(log n). AVL·Red-Black 자가균형 |
| 힙 | 최대/최소힙. insert/delete O(log n). 우선순위 큐 |
| 그래프 | 인접리스트·인접행렬. 방향/무방향·가중치 |
정렬 알고리즘
| 알고리즘 | 평균 | 최악 | 안정 |
|---|---|---|---|
| 버블·삽입·선택 | O(n²) | O(n²) | 버블·삽입 O |
| 병합 (Merge) | O(n log n) | O(n log n) | O |
| 퀵 (Quick) | O(n log n) | O(n²) | X |
| 힙 | O(n log n) | O(n log n) | X |
| 기수 (Radix) | O(dn) | O(dn) | O |
탐색·그래프 알고리즘
- DFS: 스택 사용. 깊이 우선
- BFS: 큐 사용. 너비 우선. 최단경로 (가중치 X)
- 다익스트라: 단일 출발점 최단경로. O(E log V) (양수 가중치)
- 벨만-포드: 음수 가중치 가능
- 플로이드-워셜: 모든 쌍 최단경로. O(V³)
- 크루스칼·프림: 최소신장트리 (MST)
📌 출제: 정렬 시간복잡도 + 트리 순회 매년.