알고리즘은 "동작 과정" 추적 + "복잡도" 단답
자료구조/알고리즘은 실기에서 1문제 정도 출제되지만, 필기까지 합쳐 보면 자주 나오는 영역이에요. 단답형으로는 알고리즘 이름을 묻고, 서술형으로는 정렬·순회 과정을 단계별로 쓰라는 문제가 나옵니다.
이 과목은 암기 대상이 비교적 적지만, 과정 한 단계를 건너뛰면 전체가 틀리는 구조라서 연필로 직접 시뮬레이션해 보는 연습이 필수예요.
스택 vs 큐
| 구분 | 스택 (Stack) | 큐 (Queue) |
|---|---|---|
| 구조 | LIFO (후입선출) | FIFO (선입선출) |
| 핵심 연산 | push, pop, peek | enqueue, dequeue |
| 대표 응용 | 함수 호출, 수식 괄호, DFS | BFS, 프린터 대기열 |
스택 동작 예시
push 1, push 2, push 3, pop, push 4, pop
push 1→ [1]push 2→ [1, 2]push 3→ [1, 2, 3]pop→ [1, 2] (반환: 3)push 4→ [1, 2, 4]pop→ [1, 2] (반환: 4)
최종 스택: [1, 2], pop된 순서: 3, 4.
큐 동작 예시
enqueue 1, 2, 3, dequeue, enqueue 4, dequeue
- 1, 2, 3 순서로 삽입 → [1, 2, 3]
dequeue→ [2, 3] (반환: 1)enqueue 4→ [2, 3, 4]dequeue→ [3, 4] (반환: 2)
최종 큐: [3, 4], dequeue된 순서: 1, 2.
트리 순회 — 전위 / 중위 / 후위
A
/ \
B C
/ \ \
D E F
| 순회 | 순서 | 결과 |
|---|---|---|
| 전위(Preorder) | 루트 → 왼쪽 → 오른쪽 | A B D E C F |
| 중위(Inorder) | 왼쪽 → 루트 → 오른쪽 | D B E A C F |
| 후위(Postorder) | 왼쪽 → 오른쪽 → 루트 | D E B F C A |
| 레벨(Level) | 레벨 순서대로 | A B C D E F |
이진 탐색 트리(BST) 중위 순회
BST는 중위 순회하면 오름차순으로 정렬된 값이 나옵니다. 단답으로 "BST를 오름차순으로 출력하려면 어떤 순회를 써야 하는가?"를 묻는 문제가 나와요.
그래프 — DFS vs BFS
| 구분 | DFS (깊이 우선) | BFS (너비 우선) |
|---|---|---|
| 자료구조 | 스택 (또는 재귀) | 큐 |
| 동작 | 한 갈래를 끝까지 파고듦 | 같은 거리의 노드를 먼저 |
| 주 용도 | 경로 존재 여부, 백트래킹 | 최단 경로 (가중치 동일) |
DFS 탐색 예시
그래프: A-B, A-C, B-D, B-E, C-F
시작: A, 이웃은 알파벳 순서
- A 방문 → 스택 [A]
- B 방문 → [A, B]
- D 방문 → [A, B, D] → 더 갈 곳 없으면 pop
- E 방문 → [A, B, E] → pop
- C 방문 → [A, C]
- F 방문 → [A, C, F]
방문 순서: A → B → D → E → C → F
BFS 탐색 예시
같은 그래프에서:
- A 큐에 넣음 → 방문: A
- A의 이웃 B, C를 큐에 추가
- B 방문, B의 이웃 D, E 추가
- C 방문, C의 이웃 F 추가
- D, E, F 순서대로 방문
방문 순서: A → B → C → D → E → F
정렬 알고리즘과 복잡도
| 알고리즘 | 평균 | 최악 | 최선 | 안정 정렬 |
|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(n) | ✓ |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | ✗ |
| 삽입 정렬 | O(n²) | O(n²) | O(n) | ✓ |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | ✓ |
| 퀵 정렬 | O(n log n) | O(n²) | O(n log n) | ✗ |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) | ✗ |
- 안정 정렬: 같은 값의 원래 순서를 보존하는 정렬
- 퀵 정렬의 최악은 이미 정렬된 배열에서 피벗을 극단값으로 고를 때 발생
삽입 정렬 한 단계 추적
[5, 2, 4, 1, 3] 오름차순 정렬:
[5]2→ 2를 앞으로 →[2, 5]4 1 3[2, 5]4→ 5 앞으로 →[2, 4, 5]1 3[2, 4, 5]1→ 맨 앞으로 →[1, 2, 4, 5]3[1, 2, 4, 5]3→ 4 앞으로 →[1, 2, 3, 4, 5]
서술형으로 "각 단계별 정렬 결과를 쓰시오"라고 나오면 이런 형태입니다.
해시 테이블과 충돌 해결
해시 함수가 서로 다른 키를 같은 인덱스로 매핑하는 현상이 **충돌(Collision)**입니다. 해결 방법은 두 가지.
| 방법 | 설명 |
|---|---|
| 체이닝(Chaining) | 같은 인덱스에 연결 리스트로 이어 붙임 |
| 개방 주소법(Open Addressing) | 다른 빈 슬롯을 찾아 저장 (선형·제곱·이중 해싱) |
충돌이 자주 발생하면 탐색이 O(n)으로 떨어집니다. 적재율(load factor)을 낮게 유지하는 게 성능 유지의 핵심이에요.
Big-O — 시간 복잡도 위계
자주 등장하는 복잡도를 빠른 순서로 정리하면 이렇습니다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
| 복잡도 | 대표 예시 |
|---|---|
| O(1) | 배열 인덱스 접근, 해시 조회 |
| O(log n) | 이진 탐색, 균형 BST |
| O(n) | 선형 탐색 |
| O(n log n) | 병합·퀵·힙 정렬 |
| O(n²) | 이중 반복문, 버블·선택·삽입 정렬 |
| O(2ⁿ) | 재귀 분할(피보나치 naive) |
자주 나오는 단답 키워드
| 키워드 | 의미 |
|---|---|
| LIFO | 후입선출(스택) |
| FIFO | 선입선출(큐) |
| 이진 탐색 전제 | 정렬되어 있어야 함 |
| 안정 정렬 | 같은 값의 상대 순서 보존 |
| 인 플레이스(In-place) | 추가 메모리 거의 안 씀 |
| 분할 정복 | 큰 문제를 작은 문제로 나눠 풀기 (병합·퀵 정렬) |
자주 틀리는 포인트
| 함정 | 정답 기준 |
|---|---|
| 후위 순회 순서 | 왼 → 오 → 루트 (루트를 나중에) |
| BFS의 자료구조 | 스택 아니고 큐 |
| 퀵 정렬 최악 | O(n²) (이미 정렬된 상태 + 극단 피벗) |
| 해시 최악 탐색 | 모든 키가 같은 버킷 → O(n) |
| 이진 탐색 전제 조건 | 배열이 정렬되어 있어야 함 |
정리
자료구조/알고리즘은 눈으로 코드를 읽지 말고 연필로 단계 하나하나를 적는 연습이 전부입니다. 트리 순회, 정렬 한 pass, DFS/BFS 방문 순서 — 이 세 가지만 종이에 다섯 번씩 따라 해보면 시험장에서 실수할 여지가 거의 사라져요.