응용정보기술자시험 과목A 제5회: 자료구조·탐색·정렬

AP 과목 A 제5편 · 2026년도·실라버스 Ver.7.2 기준의 독립 학습 자료입니다. IPA와 제휴하지 않으며 합격을 보장하지 않습니다. 시리즈 허브 보기

개정일: 2026-10-20 대상 범위: 2026년 시험, IPA 응용정보기술자시험 실러버스 Ver.7.2 기준 주의: 시험 전에 반드시 IPA 공식 사이트에서 최신 실러버스와 시험 정보를 다시 확인하세요. 이 글은 학습 보조 자료이며 합격을 보장하지 않습니다. IPA가 이 글을 검토하거나 보증한 것은 아닙니다.

학습 목표
용어 대조표 (한국어↔일본어↔영어)
복잡도 읽는 법과 이 글의 비용 가정
자료구조 선택 기준과 트레이드오프
탐색: 선형 탐색과 이진 탐색
정렬: 알고리즘별 특징과 비교표
예제 풀이 (4개 이상)
오리지널 연습문제 4문항
복잡도 퀵 시트
자주 하는 실수
최종 자기 점검
복습 제안 (1일/3일/7일)
실러버스 대응
출처·참고
범위 경계와 다음 회 예고

1. 학습 목표

이 회를 마치면 다음을 할 수 있어야 합니다.

배열·연결 리스트·스택·큐·트리·힙의 특징을 설명하고, 주어진 상황에 맞는 구조를 근거와 함께 고를 수 있다.
스택(LIFO)과 큐(FIFO)의 상태 변화를 한 단계씩 정확히 추적할 수 있다.
이진 탐색의 전제 조건(정렬 + 임의 접근)을 설명하고, 정해진 규칙에 따라 비교 횟수를 셀 수 있다.
주요 정렬 알고리즘의 최선/평균/최악 시간 복잡도, 보조 공간, 안정성, 제자리 여부를 조건과 함께 말할 수 있다.
Big-O가 “실행 시간(초)“이 아니라 “입력 크기에 대한 증가 차수”라는 점을 구분할 수 있다.

2. 용어 대조표 (한국어↔일본어↔영어)

한국어	일본어	영어
배열	配列	array
연결 리스트	連結リスト（リンク付リスト、線形リスト）	linked list
노드	ノード（節、セル）	node
포인터 / 링크	ポインタ / リンク	pointer / link
스택	スタック	stack
큐	キュー（待ち行列）	queue
트리	木（木構造）	tree
루트 / 리프 / 간선	根 / 葉 / 枝	root / leaf / edge
이진 탐색 트리	2分探索木	binary search tree (BST)
균형 트리	バランス木（平衡木）	balanced tree
힙	ヒープ	heap
선형 탐색	線形探索（法）	linear search
이진 탐색	2分探索（法）	binary search
정렬	整列（ソート）	sorting
안정 정렬	安定なソート（安定ソート）	stable sort
제자리 정렬	インプレースなソート（その場での整列）	in-place sort
시간 복잡도	時間計算量	time complexity
공간 복잡도	領域計算量（空間計算量）	space complexity

용어 주의: 일본어의 「内部ソート」(내부 정렬)는 “데이터를 주기억장치 안에서 정렬한다”는 뜻으로, “추가 메모리를 거의 쓰지 않는다”는 제자리(in-place) 정렬과는 다른 개념입니다.

3. 복잡도 읽는 법과 이 글의 비용 가정

3.1 Big-O는 증가 차수다

O(n), O(n²), O(log n) 같은 표기는 입력 크기 n이 커질 때 작업량이 어떤 차수로 늘어나는지를 나타냅니다.
실행 시간(초)을 직접 뜻하지 않습니다. 같은 O(n log n)이라도 상수 계수, 메모리 접근 패턴, 하드웨어에 따라 실제 시간은 달라집니다. n이 작을 때는 O(n²) 알고리즘이 더 빠를 수도 있습니다.

3.2 최선·평균·최악과 보조 공간

최선(best): 가장 유리한 입력에서의 작업량. 예: 이미 정렬된 입력에서의 삽입 정렬.
평균(average): 입력 분포를 가정했을 때의 기대 작업량.
최악(worst): 가장 불리한 입력에서의 작업량. “보장”을 말할 때는 최악을 봅니다.
보조 공간(auxiliary space): 입력 자체를 담는 공간을 제외하고 알고리즘이 추가로 쓰는 메모리. “제자리 정렬”은 보조 공간이 O(1)(또는 그에 가까운 작은 양)인 정렬을 말합니다.

3.3 이 글의 비용 가정

배열: 원소가 메모리에 연속 배치되며, 인덱스로 임의 위치에 O(1)로 접근할 수 있다고 가정합니다.
연결 리스트: 각 노드가 다음(양방향이면 이전도) 노드로의 링크를 가지며, k번째 노드에 가려면 앞에서부터 링크를 따라가야 한다고 가정합니다.
비교 1회, 교환 1회, 링크 1회 따라가기는 각각 상수 시간으로 봅니다.

4. 자료구조 선택 기준과 트레이드오프

4.1 배열 (配列 / array)

인덱스 접근: O(1). A[i]의 주소를 바로 계산할 수 있기 때문입니다.
중간 삽입·삭제: 보통 O(n). 위치 k에 넣거나 빼면 그 뒤 원소들을 한 칸씩 밀거나 당겨야(시프트) 합니다.
장점: 연속 배치라 캐시 지역성이 좋아, 순차 처리가 실제로 빠른 경우가 많습니다.
동적 배열의 끝 추가: 분할 상환(amortized) O(1). 용량이 차면 더 큰 영역을 확보해 전체를 복사(O(n))하므로, 매번 O(1)이 보장되는 것은 아닙니다. 많은 추가를 평균 내면 1회당 O(1)이라는 뜻입니다.
실러버스 용어: 다차원 배열, 정적 배열, 동적 배열.

4.2 연결 리스트 (連結リスト / linked list)

위치 접근·탐색: O(n). k번째로 가려면 머리부터 링크를 따라가야 합니다.
삽입·삭제: 대상 위치(노드)와 바꿔야 할 링크를 이미 알고 있을 때만 O(1). 위치를 찾는 과정이 필요하면 그 탐색이 O(n)입니다.
- 단방향 리스트에서 어떤 노드를 삭제하려면 그 앞 노드를 알아야 합니다. 양방향 리스트는 해당 노드만 알면 앞뒤 링크를 고쳐 O(1)에 삭제할 수 있습니다.
단점: 노드마다 포인터를 저장하는 오버헤드가 있고, 노드가 흩어져 있어 캐시 지역성이 약합니다.
실러버스 용어: 단방향 리스트, 양방향 리스트, 환형 리스트.

4.3 스택과 큐

	스택 (スタック / stack)	큐 (キュー / queue)
원칙	LIFO (후입선출)	FIFO (선입선출)
넣기	push	enqueue
꺼내기	pop (가장 최근에 넣은 것)	dequeue (가장 먼저 넣은 것)
쓰임 예	실행 취소(Undo) 이력, 괄호 짝 검사, 함수 호출 관리	프린터 작업 대기열, 요청 버퍼, 너비 우선 탐색(BFS)

4.4 트리, 이진 탐색 트리, 균형 트리, 힙

트리: 계층 구조. 맨 위가 루트(根), 자식이 없는 노드가 리프(葉), 노드를 잇는 선이 **간선(枝)**입니다.
이진 탐색 트리(BST): 각 노드에 대해 “왼쪽 부분 트리의 키 < 노드의 키 < 오른쪽 부분 트리의 키”(중복 키 처리 규칙은 구현마다 다름)라는 순서가 유지됩니다.
- 일반 BST는 삽입 순서에 따라 한쪽으로 치우칠 수 있습니다. 예: 1, 2, 3, 4, 5 순서로 넣으면 사실상 리스트가 되어 탐색 최악 O(n).
- 균형 BST(AVL 트리 등)는 높이를 O(log n)으로 유지하므로 탐색·삽입·삭제가 O(log n). B 트리도 균형을 유지하는 다분 탐색 트리입니다.
힙: 완전 이진 트리이면서 “부모 ≥ 자식”(최대 힙) 같은 부모-자식 간 순서만 유지합니다.
- 최대값 확인 O(1), 삽입·최대값 꺼내기 O(log n) → 우선순위 큐에 적합.
- 전체가 정렬된 수열이 아닙니다. 형제끼리, 다른 가지끼리는 순서가 정해져 있지 않습니다.
- 그래서 임의 키 탐색에는 부적합합니다(일반적으로 O(n)).

4.5 한 줄 선택 기준

인덱스 접근이 잦다 → 배열
이미 손에 쥔 위치에서 삽입·삭제가 잦다 → (양방향) 연결 리스트
가장 최근 것부터 처리 → 스택 / 들어온 순서대로 처리 → 큐
가장 우선순위 높은 것부터 반복 처리 → 힙
키 순서를 유지하며 탐색·갱신이 잦다 → 균형 BST

5. 탐색

5.1 선형 탐색 (線形探索 / linear search)

앞에서부터 하나씩 비교합니다. 정렬이 필요 없습니다.
시간 복잡도: 최악 O(n), 평균도 O(n).
연결 리스트에도 그대로 적용할 수 있습니다.

5.2 이진 탐색 (2分探索 / binary search)

전제 조건 두 가지:
1. 탐색 범위가 정렬되어 있을 것.
2. 중앙 위치에 직접(임의) 접근할 수 있을 것 (배열처럼 인덱스로 O(1) 접근).
비교할 때마다 범위가 절반으로 줄어 O(log n).
정렬된 연결 리스트라도 자동으로 O(log n)이 되지는 않습니다. 중앙 노드에 가려면 링크를 따라 이동해야 하고, 이동량이 대략 n/2 + n/4 + … 로 합계 O(n)이 됩니다. 비교 횟수는 log 수준이어도 접근 비용이 O(n)이므로 이점이 사라집니다.

5.3 이 글의 비교 횟수 규칙 (예제·문제 공통)

정확한 횟수를 세기 전에 규칙을 먼저 정합니다.

선형 탐색: 원소 하나와 목표값을 비교하는 것을 1회로 셉니다. 정렬된 배열이어도 “목표보다 큰 값이 나오면 중단”하는 조기 종료는 하지 않는 기본형으로 셉니다.
이진 탐색: 인덱스는 0부터, 처음 low = 0, high = n − 1. 중앙은 mid = ⌊(low + high) / 2⌋ (소수점 이하 버림). A[mid]와 목표값을 비교해 “같다/작다/크다”를 판정하는 것을 **1회(1 프로브)**로 셉니다.
- 같으면 종료, A[mid] < 목표이면 low = mid + 1, A[mid] > 목표이면 high = mid − 1. low > high가 되면 “없음”으로 종료합니다.
- 참고: 교재에 따라 “같은지”와 “작은지”를 따로 2회로 세기도 하므로, 시험 문제에서는 문제의 규칙을 우선하세요.
이 규칙에서 크기 n 배열의 이진 탐색 최대 프로브 수는 ⌊log₂ n⌋ + 1 입니다.

5.4 해시 표 탐색에 대한 짧은 메모

실러버스의 같은 항목에는 해시 표 탐색법과 시노님(충돌) 대책도 용어 예로 나옵니다. 해시 함수가 키를 고르게 분산하고 적재율이 낮게 유지되면 평균적으로 O(1)에 가깝지만, 충돌이 한곳에 몰리면 최악 O(n)까지 나빠질 수 있습니다. 충돌 대책으로는 체인법, 개방 주소법 등이 있습니다. 이 회에서는 여기까지만 다룹니다.

6. 정렬

6.1 알고리즘별 핵심

버블 정렬: 인접한 두 원소를 비교·교환하는 패스를 반복합니다. 패스 1회마다 남은 범위의 최대값이 끝으로 이동합니다. “교환이 한 번도 없으면 종료” 플래그(조기 종료)를 둔 경우에만 이미 정렬된 입력에서 최선 O(n). 평균·최악 O(n²). 안정, 제자리.
선택 정렬: 남은 범위에서 최솟값을 찾아 맨 앞과 교환합니다. 입력과 무관하게 비교 횟수가 n(n−1)/2 이므로 모든 경우 O(n²). 멀리 떨어진 원소를 교환하므로 일반적으로 불안정. 제자리.
삽입 정렬: 정렬된 앞부분에 다음 키를 알맞은 위치에 끼워 넣습니다. 표준 구현에서 이미 정렬되었거나 거의 정렬된 입력이면 최선 O(n). 평균·최악 O(n²). 안정, 제자리.
셸 정렬: 간격(gap)을 두고 떨어진 원소끼리 삽입 정렬을 하고, 간격을 점점 줄여 마지막에 간격 1로 마무리하는 삽입 정렬 계열입니다. 시간 복잡도는 간격 수열에 따라 달라지며, 하나의 보편적 상한으로 말할 수 없습니다. 일반적으로 불안정.
병합(머지) 정렬: 정렬된 작은 묶음(런)을 두 개씩 병합해 키워 갑니다. 모든 경우 O(n log n). 안정. 배열에서의 전형적 구현은 O(n) 보조 공간이 필요합니다.
퀵 정렬: 피벗을 기준으로 작은 쪽/큰 쪽으로 분할하는 과정을 반복합니다. 평균 O(n log n), 최악 O(n²)(예: 이미 정렬된 입력에서 항상 맨 끝을 피벗으로 고르는 경우). 일반적으로 불안정. 공간은 구현·재귀 스택·피벗 전략에 따라 다릅니다(분할 자체는 제자리로 할 수 있지만, 호출 스택이 평균적으로 O(log n), 단순 구현의 최악에는 O(n)까지 쓰일 수 있음).
힙 정렬: 배열을 최대 힙으로 만든 뒤, 루트(최대값)를 끝과 교환하고 힙을 재구성하는 것을 반복합니다. O(n log n). 제자리. 일반적으로 불안정.

6.2 비교표

알고리즘	최선	평균	최악	보조 공간	안정성	제자리
버블 (조기 종료 있음)	O(n)	O(n²)	O(n²)	O(1)	안정	예
선택	O(n²)	O(n²)	O(n²)	O(1)	일반적으로 불안정	예
삽입 (표준 구현)	O(n)	O(n²)	O(n²)	O(1)	안정	예
셸	간격 수열에 의존	간격 수열에 의존	간격 수열에 의존	O(1)	일반적으로 불안정	예
병합 (배열 구현)	O(n log n)	O(n log n)	O(n log n)	O(n)	안정	아니오 (전형적 구현)
퀵	O(n log n)	O(n log n)	O(n²)	구현·스택·피벗 전략에 의존	일반적으로 불안정	분할은 제자리 가능
힙	O(n log n)※	O(n log n)	O(n log n)	O(1)	일반적으로 불안정	예

※ 서로 다른 키를 가정. 조기 종료 플래그가 없는 버블 정렬은 최선도 O(n²)입니다.

6.3 안정성이란

같은 키를 가진 원소들의 원래 상대 순서가 정렬 후에도 유지되면 안정 정렬입니다. 예: 선택 정렬로 [2a, 2b, 1](a, b는 원래 순서 표시)을 정렬하면, 최솟값 1을 맨 앞 2a와 교환해 [1, 2b, 2a]가 됩니다. 2a와 2b의 순서가 뒤바뀌었으므로 이 입력에서 선택 정렬은 불안정합니다.

7. 예제 풀이

예제 1: 상황별 자료구조 선택

상황	선택	이유
센서 값을 끝에 계속 추가하고, “k번째 값”을 자주 읽는다	동적 배열	인덱스 접근 O(1), 끝 추가는 분할 상환 O(1)
편집기에서 “실행 취소”	스택	가장 최근 작업부터 되돌림 (LIFO)
프린터 작업을 도착 순서대로 처리	큐	FIFO
응급도가 가장 높은 환자부터 반복 처리, 수시로 새 환자 추가	힙 (우선순위 큐)	삽입·최댓값 꺼내기 O(log n)
회원 ID 순서를 유지하며 탐색·추가·삭제가 잦고, 범위 조회도 필요	균형 BST	탐색·갱신 O(log n), 중위 순회로 순서대로 나열 가능
커서가 가리키는 노드를 이미 알고 있고, 그 자리에서 삽입·삭제가 잦다	양방향 연결 리스트	노드와 링크를 알고 있으므로 O(1)

예제 2: 스택과 큐의 상태 변화

같은 순서로 A, B를 넣고 1개 꺼내고, C, D를 넣고 2개 꺼냅니다. 상태는 왼쪽이 “먼저 들어온 쪽”입니다.

스택 (오른쪽 끝이 top)

단계	연산	꺼낸 값	상태
0	(시작)	–	[ ]
1	push A	–	[A]
2	push B	–	[A, B]
3	pop	B	[A]
4	push C	–	[A, C]
5	push D	–	[A, C, D]
6	pop	D	[A, C]
7	pop	C	[A]

꺼낸 순서: B, D, C. 남은 것: [A].

큐 (왼쪽 끝이 front)

단계	연산	꺼낸 값	상태
0	(시작)	–	[ ]
1	enqueue A	–	[A]
2	enqueue B	–	[A, B]
3	dequeue	A	[B]
4	enqueue C	–	[B, C]
5	enqueue D	–	[B, C, D]
6	dequeue	B	[C, D]
7	dequeue	C	[D]

꺼낸 순서: A, B, C. 남은 것: [D].

예제 3: 선형 탐색 vs 이진 탐색

정렬된 배열 (인덱스 0~9, n = 10):

인덱스	0	1	2	3	4	5	6	7	8	9
값	3	8	12	17	21	26	30	34	41	47

규칙은 5.3절과 같습니다.

(a) 34 찾기

선형 탐색: 3, 8, 12, 17, 21, 26, 30, 34 → 8회 (인덱스 7에서 발견).
이진 탐색:

프로브	low	high	mid	A[mid]	판정
1	0	9	4	21	21 < 34 → low = 5
2	5	9	7	34	발견

→ 2회.

(b) 10 찾기 (없는 값)

선형 탐색: 조기 종료 없는 기본형이므로 10개 모두 비교 → 10회 후 “없음”.
이진 탐색:

프로브	low	high	mid	A[mid]	판정
1	0	9	4	21	21 > 10 → high = 3
2	0	3	1	8	8 < 10 → low = 2
3	2	3	2	12	12 > 10 → high = 1
–	2	1	–	–	low > high → 없음

→ 3회.

(c) 최악의 경우: n = 10이면 ⌊log₂ 10⌋ + 1 = 3 + 1 = 4회. 예: 47을 찾으면 mid = 4(21), 7(34), 8(41), 9(47)로 4회.

예제 4: 정렬 패스 추적

입력: [5, 2, 9, 1, 6] (오름차순).

(a) 버블 정렬 — 왼쪽부터 인접 쌍을 비교하고, 왼쪽이 크면 교환. 비교 1회 = 인접 두 원소 비교 1번.

패스 1 (비교 4회):

비교 쌍	교환?	결과
(5, 2)	예	[2, 5, 9, 1, 6]
(5, 9)	아니오	[2, 5, 9, 1, 6]
(9, 1)	예	[2, 5, 1, 9, 6]
(9, 6)	예	[2, 5, 1, 6, 9]

→ 비교 4회, 교환 3회. 최댓값 9가 맨 끝에 확정.

패스 2 (확정된 끝을 제외하고 비교 3회): (2, 5) 교환 없음 → (5, 1) 교환 [2, 1, 5, 6, 9] → (5, 6) 교환 없음. 비교 3회, 교환 1회.

패스 3 (비교 2회): (2, 1) 교환 [1, 2, 5, 6, 9] → (2, 5) 교환 없음. 비교 2회, 교환 1회.

패스 4 (비교 1회): (1, 2) 교환 없음.

합계: 비교 4 + 3 + 2 + 1 = 10회 (= n(n−1)/2), 교환 5회. 참고: 이미 정렬된 5개 입력이라면, 조기 종료 플래그가 있을 때 패스 1에서 비교 4회(= n − 1), 교환 0회로 종료합니다.

(b) 삽입 정렬 — 같은 입력. 비교 1회 = 꺼낸 키와 정렬된 부분의 원소 1개 비교. 배열 맨 앞에 도달해 멈추는 것은 비교로 세지 않습니다. “이동” = 원소를 오른쪽으로 한 칸 미는 것.

단계	키	비교 내용	비교	이동	결과
1	2	5 > 2 (이동), 맨 앞 도달	1	1	[2, 5, 9, 1, 6]
2	9	5 > 9? 아니오 → 정지	1	0	[2, 5, 9, 1, 6]
3	1	9 > 1, 5 > 1, 2 > 1 (모두 이동), 맨 앞 도달	3	3	[1, 2, 5, 9, 6]
4	6	9 > 6 (이동), 5 > 6? 아니오 → 정지	2	1	[1, 2, 5, 6, 9]

합계: 비교 7회, 이동 5회. 버블의 교환 5회, 삽입의 이동 5회는 모두 입력의 역순쌍 수(5, 2), (5, 1), (2, 1), (9, 1), (9, 6) = 5개와 일치합니다. “같으면 이동하지 않는다(>로 비교)” 규칙 덕분에 삽입 정렬은 안정합니다.

(c) 병합 정렬의 라운드 — 입력 [6, 3, 8, 1, 7, 2, 5, 4] (n = 8). 길이 1의 런에서 시작해 이웃한 두 런을 병합합니다. 비교 1회 = 두 런의 맨 앞 원소끼리 비교 1번. 한쪽 런이 바닥나면 나머지는 비교 없이 복사합니다.

라운드	결과	비교 횟수
1 (1+1 → 2)	[3, 6] [1, 8] [2, 7] [4, 5]	1 + 1 + 1 + 1 = 4
2 (2+2 → 4)	[1, 3, 6, 8] [2, 4, 5, 7]	3 + 3 = 6
3 (4+4 → 8)	[1, 2, 3, 4, 5, 6, 7, 8]	7

합계 비교 17회. 라운드 수는 log₂ 8 = 3이고, 각 라운드마다 8개 원소를 모두 옮기므로 전체 작업량이 n log n 차수가 됩니다. 병합 결과를 담을 별도 배열이 필요하므로 보조 공간 O(n)입니다.

8. 오리지널 연습문제 4문항

아래 4문항은 모두 이 글을 위해 독자적으로 작성한 오리지널 문제이며, 기출문제를 사용하지 않았습니다. 선택지 기호는 IPA 시험 형식을 따라 ア・イ・ウ・エ를 씁니다.

문제 1 (자료구조 선택)

원소 수 n이 크고, 다음 두 연산이 모두 자주 실행된다. 각 연산의 최악 시간 복잡도가 모두 O(log n) 이하가 되도록 하고 싶다. 배열을 쓰는 경우 용량은 미리 충분히 확보되어 있어 재할당은 일어나지 않는다고 한다.

새 원소(우선순위 값 포함)를 추가한다.
현재 우선순위가 가장 높은 원소를 꺼낸다.

가장 적절한 자료구조는 어느 것인가?

ア 정렬하지 않은 배열 (끝에 추가)
イ 우선순위 내림차순으로 정렬해 둔 단방향 연결 리스트
ウ 이진 힙 (최대 힙)
エ 큐 (FIFO)

정답: ウ

풀이:

ア: 추가는 끝에 넣으므로 O(1)이지만, 최댓값을 꺼내려면 전체를 훑어야 해 O(n). 조건 불충족.
イ: 꺼내기는 머리 노드를 떼므로 O(1)이지만, 추가할 때 알맞은 위치를 찾아 링크를 따라가야 해 최악 O(n). 조건 불충족.
ウ: 추가는 끝에 넣고 위로 올리며(최대 높이 ⌊log₂ n⌋) O(log n), 꺼내기는 루트를 빼고 아래로 재구성하며 O(log n). 두 연산 모두 조건 충족. 정답.
エ: FIFO라서 꺼내는 것은 “가장 먼저 들어온 원소”이지 우선순위가 가장 높은 원소가 아닙니다. 우선순위로 고르려면 전체를 훑어야 해 O(n). 조건 불충족.

문제 2 (스택·큐 상태 변화)

빈 스택 S와 빈 큐 Q가 있다. 다음 연산을 순서대로 실행한다.

S에 push 1
S에 push 2
S에 push 3
S에서 pop한 값을 Q에 enqueue
S에서 pop한 값을 Q에 enqueue
S에 push 4
S에서 pop한 값을 Q에 enqueue

그 후 Q가 빌 때까지 dequeue를 반복한다. 꺼내지는 값의 순서는 어느 것인가?

ア 4, 2, 3
イ 3, 2, 4
ウ 1, 2, 3
エ 3, 2, 1

정답: イ

풀이 (상태 추적):

단계	S (오른쪽이 top)	Q (왼쪽이 front)
1~3	[1, 2, 3]	[ ]
4	[1, 2] (3을 pop)	[3]
5	[1] (2를 pop)	[3, 2]
6	[1, 4]	[3, 2]
7	[1] (4를 pop)	[3, 2, 4]

Q에서 dequeue하면 들어간 순서대로 3, 2, 4. S에는 1이 남습니다.

ア 4, 2, 3: Q를 LIFO처럼 마지막에 넣은 것부터 꺼낸 오답.
イ 3, 2, 4: 위 추적 결과와 일치. 정답.
ウ 1, 2, 3: S를 FIFO처럼 처리한 오답. (그렇게 하면 4·5단계에서 1, 2를 꺼내고, 6단계 후 S = [3, 4]에서 7단계에 3을 꺼내 Q = [1, 2, 3]이 됩니다.)
エ 3, 2, 1: 6단계의 push 4를 무시하거나 7단계 뒤에 실행한 것으로 착각해, 7단계에서 1을 꺼낸 오답.

문제 3 (이진 탐색의 조건과 비교 횟수)

다음 배열 B(인덱스 0~14, n = 15)에서 51을 이진 탐색한다. 규칙은 5.3절과 같다(mid = ⌊(low + high) / 2⌋, A[mid]와의 3방향 판정 1번을 1회로 셈).

인덱스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
값	4	9	13	18	22	27	31	36	40	45	51	56	62	68	75

비교 횟수와 이진 탐색의 적용 조건을 모두 올바르게 나타낸 것은 어느 것인가?

ア 3회. 데이터가 정렬되어 있기만 하면 연결 리스트에서도 같은 효율로 적용할 수 있다.
イ 4회. 데이터가 정렬되어 있지 않은 배열에도 적용할 수 있다.
ウ 11회. 데이터가 정렬되어 있어야 한다.
エ 4회. 데이터가 정렬되어 있고, 중앙 위치에 직접 접근할 수 있어야 한다.

정답: エ

풀이 (추적):

프로브	low	high	mid	B[mid]	판정
1	0	14	7	36	36 < 51 → low = 8
2	8	14	11	56	56 > 51 → high = 10
3	8	10	9	45	45 < 51 → low = 10
4	10	10	10	51	발견

→ 4회. (n = 15의 최대 프로브 수 ⌊log₂ 15⌋ + 1 = 4와도 일치.)

ア: 횟수가 틀림(⌊log₂ 15⌋ = 3을 횟수로 착각한 값). 또한 연결 리스트는 중앙 노드에 O(1)로 접근할 수 없어 접근 비용이 O(n)이 되므로 “같은 효율”이 아닙니다.
イ: 횟수는 맞지만, 정렬되지 않은 배열에서는 “절반을 버리는” 판단이 성립하지 않아 이진 탐색을 쓸 수 없습니다.
ウ: 11회는 선형 탐색으로 인덱스 10에 도달할 때의 비교 횟수(4, 9, …, 51의 11개)입니다. 이진 탐색의 횟수가 아닙니다.
エ: 횟수 4회와 두 조건(정렬, 직접 접근)이 모두 올바름. 정답.

문제 4 (정렬의 동작·복잡도·안정성)

정렬 알고리즘에 관한 설명으로 올바른 것은 어느 것인가?

ア 표준적인 구현의 삽입 정렬은, 이미 오름차순으로 정렬된 n개의 데이터를 오름차순으로 정렬할 때 키 비교가 n − 1회이며, 안정 정렬이다.
イ 퀵 정렬은 피벗을 어떻게 고르든 최악 시간 복잡도가 O(n log n)이다.
ウ 선택 정렬은 이미 정렬된 데이터에 대해 O(n)으로 끝난다.
エ 힙 정렬은 안정 정렬이며, 입력과 같은 크기의 보조 배열(O(n))을 필요로 한다.

정답: ア