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

컴퓨터 알고리즘(algorithm)의 특성에 대한 설명으로 옳지 않은 것은?

다음 피보나치 수열의 n번째 항을 계산하는 알고리즘에 대한 설명으로 옳지 않은 것은? (단, $\mathrm{n}\ge 0$이다)

int fib(n) {
   if (n == 0)
	return 0;
   if (n == 1) 
	return 1;
   return fib(n – 1) + fib(n – 2);
}

문제 해결을 위한 알고리즘을 기술하는 방법이 아닌 것은?

다음 (가) 트리(tree)를 깊이 우선 탐색(DFS, Depth First Search) 알고리즘으로 방문한 순서가 (나)와 같을 때, ㉠ ～ ㉢에 들어갈 노드는?

(가)

(나) a → b → c → d → e → f → g → h → i → j → k → l → m

㉠ ㉡ ㉢

1부터 n까지의 합을 계산하는 다음 알고리즘의 빈칸에 들어갈 코드는? (단, $\mathrm{n}\ge 1$인 정수이다)

힙(heap)에 대한 설명으로 옳지 않은 것은? (단, $n$은 데이터의 개수이다)

병합(merge) 정렬과 퀵(quick) 정렬에 대한 설명으로 옳지 않은 것은?

다음 버블(bubble) 정렬 알고리즘 (가)에 대한 입력 배열이 (나)일 때, 해당 알고리즘에서 데이터 교환(swap 함수 실행) 직후 (다) 배열 상태에서의 end와 cur의 값은?

(가)  bubble_sort(arr[], arr_size) { 
// arr 배열의 인덱스는 0 ～ arr_size-1
   for end ← arr_size - 1 to 1
      for cur ← 0 to end - 1
         if (arr[cur] > arr[cur + 1])
            swap(arr[cur], arr[cur + 1]);
}
(나)  6, 2, 3, 4, 0, 5, 1, 9, 8, 7
(다)  2, 3, 0, 4, 5, 1, 6, 8, 7, 9

end cur

다음 알고리즘에 해당하는 정렬은?

sort(arr[], n){ // arr 배열의 인덱스는 0 ～ n-1
   for i ← 1 to n - 1 {
      cur ← arr[i];
      j ← i – 1;
      while (j ≧ 0) and (arr[j] > cur) {
         arr[j + 1] ← arr[j];
         j ← j – 1;
      }
      arr[j + 1] ← cur;
   }
}

문제 부류(class)간 포함관계로 옳은 것은? (단, $\mathrm{P}\ne \mathrm{NP}$일 경우이다)

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

○ 문제의 입력 사례 분할 후, 분할된 문제의 해답을 우선 구한다.

○ 문제의 입력 사례를 분할할 때, 재귀 관계식을 사용할 수 있다.

○ 분할된 문제의 해답을 저장하여 분할 전 문제의 해답을 구하는 상향식 방법이다.

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

다음 알고리즘에 대한 시간 복잡도는?

sum ← 0;
for j ← 1 to n
   for i ← 1 to j
      sum ← sum + 1;
for k ← 0 to n - 1
   sum ← sum + k;

$a^x$을 계산하는 다음 알고리즘의 빈칸 ㉠ ～ ㉢에 해당하는 코드로 옳게 짝지어진 것은? (단, $a$와 $x$는 정수, $x\ge 0$, mod는 나머지 연산이다)

int power(a, x) {
   if (x == 1) 
      return ㉠;
   else if (x == 0)
      return 1;
   if (x mod 2 == 0) {
      temp ← power(a, x / 2);
      return ㉡;
   } else {
      temp ← power(a, (x – 1) / 2);
      return ㉢ ;
   }
}

㉠ ㉡ ㉢

정렬된 정수 배열을 입력으로 하는 이진 탐색 알고리즘에 대한 시간 복잡도는?

다음 설명에 해당하는 복잡도 함수에 대한 시간 복잡도는?

○ $T(1)=27$

○ $T(n)$은 궁극적으로 감소하지 않는다.

○ $T(n)=9T(\frac{n}{3})+8n$ ($n>1$이고, $n$은 3의 거듭제곱이다)

다음 수식들에 대해 ㉠ ～ ㉢에 해당하는 빅오($O$) 표기가 옳게 짝지어진 것은? (단, $k$는 상수이다)

㉠ ㉡ ㉢

다음 문제를 해결하기 위한 알고리즘 관련 설명으로 옳은 것은?

○ $n$개의 물건은 각기 고유의 무게와 가치를 갖는다.

○ 물건은 나눌 수 없으며, 선택한 물건은 통째로 넣는다.

○ 배낭 내 물건들의 총 무게는 배낭 용량을 초과할 수 없다.

○ 최대의 가치를 갖도록 한정된 용량의 배낭에 물건을 넣는다.

각 정렬 알고리즘에 대한 사례별 시간 복잡도가 옳게 짝지어진 것은?

최선의 경우 최악의 경우

다음 그래프에 대해 크루스칼(Kruskal) 알고리즘에 의한 최소 신장 트리(MST, Minimum Spanning Tree)를 계산할 때, 5번째로 MST에 포함되는 간선은? (단, 초기의 MST는 ∅이다)

다음 방향 그래프의 a 노드에서 각 노드별 최단 경로를 다익스트라(Dijkstra) 알고리즘으로 계산할 때, 각 노드별 최단 거리 갱신 횟수로 옳은 것은? (단, a 노드를 제외한 모든 노드의 최단 경로 초기값은 ∞이다)

하노이탑 문제를 해결하기 위한 다음 알고리즘의 빈칸 ㉠, ㉡에 들어갈 코드가 옳게 짝지어진 것은? (단, n은 원판의 개수이다)

hanoi(n, from, temp, to){
   if (n == 1) 
      move(from, to); // from에서 to로 이동
   if (1 < n){
	hanoi(n – 1, ㉠);
	move(from, to); // from에서 to로 이동
	hanoi(n – 1, ㉡);
   }
}

㉠ ㉡

라빈－카프(Rabin-Karp) 알고리즘에 대한 설명으로 옳지 않은 것은? (단, 패턴 문자열의 길이는 $m$, 대상 문자열의 길이는 $n$, $m\le n$이다)

KMP(Knuth-Morris-Pratt) 알고리즘에 대한 설명으로 옳지 않은 것은? (단, 패턴 문자열의 길이는 $m$, 대상 문자열의 길이는 $n$, $m\le n$이다)

다음 문자와 빈도수에 대해 허프만(Huffman) 알고리즘을 이용하여 트리를 구성했을 때, 빈칸 ㉠ ～ ㉣에 들어갈 문자는? (단, ○는 빈도수 노드, □는 문자 노드이다)

㉠ ㉡ ㉢ ㉣