7급 국가직 알고리즘 2025년 기출문제

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

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

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

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

초기상태: [69, 10, 30, 3, 16, 8]

step 1: [3, 10, 30, 69, 16, 8]

step 2: [3, 8, 30, 69, 16, 10]

step 3: [3, 8, 10, 69, 16, 30]

step 4: [3, 8, 10, 16, 69, 30]

step 5: [3, 8, 10, 16, 30, 69]

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

(A * B) － (C / D) － E

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

typedef struct node {
	char name;
	struct node *left;
	struct node *right;
} node;

void Course(node *n) {
	if(n != null) {
		Course(n->left);
		Course(n->right);
		printf("%c->", n->name);
	}
}

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

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

50, 60, 70, 90, 80, 75, 73, 72, 78

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

_FS(v) {
	visited[v] <- YES;	// 정점 v에 대한 방문 표시
	Q.enqueue(v)
	while(!Q.empty()) {	// Q가 비어있지 않은 동안
		w <- Q.dequeue();
		for all u ∈ (w에 인접한 정점) {
			if(visited[u] != YES) {
				visited[u] <- YES;
				Q.enqueue(u);
			}
		}
	}
}

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

void ABC(int A[], int n) {
	int i, j, tmp;
	for(i = n - 1; i > 0; i--) {
		j = 0;
		while(j < i) {
			if(A[j] < A[j + 1]) {
				tmp = A[j];
				A[j] = A[j + 1];
				A[j + 1] = tmp;
			}
			j = j + 1;
		}
	}
}

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

75, 15, 10, 12, 5, 30, 1, 2, 25, 27, 34, 60

(가) (나) (다)

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

def fib(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	else:
		return fib(n – 1) + fib(n – 2)

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

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

연산 1. 원소 Y 삽입

연산 2. 원소 3개 삭제

연산 3. 원소 Q 삽입

연산 4. 원소 M 삽입

연산 5. 원소 A 삽입

연산 6. 원소 K 삽입

연산 7. 원소 2개 삭제

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

간선 비용

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

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

// 입력: 가중 방향 그래프 G, 인접 행렬 A, 시작 정점 s
// 출력: s로부터 다른 모든 정점까지의 최단 경로의 길이 
Dijkstra(G, A, s) {
	U = {s};
	for(모든 정점 v ∈ G)
		D[v] = A[s][v];
	while(U != G) {
		D[w]가 최소인 정점 w ∈ (G–U)를 선택
		U = U ∪ {w};
		for(w에 인접한 모든 정점 v) {
			D[v] = (가);
		}
	}
}

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

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

○ DFS의 시작 정점은 A로 하고, 정점의 접근 순서는 알파벳 순서로 한다.

○ DFS는 사이클을 형성하지 않으면서 백트래킹을 통해 시작 정점으로 돌아왔을 때, 시작 정점에서 방문하지 않은 접근 가능한 인접 정점이 없으면 종료한다.

○ DFS의 종료시점에 그래프에 방문하지 않은 정점들이 존재하면, 방문하지 않은 정점들 중 알파벳 순서가 가장 앞선 정점을 시작 정점으로 하여 DFS를 다시 시작한다.

○ 그래프 안에 방문하지 않은 정점이 존재하지 않을 때까지 DFS를 반복한다.

트리의 개수 백트래킹 횟수

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

float AVG(float (가), int n) {
	if(n == 1) return (나);
		else
			return (data[n - 1] + (n - 1) * AVG(data, n - 1)) / (다);
}

(가) (나) (다)

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

ActSelect(n, t[]) {
	(가)의 오름차순으로 작업 t[]를 정렬;
	count = 0, last = 0, jobs[];
	jobs[count] = 0;
	for(i = 0; i < n; i++)
		if((나)) {
			count++;
			last = i;
			jobs[count] = last;
		}
	return jobs;
}

(가) (나)

동적 프로그래밍(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$이다)

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

public class Fibonacci {
	static int[] dp = new int[100];

	public static void main(String[] args) {
		System.out.println(fibo(6));
	}

	public static int fibo(int num) {
		if(num == 0) {
			return 0;
		}
		if(num == 1) {
			return 1;
		}
		if(dp[num] != 0) {
			return dp[num];
		}
		return dp[num] = fibo(num - 1) + fibo(num - 2);
	}
}

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

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

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

○ 주어진 문제에 대해 근사해나 일정 확률 이상의 최적해를 출력함

○ 근사해나 간혹 틀린 해를 허용할 수 있는 경우에 사용 가능함

○ 효율적인 결정론적 알고리즘이 밝혀져 있지 않은 문제에 효과적임