다음 중 입력 크기 n이 커질수록 성장하는 속도가 느린 것부터 빠른 순서로 옳게 나열한 것은?

이진 탐색의 점화식 T(n) = T(n/2) + O(1)을 반복 대입법으로 전개해 시간 복잡도를 유도하는 과정으로 옳은 것은?

어떤 배열에서 특정 값을 순차 탐색(sequential search)으로 찾을 때 최악의 경우와 평균적인 경우에 대한 설명으로 옳은 것은?

배열 [29, 10, 14, 37, 13]을 선택 정렬(selection sort)로 오름차순 정렬한다고 하자. 매 패스마다 아직 정렬되지 않은 구간에서 최솟값을 찾아 그 구간의 맨 앞과 교환한다. 1패스와 2패스가 끝난 직후의 배열 상태로 옳은 것은?

삽입 정렬(insertion sort)이 안정 정렬(stable sort)인 이유로 옳은 것은?

배열 [8, 3, 7, 4, 9, 2, 5]에 대해 마지막 원소(5)를 피벗으로 삼는 로무토(Lomuto) 방식의 퀵 정렬 파티션을 한 번 수행한다고 하자. 왼쪽부터 훑으며 피벗보다 작거나 같은 원소를 만날 때마다 경계 인덱스를 하나씩 늘리며 그 위치와 교환하고, 마지막에 피벗을 경계 다음 위치로 옮긴다. 파티션이 끝난 직후의 배열과 피벗의 최종 위치로 옳은 것은?

병합 정렬(merge sort)과 퀵 정렬(quick sort)의 비교로 옳지 않은 것은?

크기 5인 최대 힙(max heap)을 배열 [4, 10, 3, 5, 1](완전 이진 트리로 해석: 인덱스0이 루트, 인덱스 i의 자식은 2i+1, 2i+2)에서 상향식(bottom-up) 힙 구성으로 만든다고 하자. 마지막 내부 노드(인덱스1)부터 시작해 루트(인덱스0)까지 heapify를 적용할 때, 최종적으로 완성되는 최대 힙 배열로 옳은 것은?

기수 정렬(radix sort)에 대한 설명으로 옳은 것은?

정렬된 배열 [3, 7, 12, 18, 24, 31, 45, 52, 68](인덱스 0~8)에서 이진 탐색으로 값 31을 찾는다고 하자. low=0, high=8로 시작해 mid = (low+high)/2(내림)로 계산하며 진행할 때, 값을 찾기까지 필요한 비교 횟수와 그 과정으로 옳은 것은?

해시 테이블의 크기가 7이고 해시 함수가 h(k) = k mod 7이라 하자. 키 10, 15, 3, 22, 9를 이 순서대로 체이닝(chaining) 방식으로 삽입할 때, 충돌이 발생하는 키의 쌍과 그 이유로 옳은 것은?

무방향 그래프의 정점이 A, B, C, D, E, F이고 간선이 A–B, B–C, D–E뿐이라고 하자(F는 어떤 간선에도 연결되지 않은 고립 정점). 이 그래프의 연결 요소(connected component) 개수로 옳은 것은?

정점이 1, 2, 3, 4이고 간선(방향)이 1→2, 1→3, 2→4, 3→4인 방향 비순환 그래프(DAG)가 있다고 하자. Kahn 알고리즘(진입 차수가 0인 정점부터 차례로 제거)으로 위상 정렬을 수행할 때 나올 수 있는 결과로 옳은 것은?

무방향 가중치 그래프에서 정점 A, B, C, D와 간선 A–B(3), A–C(1), B–C(2), B–D(4), C–D(5)가 주어졌을 때, 최소 신장 트리(MST)의 총 가중치로 옳은 것은?

방향 가중치 그래프에서 정점 S, A, B, C와 간선 S→A(2), S→B(5), A→B(1), A→C(4), B→C(1)이 주어졌을 때, 다익스트라 알고리즘으로 S에서 각 정점까지의 최단 거리를 구하면?

벨만-포드 알고리즘이 다익스트라와 달리 가지는 특징으로 옳은 것은?

플로이드-워셜 알고리즘에 대한 설명으로 옳지 않은 것은?

텍스트 'ABABABC'에서 패턴 'ABABC'를 나이브(단순) 문자열 검색으로 찾는다고 하자. 나이브 검색의 시간 복잡도와 그 이유로 옳은 것은?

KMP(Knuth-Morris-Pratt) 알고리즘이 나이브 검색보다 효율적인 이유로 옳은 것은?

점화식 T(n) = 2T(n/2) + n^2(부분 문제 2개, 결합 비용 n^2)을 마스터 정리로 분석한다고 하자. a=2, b=2이므로 n^(log_b a) = n^(log_2 2) = n^1 = n이다. f(n) = n^2을 n과 비교했을 때의 결론으로 옳은 것은?

배낭 용량 7, 물건이 (무게3, 가치5), (무게4, 가치6), (무게5, 가치10)인 0/1 배낭 문제를 생각하자. 가치 대 무게 비율은 각각 약 1.67, 1.5, 2.0이다. '비율이 높은 물건부터 배낭에 넣을 수 있는 만큼 넣는' 탐욕 전략을 적용하면 물건3(무게5, 가치10)을 먼저 넣고 남은 용량 2에는 남은 물건이 들어갈 수 없어 총 가치 10을 얻는다. 반면 동적계획법으로 정확히 계산하면 물건1과 물건2를 함께 넣어(무게 3+4=7, 가치 5+6=11) 총 가치 11을 얻을 수 있다. 이 결과가 보여 주는 것으로 옳은 것은?

백트래킹으로 순열을 생성하는 문제에서, 원소 1, 2, 3의 모든 순열을 만드는 과정 중 '1을 고정하고 2를 다음에 놓은 뒤, 남은 원소는 3 하나뿐이므로 3을 놓아 순열 (1, 2, 3)을 완성한다. 그다음 마지막 자리(3)에서 더 시도할 다른 원소가 없으므로 되돌아가 두 번째 자리를 3으로 바꿔 순열 (1, 3, 2)를 만든다'는 과정에서 나타나는 백트래킹의 핵심 동작으로 옳은 것은?

정점 커버 문제(vertex cover problem, 그래프의 모든 간선이 적어도 하나의 끝점을 포함하도록 정점 집합을 고르되 그 크기가 목표 K 이하인지 판별)의 계산 복잡도 분류에 대한 설명으로 옳은 것은?

실전 시험에서 여러 알고리즘 개념이 섞여 나올 때, '이 문제는 어떤 알고리즘·설계 기법으로 접근해야 하는가'를 판단하는 절차로 가장 적절한 것은?