08. Algorithm_Midterm and Final Review Questions

학습 목표

• 중간고사 범위(1~7장)의 정의, 표기법, 점화식 문제를 빠르게 점검
• 정렬 과정 추적 문제(빈칸 채우기)의 답 확인
• 검색 트리(BST, 레드-블랙, B-트리, KD 트리) 개념 문제 점검
• 상황에 맞는 자료구조와 알고리즘 고르기
• 기말 범위(해시, DP, 그래프, 그리디, 문자열 매칭)의 단골 질문 정리
• 자세한 설명이 필요하면 각 주제의 글로 돌아가기

이 문제들은 강의 자료의 학습 목표와 예시를 바탕으로 직접 만든 예상 문제라서, 실제 시험 문장과 다를 수 있음. 개념 설명은 01 ~ 07편에 있음

---

1. 알고리즘과 분석 (1~11번)

번호	문제	답
1	알고리즘이란?	문제 해결 절차를 체계적으로 기술한 것. 입력으로부터 출력을 만드는 과정
2	요구 조건을 입력과 출력으로 명시한다는 뜻	주어지는 정보가 입력, 만들어야 할 결과가 출력 (예: 학생 100명의 점수 → 최댓값)
3	바람직한 알고리즘의 두 조건	명확성(이해하기 쉽고 간명), 효율성(적은 시간)
4	자료구조와 알고리즘의 관계	자료구조는 데이터를 저장, 조직하는 방식이고 알고리즘은 그 데이터를 처리하는 절차. 함께 문제를 품
5	표기법 네 가지와 가상코드의 장점	자연어, 순서도, 프로그래밍 언어, 가상코드. 가상코드는 언어 문법에 묶이지 않으면서 명확함
6	Big-O의 정의와 “상수배 무시”의 뜻	양수 \(c\), \(n_0\)가 있어 \(n \ge n_0\)에서 \(f(n) \le c\,g(n)\). \(3n\), \(100n\), \(0.5n\)을 모두 \(O(n)\)으로 봄
7	가운데 원소 / 전체 합 / 모든 쌍의 곱의 합	\(O(1)\) / \(O(n)\) / \(O(n^2)\)
8	점화식과 재귀 알고리즘의 관계	점화식은 함수를 더 작은 입력의 자기 자신으로 표현한 것. 재귀 알고리즘의 수행 시간은 자연스럽게 점화식이 됨
9	\(T(n-1)+c\) / \(T(n/4)+c\) / \(2T(n/2)+n\)	\(O(n)\) / \(O(\log n)\) / \(O(n \log n)\)
10	점화식 분석 방법 세 가지	반복 대치, 추정 후 증명, 마스터 정리
11	병합 정렬이 \(2T(n/2) +\) 오버헤드인 이유	절반 크기 문제 두 개를 풀고, 병합에 추가 작업이 필요해서

(중요!!) 점근적 표기법(O, Ω, Θ)의 정의와 증명은 매번 출제됨. 증명 예시는 01편

---

2. 정렬 (12~25번)

번호	문제	답
12	선택 정렬 한 루프의 작업 세 가지	범위에서 최댓값 찾기 → 맨 오른쪽과 교환 → 맨 오른쪽을 범위에서 제외
13	선택 정렬 비교 횟수	\((n-1) + (n-2) + \cdots + 1 = O(n^2)\)
14	거품 vs 삽입, 거의 정렬된 입력에서 유리한 쪽	거품은 인접 교환으로 큰 값을 뒤로, 삽입은 정렬된 앞부분에 끼워 넣음. 삽입 정렬이 유리
15	[29, 10, 14, 37, 13] 선택 정렬 첫 패스	[29, 10, 14, 13, 37]
16	같은 배열 거품 정렬 첫 패스	[10, 14, 29, 13, 37]
17	[10, 14, 29, 37, 13]에서 13 삽입	37, 29, 14를 차례로 오른쪽으로 밀고 → [10, 13, 14, 29, 37]
18	고급 정렬 세 가지와 평균 시간	병합, 퀵, 힙. 평균 \(\Theta(n \log n)\)
19	병합 정렬 네 단계	배열이 주어짐 → 반으로 나눔 → 각각 정렬 → 병합
20	퀵 정렬 평균 / 최악	\(O(n \log n)\) / \(O(n^2)\) (분할이 한쪽으로 몰릴 때)
21	힙 정렬에서 루트와 끝을 바꾼 뒤 힙을 복구하는 과정	heapify (하향 재정렬)
22	비교 정렬 하한과 선형 정렬이 가능한 경우	\(n!\)가지 순서를 비교로 구분해야 해서 \(\Omega(n \log n)\). 값의 범위가 작은 정수(계수 정렬), 자릿수가 제한된 수(기수 정렬)
23	계수 정렬의 조건	원소가 정수이고 값의 범위 \(k\)가 \(O(n)\)을 넘지 않음
24	기수 정렬에 안정 정렬이 필요한 이유	낮은 자릿수에서 정한 순서를 높은 자릿수 정렬 후에도 유지해야 전체가 맞게 정렬됨
25	최악 수행 시간 비교	선택, 거품, 삽입, 퀵 \(O(n^2)\) / 병합, 힙 \(O(n \log n)\) / 계수 \(O(n+k)\) / 기수 \(O(d(n+k))\)

15~17번의 답은 02편에서 패스마다 배열을 출력하는 코드로 확인했음.

선택 정렬
  pass 1: [29, 10, 14, 13, 37]   (최댓값 37 확정)
거품 정렬
  pass 1: [10, 14, 29, 13, 37]
삽입 정렬
  13 삽입: [10, 13, 14, 29, 37]

---

3. 검색 트리 (26~39번)

번호	문제	답
26	레코드, 필드, 검색키	레코드는 한 개체의 정보 묶음(행), 필드는 그 안의 각 정보(열), 검색키는 레코드를 대표하는 중복 없는 필드
27	검색 트리	노드가 규칙에 맞게 키를 가져 원하는 레코드를 빠르게 찾게 해 주는 트리
28	BST가 평균 \(O(\log n)\), 최악 \(O(n)\)인 이유	검색 시간은 높이에 비례. 균형이면 높이 \(\log n\), 한쪽으로 치우치면 \(n\)
29	BST에서 자식이 둘인 노드 삭제	오른쪽 서브트리 최솟값(직후 원소)의 키를 옮기고, 직후 원소 노드를 삭제
30	레드-블랙 트리의 성질	노드는 레드 또는 블랙, 루트 블랙, 리프(NIL) 블랙, 레드의 자식은 블랙, 모든 경로의 블랙 수 동일
31	레드-블랙 트리를 쓰는 이유	균형을 유지해 검색, 삽입, 삭제를 항상 \(O(\log n)\)으로 보장
32	새 노드를 레드로 넣는 이유와 문제가 생기는 경우	블랙으로 넣으면 그 경로만 블랙 수가 늘어남. 부모가 레드일 때만 문제
33	삭제에서 문제가 생기는 유일한 경우	삭제되는 노드 m과 그 자식 x가 모두 블랙
34	B-트리가 디스크에 유리한 이유	한 노드에 키가 여러 개라 높이가 낮고, 디스크 접근 횟수가 줄어듦
35	키가 \(k\)개인 노드의 자식 수	최대 \(k+1\)개
36	B-트리 삭제에서 빌릴 형제가 없을 때	부모의 키를 내려받아 형제와 병합
37	KD 트리	k차원 데이터를 축을 번갈아 기준으로 공간 분할하며 저장하는 이진 검색 트리의 일종
38	KD 트리 삭제의 세 경우	리프, 오른쪽 서브트리가 있는 경우, 왼쪽 서브트리만 있는 경우
39	KD 트리 응용	최근접 이웃 검색, 지도/위치 검색, 그래픽스와 충돌 탐지

04편에서 세 트리를 직접 구현했을 때, 정렬된 입력 5,000개에서 BST의 높이는 5,000, 레드-블랙 트리는 22였음 (28, 31번의 근거).

---

4. 종합 (40~44번)

40. 알고리즘 수업에서 중요한 것은 코딩 자체가 아니라 문제 해결 절차와 생각하는 방법이다 (서술)

알고리즘은 문제를 입력과 출력으로 정의하고, 그 사이의 절차를 설계하는 일이다. 같은 문제라도 어떤 알고리즘을 쓰느냐에 따라 수행 시간이 크게 달라진다. 실제로 과제에서 n = 50,000개를 정렬할 때 거품 정렬은 약 47초, 퀵 정렬은 약 0.03초가 걸렸다. 점화식, 점근적 분석, 정렬의 원리, 트리의 균형 같은 내용은 특정 언어의 문법보다 더 근본적인 사고 방법이다. 따라서 이 수업의 핵심은 문법을 외우는 것이 아니라, 효율적인 해법을 설계하고 그 효율을 분석하는 방법을 배우는 것이다.

41. 상황에 맞는 자료구조/알고리즘

상황	답	이유
일반적인 대량 정렬, 안정적인 \(O(n \log n)\)	병합 정렬	최악도 \(O(n \log n)\)이고 안정 정렬
값의 범위가 매우 작은 정수	계수 정렬	\(\Theta(n + k)\)
디스크 기반 데이터베이스 인덱스	B-트리	높이가 낮아 디스크 접근이 적음
2, 3차원 공간의 점 검색	KD 트리	공간 분할
삽입, 삭제, 검색 모두 \(O(\log n)\) 보장	레드-블랙 트리	균형 유지

42. 기본 정렬과 고급 정렬의 차이: 기본 정렬(선택, 거품, 삽입)은 단순하지만 \(O(n^2)\), 고급 정렬(병합, 퀵, 힙)은 평균 \(O(n \log n)\). 계수, 기수 정렬은 입력 조건이 맞을 때 \(O(n)\)도 가능.

43. 옳은 것 고르기

문장	답	이유
선택 정렬의 최악 수행 시간은 \(O(n)\)	X	\(O(n^2)\)
병합 정렬은 둘로 나눠 각각 정렬한 뒤 병합	O
BST는 항상 \(O(\log n)\) 검색을 보장	X	최악 \(O(n)\)
RB 트리는 균형을 유지해 검색 시간을 보장	O
계수 정렬은 모든 입력에서 \(O(n)\)	X	값의 범위 조건이 필요

44. O/X

문장	답
삽입 정렬은 입력이 거의 정렬된 경우 유리하다	O
퀵 정렬의 평균 수행 시간은 \(O(n \log n)\)이다	O
B-트리는 한 노드가 여러 개의 키를 가질 수 있다	O
KD 트리는 문자열 사전 정렬 전용 자료구조이다	X (다차원 공간 데이터용)
레드-블랙 트리의 모든 리프는 블랙이다	O

---

5. 기말 범위 핵심 질문

주제	질문	답
해시	개방 주소법의 세 방법과 각 문제	선형 조사(1차 군집), 이차 조사(2차 군집), 더블 해싱(군집 예방)
해시	개방 주소법에서 삭제할 때	칸을 비우지 않고 DELETED 표식을 남김
해시	적재율이 1에 가까워질 때	개방 주소법 성능이 급격히 나빠짐 → 테이블을 2배로 늘려 재해싱
DP	DP 적용 조건	최적 부분 구조, 재귀 호출 시 심한 중복
그래프	BFS와 DFS의 자료구조와 시간	큐 / 스택, 둘 다 \(\Theta(V+E)\)
그래프	Prim과 Dijkstra의 v.dist 차이	Prim은 트리에 연결하는 간선 하나의 비용, Dijkstra는 시작점부터의 누적 거리
그래프	Dijkstra가 음의 가중치를 허용하지 않는 이유	확정된 정점을 다시 갱신하지 않아 음의 간선으로 생기는 더 짧은 경로를 놓침
그래프	Bellman-Ford가 \(V-1\)번 반복하는 이유	단순 경로의 간선은 최대 \(V-1\)개
그래프	위상 정렬의 조건	사이클이 없는 유향 그래프(DAG)
그리디	그리디 성공 조건	탐욕적 선택 속성, 최적 부분 구조 (매트로이드면 보장)
그리디	회의실 배정의 최적 기준	종료 시간이 가장 이른 회의부터
문자열	오토마타의 다섯 구성 요소	Q, \(q_0\), A, \(\Sigma\), \(\delta\)
문자열	라빈-카프의 핵심	문자열 비교를 수치 비교로 바꾸고, 나머지 연산과 \(O(1)\) 창 이동

---

최종 핵심 정리

1. 알고리즘은 입력에서 출력을 만드는 절차이고, 명확성과 효율성을 갖춰야 함
2. O, Ω, Θ의 정의와 증명, 점화식 세 가지 분석 방법은 매번 출제되는 핵심
3. 선택/거품 정렬의 첫 패스, 삽입 정렬의 삽입 과정처럼 배열 상태를 쓰는 문제는 직접 손으로 추적해 볼 것
4. 정렬 성능 비교표(최악, 평균, 최선)를 빈칸 없이 채울 수 있어야 함
5. BST는 최악 \(O(n)\), 레드-블랙 트리는 항상 \(O(\log n)\)이며, 레드-블랙 성질과 삽입/삭제에서 문제가 생기는 조건을 기억할 것
6. B-트리는 디스크용 다진 트리, KD 트리는 다차원 공간 분할 트리
7. 기말 범위는 해시 충돌 해결, DP 조건, 그래프 알고리즘의 조건과 시간, 그리디 성공 조건, 문자열 매칭 전처리가 핵심
8. 상황에 맞는 자료구조/알고리즘을 고르는 문제는 각 방법의 조건과 장점을 한 줄로 연결해 두면 풀림

---

End.