Skip to Content
독학사독학사 4단계알고리즘19. 예상·기출 변형: 정렬·탐색 파트

이 문서의 문항은 실제 기출 문제를 그대로 복제한 것이 아니라, 국가평생교육진흥원이 공개한 독학사 4단계 알고리즘 과목 출제기준(평가영역)을 근거로 새로 재구성한 예상·유사 문항이다. 실제 시험의 문항 수·배점·난이도 분포는 회차별 공고를 통해 별도로 확인해야 한다.

왜 이 편이 필요한가

06~10편에서 각 정렬·탐색 알고리즘을 개별적으로 깊이 다뤘다면, 이 편은 그 내용을 시험 문항 형태로 다시 확인하는 편이다. 특히 “안정성·제자리 여부·복잡도를 표로 비교하는 문제”, “의사코드나 배열 상태를 보고 몇 번째 패스인지 추적하는 문제”, “정렬 방법을 바꾸면 결과가 달라지는 함정 문제”에 익숙해지는 것이 목표다. 각 문항의 해설에는 계산 과정을 전 단계 생략 없이 적었으므로, 정답을 확인한 뒤 반드시 해설의 계산 과정을 스스로 다시 손으로 짚어 보길 권한다.

마무리 복습

문제 14지선다
배열 [5, 2, 4, 1, 3]에 선택 정렬을 적용할 때, 1회전(첫 번째 패스)이 끝난 직후의 배열 상태로 옳은 것은?
문제 24지선다
배열 [4, 3, 2, 1]에 버블 정렬을 적용할 때, 안쪽 반복을 한 번 끝까지 수행한 1회전 직후의 배열 상태로 옳은 것은?
문제 34지선다
배열 [8, 4, 6, 2]에 삽입 정렬을 적용할 때, 인덱스 2(값 6)까지 삽입을 마친 직후의 배열 상태로 옳은 것은?
문제 44지선다
퀵 정렬에서 배열 [6, 1, 8, 3, 5]의 맨 오른쪽 원소(5)를 피벗으로 삼아 한 번의 파티션을 수행했을 때, 파티션이 끝난 직후 피벗 5가 놓이는 최종 인덱스로 옳은 것은?
문제 54지선다
병합 정렬로 배열 [5, 3, 8, 1]을 정렬할 때, 분할이 끝나 크기 1인 부분 배열들로 나뉜 뒤 처음 병합되는 두 쌍으로 옳은 것은?
문제 64지선다
최소 힙으로 힙 정렬을 수행하면 안 되고 반드시 최대 힙을 사용해야 하는 이유로 가장 적절한 것은?
문제 74지선다
크기가 5인 배열에 대해 힙 정렬을 위한 최대 힙을 구성하는 과정(build-heap)의 시간복잡도로 가장 적절한 것은?
문제 84지선다
키 값이 [170, 45, 75, 90] 인 배열에 기수 정렬(radix sort)을 적용할 때, 1의 자리를 기준으로 한 번째 자릿수 정렬을 마친 직후의 배열 순서로 옳은 것은?
문제 94지선다
기수 정렬이 비교 기반 정렬의 하한인 O(n log n)보다 빠른 O(d(n+k))로 동작할 수 있는 근본적인 이유로 가장 적절한 것은?
문제 104지선다
다음 중 정렬 알고리즘과 최악의 경우 시간복잡도의 짝으로 옳지 않은 것은?
문제 114지선다
정렬 알고리즘 중 안정 정렬(stable sort)에 해당하지 않는 것은?
문제 124지선다
제자리(in-place) 정렬에 대한 설명으로 옳은 것은?
문제 134지선다
정렬된 배열 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]에서 이진 탐색으로 값 23을 찾을 때, 첫 번째로 비교하는 원소의 값으로 옳은 것은?
문제 144지선다
크기 100인 정렬된 배열에서 이진 탐색으로 특정 값을 찾을 때, 최악의 경우 필요한 비교 횟수의 상한으로 가장 적절한 것은?
문제 154지선다
이진 탐색을 적용하기 위한 전제 조건으로 가장 적절한 것은?
문제 164지선다
해시 테이블에서 체이닝(chaining)으로 충돌을 해결할 때에 대한 설명으로 옳은 것은?
문제 174지선다
해시 테이블에서 개방 주소법(open addressing) 중 선형 조사(linear probing)에 대한 설명으로 옳은 것은?
문제 184지선다
적재율(load factor, 저장된 원소 수를 테이블 크기로 나눈 값)이 1에 매우 가까워질 때 개방 주소법 해시 테이블에서 발생하는 문제로 가장 적절한 것은?
문제 194지선다
크기 100만인 정렬되지 않은 배열에서 특정 값 하나를 딱 한 번만 찾아야 할 때, 미리 정렬한 뒤 이진 탐색을 쓰는 것보다 순차 탐색이 더 적절할 수 있는 이유로 가장 적절한 것은?
문제 204지선다
다음 중 평균 시간복잡도가 O(1)에 가장 가까운 탐색 방법은?
문제 214지선다
퀵 정렬과 병합 정렬 모두 분할정복 기법을 사용하지만 실제 동작 방식에는 차이가 있다. 이에 대한 설명으로 옳지 않은 것은?
문제 224지선다
배열 [3, 7, 1, 9, 5]를 삽입 정렬로 정렬하는 과정에서, 값 1을 삽입하기 위해 비교·이동해야 하는 원소의 개수로 옳은 것은? (1은 인덱스 2에 위치하며, 왼쪽의 이미 정렬된 부분은 [3, 7]이다)

참고 자료

Last updated on
18. 혼합 알고리즘 문제 유형: 정렬·그래프·DP 결합20. 예상·기출 변형: 그래프·최단경로·MST