topic★★★★★난이도 · 약 25분
자료구조
선형(배열·리스트·스택·큐·데크) + 비선형(트리·그래프).
#자료구조
왜 배우는가
각 자료구조의 LIFO/FIFO 특성과 트리 순회가 단답으로 출제.
| 구조 | 분류 | 특징 |
|---|---|---|
| 배열 (Array) | 선형 | 고정 크기, 인덱스 접근 O(1) |
| 연결 리스트 (Linked List) | 선형 | 동적 크기, 포인터 기반 |
| 스택 (Stack) | 선형 | LIFO (후입선출) |
| 큐 (Queue) | 선형 | FIFO (선입선출) |
| 데크 (Deque) | 선형 | 양쪽 끝 삽입/삭제 |
| 트리 (Tree) | 비선형 | 계층 구조 |
| 그래프 (Graph) | 비선형 | 정점·간선 |
이진 트리 순회 — 전위(preorder): Root-L-R / 중위(inorder): L-Root-R / 후위(postorder): L-R-Root / 레벨(level): BFS 방식.
| 이진 트리 종류 | 설명 |
|---|---|
| 정(Full) | 모든 노드가 0 또는 2 자식 |
| 완전(Complete) | 마지막 레벨 제외 꽉 차고, 마지막도 왼쪽부터 |
| 포화(Perfect) | 모든 레벨이 꽉 참 |
| 편향(Skewed) | 한쪽으로만 치우침 |
| 균형(AVL) | 좌우 높이 차 ≤ 1 |
그래프 탐색 — DFS(깊이 우선) 은 스택/재귀, BFS(너비 우선) 는 큐. 최단 경로: 다익스트라(음수 간선 X), 벨만-포드(음수 OK), 플로이드-워셜(모든 쌍). MST: 크루스칼(간선 정렬), 프림(정점 확장).
실기 드릴 3문항
edit실기 드릴 · 단답형
후입선출(LIFO) 특성을 가지는 선형 자료구조는?
edit실기 드릴 · 단답형
이진 트리의 중위(inorder) 순회 순서를 쓰시오.
edit실기 드릴 · 단답형
모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘은?