🗂️ 자료구조 · 알고리즘 (5과목)
📦 선형 구조
| 구조 | 특징 | 대표 응용 |
|---|---|---|
| 배열 | 연속된 공간, 인덱스로 즉시 접근 O(1). 삽입·삭제는 비쌈 | 정적 테이블 |
| 연결 리스트 | 포인터로 연결. 삽입·삭제 쉬움, 임의 접근 불가 | 동적 메모리 |
| 스택 | LIFO (후입선출). Top에서만 삽입(Push)·삭제(Pop) | 함수 호출·재귀·인터럽트 복귀주소, 수식 변환, 되돌리기 |
| 큐 | FIFO (선입선출). Rear 삽입, Front 삭제 | 버퍼·스케줄링·프린터 대기열 |
| 데크Deque | 양쪽 끝에서 삽입·삭제 모두 가능 | 스택+큐 겸용 |
🌳 트리 순회 — 계산 문제 단골
A
╱ ╲
B C
╱ ╲
D E
전위(Preorder) 뿌리 → 왼쪽 → 오른쪽 A B D E C
중위(Inorder) 왼쪽 → 뿌리 → 오른쪽 D B E A C
후위(Postorder) 왼쪽 → 오른쪽 → 뿌리 D E B C A
이름 외우는 법 — 뿌리(Root)를 언제 방문하느냐로 정해진다. 전위 = 앞, 중위 = 가운데, 후위 = 뒤.
왼쪽이 오른쪽보다 먼저인 것은 세 방식 모두 동일하다.
🔢 정렬 알고리즘 — 시간 복잡도
| 알고리즘 | 평균 | 최악 | 특징 |
|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | 인접한 두 개를 비교·교환. 가장 단순 |
| 선택 정렬 | O(n²) | O(n²) | 최솟값을 골라 앞으로 |
| 삽입 정렬 | O(n²) | O(n²) | 거의 정렬된 자료에 유리 (최선 O(n)) |
| 퀵 정렬 | O(n log n) | O(n²) | 피벗 기준 분할. 평균 가장 빠름 |
| 병합 정렬 | O(n log 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) | 정렬 불필요. 처음부터 순서대로 |
| 이진 탐색 | O(log n) | 반드시 정렬되어 있어야 함. 중간값과 비교해 절반씩 줄임 |
| 해싱 | O(1) | 해시 함수로 주소를 직접 계산. 충돌(Collision) 과 오버플로 처리 필요 |
해싱 충돌 해결 — 선형 조사법(다음 빈 칸으로) · 이차 조사법 · 체이닝(연결 리스트로 매달기) · 재해싱
해시 함수 — 제산법(나머지) · 중간제곱법 · 폴딩법 · 기수변환법
해시 함수 — 제산법(나머지) · 중간제곱법 · 폴딩법 · 기수변환법
📝 시험 포인트
• 스택 = LIFO(함수 호출·인터럽트 복귀), 큐 = FIFO(버퍼·스케줄링)
• 트리 순회 — 뿌리를 언제 방문하는가가 이름. 전위 ABDEC / 중위 DBEAC / 후위 DEBCA
• 이진 탐색은 정렬이 전제, O(log n)
• 퀵 = 평균 O(n log n) · 최악 O(n²) / 병합·힙 = 항상 O(n log n)
• 해싱 = O(1)이지만 충돌 처리 필요
• 스택 = LIFO(함수 호출·인터럽트 복귀), 큐 = FIFO(버퍼·스케줄링)
• 트리 순회 — 뿌리를 언제 방문하는가가 이름. 전위 ABDEC / 중위 DBEAC / 후위 DEBCA
• 이진 탐색은 정렬이 전제, O(log n)
• 퀵 = 평균 O(n log n) · 최악 O(n²) / 병합·힙 = 항상 O(n log n)
• 해싱 = O(1)이지만 충돌 처리 필요