알고리즘 — 2025년도 국가공무원 7급 공채 제2차 필기시험

1번

알고리즘의 조건에 대한 설명으로 옳지 않은 것은?

2번

점근 표기법에 대한 설명으로 옳은 것은?

3번

다음 그림과 같은 최대 힙(max heap)을 이용하여 힙 정렬을 수행할 때, 최댓값 9가 배열의 마지막 요소인 4와 교환된 다음, 힙 구조 유지를 위한 연산이 완료된 상태에서의 배열 내용으로 옳은 것은?

4번

다음은 초기상태 배열을 오름차순으로 정렬하는 단계들이다. 이와 같이 정렬을 수행하는 알고리즘으로 옳은 것은?

5번

다음 중위 표기법 수식을 후위 표기법 수식으로 옳게 변환한 것은?

6번

그림과 같이 연결되어 있는 11개의 여행지를 관광객들이 모두 방문할 수 있도록 안내하기 위해 C언어로 구현한 Course() 함수를 다음과 같이 제시하고 있다. 여행지 H를 파라미터로 하여 알고리즘을 호출했을 때, 출력결과의 (가) ～ (라)에 들어갈 내용을 바르게 연결한 것은? (단, 상위 노드 기준으로 n->left는 왼쪽으로 순회하고 n->right는 오른쪽으로 순회한다)

(가) (나) (다) (라)

7번

다음 데이터를 순서대로 삽입하여 불균형이 발생했을 때 회전 연산을 수행하여 균형 상태를 유지하는 AVL 트리를 구성하였다. 구성된 AVL 트리에서 단말 노드(leaf node)에 해당하는 값만을 모두 고르면?

8번

그림과 같은 그래프를 대상으로 다음 알고리즘을 적용하였을 때, 결과에 대한 설명으로 옳지 않은 것은? (단, 탐색의 시작 정점은 1이고, Q는 큐 객체이며, Q.enqueue()와 Q.dequeue()는 큐 Q에 대한 삽입과 삭제 연산이고, 각 정점의 방문을 표시하는 것은 visited[] 배열을 이용한다)

9번

다음 C언어 함수 ABC()에 대한 설명으로 옳은 것은?

10번

다음 자료를 차수가 3인 B－트리에 순서대로 삽입하여 그림과 같은 B－트리를 생성하였을 때, (가) ～ (다)에 들어갈 값을 바르게 연결한 것은?

(가) (나) (다)

11번

다음은 재귀 호출을 이용하여 피보나치(Fibonacci) 수열값을 찾는 파이썬 코드이다. 이 코드의 시간 복잡도는? (단, n은 0 이상의 정수이다)

12번

분할 정복(divide-and-conquer) 방식의 정렬 알고리즘에 대한 설명으로 옳지 않은 것은?

13번

배열로 운영하는 원형 큐에 대해 다음과 같이 연산 1에서 7까지의 연산을 차례로 수행했을 때, 수행이 완료된 후 큐의 상태로 옳은 것은? (단, 현재 상태에서 front ＝ 0, rear ＝ 2이다)

14번

다음 그래프를 대상으로 크루스칼(Kruskal) 알고리즘을 적용하여 최소 신장 트리(MST, Minimum Spanning Tree)를 구성하고자 할 때, 생성되는 MST에 5번째 추가되는 간선과 비용을 바르게 연결한 것은?

간선 비용

15번

문자열 매칭을 위한 알고리즘으로 옳은 것은?

16번

다음은 단일 출발점 최단 경로를 찾기 위한 다익스트라(Dijkstra) 알고리즘을 의사(pseudo) 코드로 기술한 것이다. 이 코드에서 (가)에 들어갈 내용으로 옳은 것은?

17번

KMP(Knuth-Morris-Pratt) 알고리즘과 보이어－무어(Boyer-Moore) 알고리즘에 대한 설명으로 옳지 않은 것은?

18번

다음 조건에 따라 주어진 그래프에 대해 깊이 우선 탐색(DFS, Depth First Search) 방법을 이용하여 트리를 만들 경우, 나올 수 있는 트리의 개수와 수행하는 백트래킹 횟수를 바르게 연결한 것은?

트리의 개수 백트래킹 횟수

19번

다음은 n개의 데이터에 대한 평균을 재귀적으로 계산하는 프로그램이다. (가) ～ (다)에 들어갈 내용을 바르게 연결한 것은? (단, n ≥ 1이다)

(가) (나) (다)

20번

작업 선택 문제를 다루는 다음 알고리즘은 각 작업의 시작 시간 s와 완료 시간 f가 정해진 $n$ 개의 작업 t[0..n-1]가 주어질 때, 하나의 기계만 사용하여 충돌 없이 수행할 수 있는 최대 개수의 작업을 선택한다. 이 알고리즘의 (가), (나)에 들어갈 내용을 바르게 연결한 것은? (단, n ≥ 2인 정수, count는 선택한 작업의 개수, t[i].s는 작업 t[i]의 시작 시간, t[i].f는 작업 t[i]의 종료 시간이고, jobs 배열은 선택된 작업을 저장한다)

(가) (나)

21번

동적 프로그래밍(dynamic programming) 방법으로 최소의 원소단위 곱셈 횟수를 갖도록 연쇄 행렬곱셈(matrix-chain multiplication)의 순서를 정하려 한다. $c_{i}, j$ 를 행렬 $M_{i}$ 부터 $M_{j}$ 까지의 연쇄 행렬곱셈의 최소 비용이라고 할 때, $c_{i}, j$ 에 대한 관계식으로 옳은 것은? (단, $i < j$ 이고, 각 행렬의 차원이 $p_{0}, p_{1}, . . ., p_{n}$ 일 때, 행렬 $M_{i}$ 의 크기는 $p_{i - 1} \times p_{i}$ 이다)

22번

동적 프로그래밍은 한 번 계산된 값을 메모리에 저장한 후, 저장된 값을 필요할 때마다 가져다 쓰는 방법이다. 동적 프로그래밍을 적용하여 구현한 다음 Java 프로그램에서 피보나치 수열 fibo(6)을 구하기 위해 저장되어 있는 fibo(3)의 결과를 가져다 쓰는 횟수는?

23번

배낭 문제(knapsack problem)에 대한 설명으로 옳은 것은?

24번

알고리즘들에 대한 설명으로 옳지 않은 것은?

25번

다음 설명에 해당하는 알고리즘은?