7급 국가직 알고리즘 기출문제 전 회차를 한 권으로 — PDF 전자책(문제집·정답해설집)

23년 1회차

총 25문항 · 객관식 · A4 약 1장

1 / 1

A4정답 포함← → 키 · 드래그로 넘김

7급 국가직 알고리즘 기출문제모두CBT · moducbt.com

23년 1회차

총 25문항 · 객관식 · 정답·해설 포함

문제 1

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

1알고리즘은 1개 이상의 결과(output)를 생성해야 한다.

2알고리즘에는 반드시 입력(input)이 1개 이상 존재해야 한다.

3알고리즘은 한정된 횟수의 단계 실행 후 반드시 종료해야 한다.

4알고리즘의 각 명령은 모호하지 않고 명확해야 한다.

정답 및 해설

알고리즘의 입력은 0개 이상이면 되므로, 입력이 반드시 1개 이상 존재해야 한다는 설명이 옳지 않다.

알고리즘의 조건은 입력(0개 이상), 출력(1개 이상), 명확성, 유한성, 효과성이다. 난수 생성처럼 외부 입력 없이도 결과를 내는 알고리즘이 있다.

1개 이상의 결과를 생성해야 한다는 것은 출력 조건으로 옳다.
한정된 단계 실행 후 반드시 종료해야 한다는 것은 유한성으로 옳다.
각 명령이 모호하지 않고 명확해야 한다는 것은 명확성으로 옳다.

문제 2

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

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

1fib(7) 호출 시, fib(3)은 5번 호출된다.

2알고리즘의 시간 복잡도는

O(\log_2(n))

이다.

3알고리즘의 점화식은

F_n = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ F_{n-1} + F_{n-2}, & n \gt 1 \end{cases}

이다.

4반복문을 사용하여 알고리즘 성능을 개선할 수 있다.

정답 및 해설

재귀 피보나치는 호출이 지수적으로 늘어나므로 시간 복잡도가 $O(\log_2(n))$ 라는 설명이 옳지 않다.

fib(n)은 fib(n-1)과 fib(n-2)를 모두 다시 호출해 같은 값을 중복 계산하므로, 호출 횟수가 피보나치 수에 비례해 늘어나는 지수 시간( $O(2^n)$ 상한)이 된다.

fib(4)·fib(5)·fib(6)·fib(7)을 호출할 때 fib(3)의 호출 횟수는 1, 2, 3, 5회로 피보나치 수열처럼 늘어 fib(7)에서 5회가 맞다.
제시된 점화식은 코드의 두 기저 조건과 재귀 호출을 그대로 옮긴 것으로 옳다.
반복문으로 직전 두 항만 유지하며 계산하면 $O(n)$ 으로 성능이 개선된다.

문제 3

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

1순서도(flowchart)를 사용하여 도식화한다.

2의사 코드(pseudo code)를 사용하여 기술한다.

3추상 데이터 타입(abstract data type)만으로 기술한다.

4단계별로 명확한 문장(자연어)으로 기술한다.

정답 및 해설

추상 데이터 타입은 자료와 연산의 명세일 뿐 처리 절차를 나타내지 않으므로, 추상 데이터 타입만으로 기술하는 것은 알고리즘 기술 방법이 아니다.

알고리즘은 문제를 푸는 단계적 절차이므로 자연어, 순서도, 의사 코드, 프로그래밍 언어처럼 실행 순서를 표현할 수 있는 수단으로 기술한다.

순서도는 처리 흐름을 도형으로 나타내는 기술 방법이다.
의사 코드는 특정 언어에 얽매이지 않고 절차를 표현하는 대표적 기술 방법이다.
자연어 기술도 단계가 명확하면 알고리즘 기술 방법이 된다.

문제 4

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

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

㉠㉡㉢

1e / g / c

2e / h / i

3k / g / i

4k / h / c

정답 및 해설

DFS 방문 순서를 트리에 대입하면 ㉠은 e, ㉡은 h, ㉢은 i이다.

깊이 우선 탐색의 방문 순서는 전위 순회 순서와 같다. a의 왼쪽 자식 b 아래에서 c와 그 자식 d, 둘째 자식 e(㉠), 셋째 자식 f와 그 자식 g·h(㉡)를 차례로 방문한다.

이어서 a의 오른쪽 자식 i(㉢)와 그 서브트리 j, k, l, m을 방문한다.

e·g·c 조합: f의 두 자식 중 g가 먼저 방문되므로 ㉡ 자리는 h이고, c는 b의 첫 자식이다.
k·g·i 조합: k는 a의 오른쪽 서브트리에 속해 b의 자식 자리에 올 수 없다.
k·h·c 조합: ㉠은 b의 둘째 자식 e이고, ㉢은 오른쪽 서브트리의 루트 i이다.

문제 5

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

int sum(n){
  if (n == 1)
    return 1;
  else
    (          );
}

1return n + sum(n - 1)

2return n - sum(n - 1)

3return n + sum(n + 1)

4return n - sum(n + 1)

정답 및 해설

빈칸에는 return n + sum(n - 1)이 들어간다.

1부터 n까지의 합은 n에 1부터 n-1까지의 합을 더한 값이므로 $S(n)=n+S(n-1)$ 이고, 인자가 1씩 줄어 기저 조건 n == 1에 도달한다.
예: sum(3) = 3 + sum(2) = 3 + 2 + sum(1) = 6

n에서 sum(n - 1)을 빼면 합이 아니라 차가 되어 sum(2)가 1이 되는 등 결과가 틀린다.
n에 sum(n + 1)을 더하면 인자가 커지기만 해 n == 1에 도달하지 못하고 무한 재귀에 빠진다.
n에서 sum(n + 1)을 빼는 경우도 인자가 증가해 종료되지 않는다.

문제 6

힙(heap)에 대한 설명으로 옳지 않은 것은? (단,

n

은 데이터의 개수이다)

1힙을 구성하는 완전 이진 트리는 1차원 배열을 사용하여 구현할 수 있다.

2최대 힙(max heap)의 모든 부모 노드 값은 그들의 자식 노드 값보다 크거나 같다.

3새로운 데이터 삽입 후 힙 성질을 만족하기 위한 연산의 시간 복잡도는

O(n\log_2(n))

이다.

4루트 노드에서 데이터 삭제 후 힙 성질을 만족하기 위한 연산의 시간 복잡도는

O(\log_2(n))

이다.

정답 및 해설

힙에 데이터 하나를 삽입한 뒤 재정비하는 비용은 $O(\log_2(n))$ 이므로 $O(n\log_2(n))$ 라는 설명이 옳지 않다.

새 원소를 마지막 위치에 넣고 부모와 비교·교환하며 올라가는데, 완전 이진 트리의 높이가 $\lfloor \log_2 n \rfloor$ 이므로 교환은 높이만큼만 일어난다.

완전 이진 트리는 빈자리 없이 채워지므로 1차원 배열(부모 i, 자식 2i·2i+1)로 구현할 수 있다.
최대 힙은 모든 부모가 자식보다 크거나 같은 힙 성질을 만족한다.
루트 삭제 후에는 마지막 원소를 루트로 옮겨 아래로 내려가며 재정비하므로 $O(\log_2(n))$ 이다.

문제 7

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

1병합 정렬과 퀵 정렬은 모두 재귀 함수(recursive function)로 구현할 수 있다.

2병합 정렬과 퀵 정렬은 모두 분할 정복(divide-and-conquer) 알고리즘에 속한다.

3퀵 정렬은 병합 정렬과 달리 배열 내 요소 간 데이터를 교환 (swap)하지 않는다.

4퀵 정렬은 입력의 피봇(pivot) 값을, 병합 정렬은 중간 위치를 사용하여 배열을 분할한다.

정답 및 해설

퀵 정렬은 피봇을 기준으로 원소를 좌우로 나누는 과정에서 교환(swap)을 반복하므로, 교환하지 않는다는 설명이 옳지 않다.

오히려 병합 정렬이 교환 대신 보조 배열에 원소를 복사·병합하는 방식이다.

두 정렬은 부분 배열에 자기 자신을 다시 호출하는 재귀 함수로 구현할 수 있다.
두 정렬 모두 분할 → 정복 → 결합의 분할 정복 구조다.
퀵 정렬은 피봇 값에 따라, 병합 정렬은 중간 위치에서 배열을 나눈다.

문제 8

다음 버블(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

18 / 2

28 / 4

37 / 2

47 / 4

정답 및 해설

(다) 상태는 end = 8, cur = 2에서 교환이 일어난 직후다.

end = 9 회차: 6이 오른쪽으로 이동하며 2, 3, 4, 0, 5, 1과 차례로 교환되고, 9가 8, 7과 교환되어 2, 3, 4, 0, 5, 1, 6, 8, 7, 9가 된다.

end = 8 회차: cur = 0(2와 3), cur = 1(3과 4)은 교환이 없고, cur = 2에서 4 > 0이므로 교환해 2, 3, 0, 4, 5, 1, 6, 8, 7, 9, 즉 (다)가 된다.

end = 8, cur = 4는 같은 회차에서 5와 1을 교환하는 시점이라 (다)보다 더 진행된 상태다.
end = 7, cur = 2 시점에는 직전 회차에서 8과 7이 이미 교환되어 끝부분이 7, 8, 9이므로 (다)와 다르다.
end = 7, cur = 4 역시 끝부분이 7, 8, 9로 정리된 뒤라 (다)와 맞지 않는다.

문제 9

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

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;
  }
}

1쉘(shell) 정렬

2기수(radix) 정렬

3선택(selection) 정렬

4삽입(insertion) 정렬

정답 및 해설

제시된 코드는 삽입(insertion) 정렬이다.

i번째 원소를 cur에 두고, 앞쪽의 이미 정렬된 구간에서 cur보다 큰 원소를 한 칸씩 오른쪽으로 밀어낸 뒤 빈자리에 cur을 끼워 넣는 구조다.

쉘 정렬은 일정 간격(gap)으로 떨어진 원소끼리 삽입 정렬을 하고 간격을 줄여 가는데, 이 코드는 간격 없이 인접 원소만 비교한다.
기수 정렬은 자릿수별로 버킷에 분배하는 비교 없는 정렬이지만, 이 코드는 원소끼리 대소를 비교한다.
선택 정렬은 남은 구간의 최솟값을 찾아 교환하는 방식이라, 원소를 밀어 옮기는 이 코드와 다르다.

문제 10

문제 부류(class)간 포함관계로 옳은 것은? (단,

\mathrm{P} \neq \mathrm{NP}

일 경우이다)

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

$\mathrm{P} \neq \mathrm{NP}$ 일 때 옳은 그림은 P가 NP 안에 NP-완전과 겹치지 않게 있고, NP-완전이 NP와 NP-하드의 겹친 영역에 놓인 것이다.

P의 문제는 모두 NP에 속하고, NP-완전은 NP이면서 NP-하드인 문제로 정의된다. P와 NP가 다르면 NP-완전 문제는 다항 시간에 풀 수 없으므로 P는 NP-완전·NP-하드와 겹치지 않는다.

NP 원 안에 NP-완전이 따로 있고 P가 겹친 영역에 놓인 그림: NP-완전을 NP-하드 밖에 두고 P를 NP-하드에 넣었다.
NP-하드 원 안에 NP-완전이 따로 있고 P가 겹친 영역에 놓인 그림: NP-완전을 NP 밖에 두고 P를 NP-하드에 넣었다.
NP-하드 원 안에 P가 있고 NP-완전이 겹친 영역에 놓인 그림: P를 NP 밖에 두어 P가 NP에 포함된다는 사실에 어긋난다.

문제 11

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

○ 문제의 입력 사례 분할 후, 분할된 문제의 해답을 우선 구한다.
○ 문제의 입력 사례를 분할할 때, 재귀 관계식을 사용할 수 있다.
○ 분할된 문제의 해답을 저장하여 분할 전 문제의 해답을 구하는 상향식 방법이다.

1브루트포스(bruteforce)

2백 트랙킹(backtracking)

3분기 한정법(branch-and-bound)

4동적 프로그래밍(dynamic programming)

정답 및 해설

설명은 동적 프로그래밍에 해당한다.

재귀 관계식으로 문제를 작은 부분 문제로 나누고, 작은 문제의 해답을 표에 저장해 두었다가 큰 문제의 해답을 구하는 상향식(bottom-up) 방법이 동적 프로그래밍의 특징이다.

브루트포스는 가능한 모든 경우를 전부 시도하는 방법으로, 부분 문제의 해답을 저장해 재사용하지 않는다.
백트래킹은 상태 공간 트리를 깊이 우선으로 탐색하다 유망하지 않으면 되돌아가는 방법이다.
분기 한정법은 한계값(bound)으로 유망하지 않은 노드를 가지치기하며 최적해를 찾는 방법이다.

문제 12

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

1이진 탐색(binary search)은 분할 정복 알고리즘에 속한다.

2분할 정복에 기반을 둔 알고리즘의 시간 복잡도는 최악의 경우

O(\log_2(n))

이다.

3반복문(iteration)만을 사용하여 큰 문제를 작은 문제들로 분할한다.

n

개의 정수들 중

k

번째로 큰 정수를 찾는 선택(selection) 문제에서 문제의 크기는 재귀적으로 절반씩 분할된다.

정답 및 해설

이진 탐색은 탐색 구간을 절반으로 나눠 한쪽만 재귀적으로 푸는 분할 정복 알고리즘이다.

가운데 원소와 비교해 문제를 크기 절반의 부분 문제 하나로 줄이므로, 분할 정복의 가장 단순한 형태다.

분할 정복 알고리즘의 복잡도는 문제마다 다르다. 병합 정렬은 $O(n\log_2(n))$ , 퀵 정렬은 최악 $O(n^2)$ 이므로 일괄적으로 $O(\log_2(n))$ 라 할 수 없다.
분할 정복은 보통 재귀로 큰 문제를 작은 문제로 나누므로, 반복문만 사용한다는 설명은 틀리다.
선택 문제는 분할 원소(피봇)를 기준으로 나누므로 부분 문제 크기가 피봇 위치에 따라 달라지며, 항상 절반씩 분할되는 것은 아니다.

문제 13

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

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

O(n)

O(n\log_2(n))

O(n^2)

O(2^n)

정답 및 해설

전체 시간 복잡도는 $O(n^2)$ 이다.

이중 반복문: 안쪽 반복이 j회씩 실행되므로 $1+2+\cdots+n=\dfrac{n(n+1)}{2}$ 회
단일 반복문: n회
합계: $\dfrac{n(n+1)}{2}+n$ 이며 최고차항이 $n^2$ 이다.

$O(n)$ 은 뒤쪽 단일 반복문만 센 값으로, 이중 반복을 반영하지 못한다.
$O(n\log_2(n))$ 는 반복 범위가 절반씩 줄어드는 구조에서 나오며, 여기서 안쪽 반복은 j까지 선형으로 늘어난다.
$O(2^n)$ 은 지수적 재귀 등에서 나타나며, 다항 횟수만 실행되는 이 코드와 무관하다.

문제 14

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 ( ㉢ );
  }
}

㉠㉡㉢

1a * a / temp * a / temp * temp * a

2a * a / temp * temp / a * a * temp

3a / temp * a / a * a * temp

4a / temp * temp / temp * temp * a

정답 및 해설

㉠은 a, ㉡은 temp * temp, ㉢은 temp * temp * a이다.

x가 1이면 $a^1=a$ 를 반환한다. x가 짝수면 $a^x=(a^{x/2})^2$ 이므로 temp를 제곱하고, 홀수면 $a^x=(a^{(x-1)/2})^2\cdot a$ 이므로 제곱에 a를 한 번 더 곱한다.

예: power(2, 5)는 temp = power(2, 2) = 4이고, 4 * 4 * 2 = 32이다.

㉠을 a * a, ㉡을 temp * a로 둔 조합은 x가 1일 때 $a^2$ 를 반환하고 짝수 지수에서도 temp를 제곱하지 않아 틀린다.
㉠을 a * a, ㉢을 a * a * temp로 둔 조합은 x가 1일 때 $a^2$ 를 반환하고 홀수 지수에서 temp를 제곱하지 않아 틀린다.
㉡을 temp * a, ㉢을 a * a * temp로 둔 조합은 ㉠은 맞지만 짝수·홀수 경우 모두 temp를 제곱하지 않아 거듭제곱 값이 맞지 않는다.

문제 15

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

O(\log_2(n))

O(n)

O(n\log_2(n))

O(n^2)

정답 및 해설

정렬된 배열의 이진 탐색은 $O(\log_2(n))$ 이다.

비교할 때마다 탐색 구간이 절반으로 줄어 $n \to n/2 \to n/4 \to \cdots \to 1$ 이 되므로, 최악에도 약 $\log_2 n$ 회 비교로 끝난다. 점화식은 $T(n)=T(n/2)+O(1)$ 이다.

$O(n)$ 은 처음부터 하나씩 확인하는 순차 탐색의 복잡도다.
$O(n\log_2(n))$ 은 병합 정렬·힙 정렬 같은 비교 정렬의 복잡도다.
$O(n^2)$ 은 삽입·선택 정렬 등의 최악 복잡도로 탐색과 무관하다.

문제 16

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

○

T(1)=27

○

T(n)

은 궁극적으로 감소하지 않는다.
○

T(n)=9T(\frac{n}{3})+8n

(

n \gt 1

이고,

n

은 3의 거듭제곱이다)

\Theta(1)

\Theta(\log_2(n))

\Theta(n)

\Theta(n^2)

정답 및 해설

시간 복잡도는 $\Theta(n^2)$ 이다.

마스터 정리 적용: $a=9,\ b=3,\ f(n)=8n$
$n^{\log_b a}=n^{\log_3 9}=n^2$

$f(n)=8n=O(n^{2-\epsilon})$ ( $\epsilon=1$ )이므로 첫째 경우에 해당해 $T(n)=\Theta(n^2)$ 이다. 초기값 T(1)=27은 상수배에만 영향을 준다.

$\Theta(1)$ 은 n과 무관한 상수 시간으로, 재귀 호출이 9개씩 늘어나는 이 식과 맞지 않는다.
$\Theta(\log_2(n))$ 은 $T(n)=T(n/2)+c$ 처럼 부분 문제가 하나일 때의 결과다.
$\Theta(n)$ 은 비재귀 항 8n만 본 것으로, 지배적인 재귀 부분 $n^2$ 를 놓친 값이다.

문제 17

다음 수식들에 대해 ㉠～㉢에 해당하는 빅오(

O

) 표기가 옳게 짝지어진 것은? (단,

k

는 상수이다)

㉠: $6{,}450{,}254$ , $4\log(n)+3$ , $3n+8{,}230$ , $n\log(n)+4n$ , $2n^2+5n+3$
㉡: $6{,}450{,}254$
㉢: $6{,}450{,}254$ , $4\log(n)+3$ , $3n+8{,}230$ , $n\log(n)+4n$ , $2n^2+5n+3$ , $4n^3+n^2-2n$
묶음 밖: $3 \times 2^n+8n^5$

㉠㉡㉢

O(2^n)

O(1)

O(n^k)

O(n^2)

O(1)

O(n^3)

O(n^2)

O(\log(n))

O(n^k)

O(n^2)

O(\log(n))

O(n^3)

정답 및 해설

각 묶음에서 가장 빠르게 증가하는 항을 취하면 ㉠은 $O(n^2)$ , ㉡은 $O(1)$ , ㉢은 $O(n^3)$ 이다.

빅오 표기는 최고차항만 남기고 계수를 버린다. ㉡의 6,450,254는 n과 무관한 상수이고, ㉠의 최고차항은 $2n^2$ , ㉢의 최고차항은 $4n^3$ 이다.

지수·상수· $n^k$ 조합: ㉠ 묶음에는 지수항이 없으며 ㉢의 차수는 3으로 정해진다.
제곱·로그· $n^k$ 조합: 상수인 ㉡을 로그로 잡았고 ㉢의 차수도 3으로 특정된다.
제곱·로그·세제곱 조합: ㉡은 상수이므로 가장 엄격한 표기는 로그가 아니라 상수 시간이다.

문제 18

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

○

n

개의 물건은 각기 고유의 무게와 가치를 갖는다.
○ 물건은 나눌 수 없으며, 선택한 물건은 통째로 넣는다.
○ 배낭 내 물건들의 총 무게는 배낭 용량을 초과할 수 없다.
○ 최대의 가치를 갖도록 한정된 용량의 배낭에 물건을 넣는다.

1탐욕 알고리즘을 사용할 경우 시간 복잡도는

O(n)

이다.

2탐욕 알고리즘은 문제에 대한 최적해를 계산할 수 없다.

3동적 프로그래밍 알고리즘은 가치÷무게(무게당 가치)를 사용한다.

4동적 프로그래밍 알고리즘은 힙(heap)을 구성하여 최적해를 탐색한다.

정답 및 해설

물건을 쪼갤 수 없는 0-1 배낭 문제에서 탐욕 알고리즘은 최적해를 보장하지 못한다.

무게당 가치가 큰 순으로 담는 탐욕 전략은 물건을 쪼갤 수 있는 분할 가능 배낭 문제에서만 최적이며, 0-1 배낭은 동적 프로그래밍(또는 분기 한정법)으로 최적해를 구한다.

예: 용량 50에 (무게 10, 가치 60), (20, 100), (30, 120)이면 무게당 가치 순 탐욕은 160을 얻지만 최적은 뒤의 두 물건을 담은 220이다.

탐욕 알고리즘도 무게당 가치로 정렬해야 하므로 $O(n\log_2(n))$ 이 들며 $O(n)$ 이 아니다.
무게당 가치를 기준으로 고르는 것은 탐욕 알고리즘의 방식이며, 동적 프로그래밍은 물건 수와 용량별 최대 가치 표를 채운다.
힙(우선순위 큐)으로 유망한 노드부터 탐색하는 것은 분기 한정법이며, 동적 프로그래밍은 표를 사용한다.

문제 19

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

1삽입(insertion) 정렬:

\Omega(n)

O(n^2)

2선택(selection) 정렬:

\Omega(n)

O(n^2)

3힙(heap) 정렬:

\Omega(n\log_2(n))

O(n^2)

4퀵(quick) 정렬:

\Omega(n\log_2(n))

O(n\log_2(n))

정답 및 해설

삽입 정렬은 최선 $\Omega(n)$ , 최악 $O(n^2)$ 로 옳게 짝지어져 있다.

이미 정렬된 입력이면 원소마다 한 번만 비교해 선형 시간에 끝나고, 역순 입력이면 매번 앞 원소를 모두 밀어야 해 이차 시간이 된다.

선택 정렬은 입력 상태와 관계없이 남은 구간 전체에서 최솟값을 찾으므로 최선도 $\Omega(n^2)$ 이다.
힙 정렬은 최악에도 $O(n\log_2(n))$ 을 보장하므로 최악 $O(n^2)$ 가 틀리다.
퀵 정렬은 피봇이 계속 한쪽 끝으로 치우치면 최악 $O(n^2)$ 가 되므로 최악 $O(n\log_2(n))$ 가 틀리다.

문제 20

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

1(b, c)

2(b, g)

3(c, e)

4(d, e)

정답 및 해설

크루스칼 알고리즘에서 다섯 번째로 MST에 포함되는 간선은 (c, e)이다.

가중치 오름차순으로 (a, b) 2, (c, f) 3, (g, f) 4, (b, g) 5가 사이클 없이 채택되어 a, b, g, f, c가 한 집합이 된다.

가중치 6인 (b, c)는 같은 집합의 두 노드를 이어 사이클을 만들므로 버리고, 같은 가중치의 (c, e)가 다섯 번째로 채택된다.

(b, c): 가중치는 같지만 사이클을 만들어 제외된다.
(b, g): 네 번째로 채택된 간선이다.
(d, e): 가중치 8로 (c, e) 다음, 여섯 번째로 채택된다.

문제 21

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

1b : 1회, c : 1회

2f : 2회, g : 1회

3d : 2회, i : 2회

4e : 3회, h : 1회

정답 및 해설

갱신 횟수가 옳은 것은 e 3회, h 1회이다.

a(0) 확정: b=2, e=11, d=13
b(2) 확정: c=10, e=9, f=5
f(5) 확정: c=6, i=6
c(6)·i(6) 확정: h=7, e=8
h(7) 확정: d=11, g=8
e(8)·g(8) 확정: d=10

∞에서 처음 값이 들어가는 것도 갱신으로 세면 e는 ∞→11→9→8로 3회, h는 ∞→7로 1회다.

b·c 조합: c는 ∞→10→6으로 2회 갱신된다.
f·g 조합: f는 ∞→5로 1회만 갱신된다.
d·i 조합: d는 ∞→13→11→10으로 3회, i는 ∞→6으로 1회다.

문제 22

하노이탑 문제를 해결하기 위한 다음 알고리즘의 빈칸 ㉠, ㉡에 들어갈 코드가 옳게 짝지어진 것은? (단, 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, ( ㉡ ));
  }
}

㉠㉡

1from, to, temp / from, temp, to

2from, to, temp / temp, from, to

3temp, from, to / from, to, temp

4temp, from, to / from, temp, to

정답 및 해설

㉠은 from, to, temp, ㉡은 temp, from, to이다.

매개변수 순서는 (출발, 경유, 도착)이다. 먼저 위쪽 n-1개를 to를 경유해 from에서 temp로 옮기므로 hanoi(n – 1, from, to, temp)이다.

가장 큰 원판을 from에서 to로 옮긴 뒤, temp에 있는 n-1개를 from을 경유해 to로 옮기므로 hanoi(n – 1, temp, from, to)이다.

㉡을 from, temp, to로 둔 조합은 원판을 옮겨 둔 temp가 아니라 이미 비운 from에서 다시 출발하므로 n-1개가 to로 가지 않는다.
㉠을 temp, from, to, ㉡을 from, to, temp로 둔 조합은 첫 호출이 원판이 없는 temp에서 출발하게 되어 위쪽 원판을 치울 수 없다.
㉠을 temp, from, to, ㉡을 from, temp, to로 둔 조합은 두 재귀 호출의 출발 기둥이 모두 잘못되었다.

문제 23

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

m

, 대상 문자열의 길이는

n

m \le n

이다)

1패턴 문자열에 대한 해시 값 1개, 대상 문자열에 대한 해시 값이 최대

n-m+1

개 생성된다.

2문자열의 해시 값을 계산하는 과정에서 호너의 방법(Horner’s rule)을 사용할 수 있다.

3해시 값이 컴퓨터 레지스터의 용량을 초과할 경우, 나머지 연산 (mod)을 사용한다.

4패턴 문자열의 해시 값과 대상 문자열의 일부 문자열에 대한 해시 값이 일치하면 알고리즘을 종료한다.

정답 및 해설

해시 값이 같아도 문자열이 실제로 같다는 보장이 없으므로(해시 충돌), 해시 값이 일치하면 바로 종료한다는 설명이 옳지 않다.

해시 값이 일치하면 해당 위치의 문자를 하나씩 직접 비교해 실제 일치인지 확인하고, 모든 출현 위치를 찾을 때까지 다음 위치로 계속 진행한다.

길이 m인 창을 한 칸씩 옮기므로 대상 문자열의 해시 값은 최대 $n-m+1$ 개, 패턴의 해시 값은 1개다.
문자열을 다항식으로 보고 해시를 계산할 때 호너의 방법을 쓰면 곱셈 횟수를 줄일 수 있다.
해시 값이 너무 커지면 나머지 연산으로 값을 일정 범위로 유지한다.

문제 24

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

m

, 대상 문자열의 길이는

n

m \le n

이다)

1알고리즘의 전처리(preprocessing) 과정을 포함한 시간 복잡도는

O(mn)

이다.

2대상 문자열과 패턴 문자열의 문자들을 각각 비교하며 문자열 매칭 여부를 판단한다.

3매칭이 실패할 경우 미리 생성된 위치 정보를 이용하여 비교를 다시 시작한다.

4대상 문자열과 패턴 문자열에서 일치하는 부분 문자열을 이용하여 비교 횟수를 감소시킨다.

정답 및 해설

KMP는 전처리를 포함해 $O(m+n)$ 이므로 $O(mn)$ 이라는 설명이 옳지 않다.

패턴의 실패 함수(접두사·접미사 일치 정보)를 $O(m)$ 에 미리 만들고, 대상 문자열은 비교 위치를 되돌리지 않고 $O(n)$ 에 한 번 훑는다. $O(mn)$ 은 단순 매칭의 최악 복잡도다.

대상과 패턴의 문자를 하나씩 비교하며 매칭 여부를 판단하는 것은 KMP의 기본 동작이다.
매칭 실패 시 미리 만든 실패 함수 값을 이용해 패턴의 비교 재시작 위치를 정한다.
이미 일치한 접두사 정보를 재활용해 불필요한 비교를 건너뛰므로 비교 횟수가 줄어든다.

문제 25

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

문자	a	b	d	e	g	i	k
빈도 수	50	4	2	8	1	25	6

㉠㉡㉢㉣

1a / i / b / k

2a / i / k / b

3i / e / d / g

4i / e / k / b

정답 및 해설

허프만 트리에서 ㉠은 i, ㉡은 e, ㉢은 k, ㉣은 b이다.

빈도가 가장 작은 두 노드를 반복해 합치면 g(1)+d(2)=3, 3+b(4)=7, k(6)+7=13, e(8)+13=21, 21+i(25)=46, 46+a(50)=96 순이다.

따라서 루트 오른쪽 문자 노드가 a, 그 아래로 ㉠ i, ㉡ e, ㉢ k가 차례로 붙고, 내부 노드 7의 오른쪽 ㉣이 b, 맨 아래 두 문자 노드가 g와 d이다.

a·i·b·k 조합: a는 루트 바로 아래 문자 노드이고, b(4)는 k(6)보다 먼저 합쳐져 더 깊이 놓인다.
a·i·k·b 조합: a는 루트 바로 아래 문자 노드이므로 ㉠ 자리는 i, ㉡ 자리는 e이다.
i·e·d·g 조합: 가장 드문 g와 d는 맨 아래 두 문자 노드로 묶이고, ㉢·㉣은 k와 b이다.

7급 국가직 알고리즘 기출문제모두CBT · moducbt.com

23년 1회차

총 25문항 · 객관식 · 정답·해설 포함

문제 1

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

1알고리즘은 1개 이상의 결과(output)를 생성해야 한다.

2알고리즘에는 반드시 입력(input)이 1개 이상 존재해야 한다.

3알고리즘은 한정된 횟수의 단계 실행 후 반드시 종료해야 한다.

4알고리즘의 각 명령은 모호하지 않고 명확해야 한다.

정답 및 해설

알고리즘의 입력은 0개 이상이면 되므로, 입력이 반드시 1개 이상 존재해야 한다는 설명이 옳지 않다.

알고리즘의 조건은 입력(0개 이상), 출력(1개 이상), 명확성, 유한성, 효과성이다. 난수 생성처럼 외부 입력 없이도 결과를 내는 알고리즘이 있다.

1개 이상의 결과를 생성해야 한다는 것은 출력 조건으로 옳다.
한정된 단계 실행 후 반드시 종료해야 한다는 것은 유한성으로 옳다.
각 명령이 모호하지 않고 명확해야 한다는 것은 명확성으로 옳다.

문제 2

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

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

1fib(7) 호출 시, fib(3)은 5번 호출된다.

2알고리즘의 시간 복잡도는

O(\log_2(n))

이다.

3알고리즘의 점화식은

F_n = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ F_{n-1} + F_{n-2}, & n \gt 1 \end{cases}

이다.

4반복문을 사용하여 알고리즘 성능을 개선할 수 있다.

정답 및 해설

재귀 피보나치는 호출이 지수적으로 늘어나므로 시간 복잡도가 $O(\log_2(n))$ 라는 설명이 옳지 않다.

fib(4)·fib(5)·fib(6)·fib(7)을 호출할 때 fib(3)의 호출 횟수는 1, 2, 3, 5회로 피보나치 수열처럼 늘어 fib(7)에서 5회가 맞다.
제시된 점화식은 코드의 두 기저 조건과 재귀 호출을 그대로 옮긴 것으로 옳다.
반복문으로 직전 두 항만 유지하며 계산하면 $O(n)$ 으로 성능이 개선된다.

문제 3

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

1순서도(flowchart)를 사용하여 도식화한다.

2의사 코드(pseudo code)를 사용하여 기술한다.

3추상 데이터 타입(abstract data type)만으로 기술한다.

4단계별로 명확한 문장(자연어)으로 기술한다.

정답 및 해설

알고리즘은 문제를 푸는 단계적 절차이므로 자연어, 순서도, 의사 코드, 프로그래밍 언어처럼 실행 순서를 표현할 수 있는 수단으로 기술한다.

순서도는 처리 흐름을 도형으로 나타내는 기술 방법이다.
의사 코드는 특정 언어에 얽매이지 않고 절차를 표현하는 대표적 기술 방법이다.
자연어 기술도 단계가 명확하면 알고리즘 기술 방법이 된다.

문제 4

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

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

㉠㉡㉢

1e / g / c

2e / h / i

3k / g / i

4k / h / c

정답 및 해설

DFS 방문 순서를 트리에 대입하면 ㉠은 e, ㉡은 h, ㉢은 i이다.

이어서 a의 오른쪽 자식 i(㉢)와 그 서브트리 j, k, l, m을 방문한다.

e·g·c 조합: f의 두 자식 중 g가 먼저 방문되므로 ㉡ 자리는 h이고, c는 b의 첫 자식이다.
k·g·i 조합: k는 a의 오른쪽 서브트리에 속해 b의 자식 자리에 올 수 없다.
k·h·c 조합: ㉠은 b의 둘째 자식 e이고, ㉢은 오른쪽 서브트리의 루트 i이다.

문제 5

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

int sum(n){
  if (n == 1)
    return 1;
  else
    (          );
}

1return n + sum(n - 1)

2return n - sum(n - 1)

3return n + sum(n + 1)

4return n - sum(n + 1)

정답 및 해설

빈칸에는 return n + sum(n - 1)이 들어간다.

n에서 sum(n - 1)을 빼면 합이 아니라 차가 되어 sum(2)가 1이 되는 등 결과가 틀린다.
n에 sum(n + 1)을 더하면 인자가 커지기만 해 n == 1에 도달하지 못하고 무한 재귀에 빠진다.
n에서 sum(n + 1)을 빼는 경우도 인자가 증가해 종료되지 않는다.

문제 6

힙(heap)에 대한 설명으로 옳지 않은 것은? (단,

n

은 데이터의 개수이다)

1힙을 구성하는 완전 이진 트리는 1차원 배열을 사용하여 구현할 수 있다.

2최대 힙(max heap)의 모든 부모 노드 값은 그들의 자식 노드 값보다 크거나 같다.

3새로운 데이터 삽입 후 힙 성질을 만족하기 위한 연산의 시간 복잡도는

O(n\log_2(n))

이다.

4루트 노드에서 데이터 삭제 후 힙 성질을 만족하기 위한 연산의 시간 복잡도는

O(\log_2(n))

이다.

정답 및 해설

힙에 데이터 하나를 삽입한 뒤 재정비하는 비용은 $O(\log_2(n))$ 이므로 $O(n\log_2(n))$ 라는 설명이 옳지 않다.

새 원소를 마지막 위치에 넣고 부모와 비교·교환하며 올라가는데, 완전 이진 트리의 높이가 $\lfloor \log_2 n \rfloor$ 이므로 교환은 높이만큼만 일어난다.

완전 이진 트리는 빈자리 없이 채워지므로 1차원 배열(부모 i, 자식 2i·2i+1)로 구현할 수 있다.
최대 힙은 모든 부모가 자식보다 크거나 같은 힙 성질을 만족한다.
루트 삭제 후에는 마지막 원소를 루트로 옮겨 아래로 내려가며 재정비하므로 $O(\log_2(n))$ 이다.

문제 7

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

1병합 정렬과 퀵 정렬은 모두 재귀 함수(recursive function)로 구현할 수 있다.

2병합 정렬과 퀵 정렬은 모두 분할 정복(divide-and-conquer) 알고리즘에 속한다.

3퀵 정렬은 병합 정렬과 달리 배열 내 요소 간 데이터를 교환 (swap)하지 않는다.

4퀵 정렬은 입력의 피봇(pivot) 값을, 병합 정렬은 중간 위치를 사용하여 배열을 분할한다.

정답 및 해설

퀵 정렬은 피봇을 기준으로 원소를 좌우로 나누는 과정에서 교환(swap)을 반복하므로, 교환하지 않는다는 설명이 옳지 않다.

오히려 병합 정렬이 교환 대신 보조 배열에 원소를 복사·병합하는 방식이다.

두 정렬은 부분 배열에 자기 자신을 다시 호출하는 재귀 함수로 구현할 수 있다.
두 정렬 모두 분할 → 정복 → 결합의 분할 정복 구조다.
퀵 정렬은 피봇 값에 따라, 병합 정렬은 중간 위치에서 배열을 나눈다.

문제 8

(가) 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

18 / 2

28 / 4

37 / 2

47 / 4

정답 및 해설

(다) 상태는 end = 8, cur = 2에서 교환이 일어난 직후다.

end = 9 회차: 6이 오른쪽으로 이동하며 2, 3, 4, 0, 5, 1과 차례로 교환되고, 9가 8, 7과 교환되어 2, 3, 4, 0, 5, 1, 6, 8, 7, 9가 된다.

end = 8 회차: cur = 0(2와 3), cur = 1(3과 4)은 교환이 없고, cur = 2에서 4 > 0이므로 교환해 2, 3, 0, 4, 5, 1, 6, 8, 7, 9, 즉 (다)가 된다.

end = 8, cur = 4는 같은 회차에서 5와 1을 교환하는 시점이라 (다)보다 더 진행된 상태다.
end = 7, cur = 2 시점에는 직전 회차에서 8과 7이 이미 교환되어 끝부분이 7, 8, 9이므로 (다)와 다르다.
end = 7, cur = 4 역시 끝부분이 7, 8, 9로 정리된 뒤라 (다)와 맞지 않는다.

문제 9

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

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;
  }
}

1쉘(shell) 정렬

2기수(radix) 정렬

3선택(selection) 정렬

4삽입(insertion) 정렬

정답 및 해설

제시된 코드는 삽입(insertion) 정렬이다.

i번째 원소를 cur에 두고, 앞쪽의 이미 정렬된 구간에서 cur보다 큰 원소를 한 칸씩 오른쪽으로 밀어낸 뒤 빈자리에 cur을 끼워 넣는 구조다.

쉘 정렬은 일정 간격(gap)으로 떨어진 원소끼리 삽입 정렬을 하고 간격을 줄여 가는데, 이 코드는 간격 없이 인접 원소만 비교한다.
기수 정렬은 자릿수별로 버킷에 분배하는 비교 없는 정렬이지만, 이 코드는 원소끼리 대소를 비교한다.
선택 정렬은 남은 구간의 최솟값을 찾아 교환하는 방식이라, 원소를 밀어 옮기는 이 코드와 다르다.

문제 10

문제 부류(class)간 포함관계로 옳은 것은? (단,

\mathrm{P} \neq \mathrm{NP}

일 경우이다)

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

$\mathrm{P} \neq \mathrm{NP}$ 일 때 옳은 그림은 P가 NP 안에 NP-완전과 겹치지 않게 있고, NP-완전이 NP와 NP-하드의 겹친 영역에 놓인 것이다.

NP 원 안에 NP-완전이 따로 있고 P가 겹친 영역에 놓인 그림: NP-완전을 NP-하드 밖에 두고 P를 NP-하드에 넣었다.
NP-하드 원 안에 NP-완전이 따로 있고 P가 겹친 영역에 놓인 그림: NP-완전을 NP 밖에 두고 P를 NP-하드에 넣었다.
NP-하드 원 안에 P가 있고 NP-완전이 겹친 영역에 놓인 그림: P를 NP 밖에 두어 P가 NP에 포함된다는 사실에 어긋난다.

문제 11

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

1브루트포스(bruteforce)

2백 트랙킹(backtracking)

3분기 한정법(branch-and-bound)

4동적 프로그래밍(dynamic programming)

정답 및 해설

설명은 동적 프로그래밍에 해당한다.

브루트포스는 가능한 모든 경우를 전부 시도하는 방법으로, 부분 문제의 해답을 저장해 재사용하지 않는다.
백트래킹은 상태 공간 트리를 깊이 우선으로 탐색하다 유망하지 않으면 되돌아가는 방법이다.
분기 한정법은 한계값(bound)으로 유망하지 않은 노드를 가지치기하며 최적해를 찾는 방법이다.

문제 12

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

1이진 탐색(binary search)은 분할 정복 알고리즘에 속한다.

2분할 정복에 기반을 둔 알고리즘의 시간 복잡도는 최악의 경우

O(\log_2(n))

이다.

3반복문(iteration)만을 사용하여 큰 문제를 작은 문제들로 분할한다.

n

개의 정수들 중

k

번째로 큰 정수를 찾는 선택(selection) 문제에서 문제의 크기는 재귀적으로 절반씩 분할된다.

정답 및 해설

이진 탐색은 탐색 구간을 절반으로 나눠 한쪽만 재귀적으로 푸는 분할 정복 알고리즘이다.

가운데 원소와 비교해 문제를 크기 절반의 부분 문제 하나로 줄이므로, 분할 정복의 가장 단순한 형태다.

분할 정복 알고리즘의 복잡도는 문제마다 다르다. 병합 정렬은 $O(n\log_2(n))$ , 퀵 정렬은 최악 $O(n^2)$ 이므로 일괄적으로 $O(\log_2(n))$ 라 할 수 없다.
분할 정복은 보통 재귀로 큰 문제를 작은 문제로 나누므로, 반복문만 사용한다는 설명은 틀리다.
선택 문제는 분할 원소(피봇)를 기준으로 나누므로 부분 문제 크기가 피봇 위치에 따라 달라지며, 항상 절반씩 분할되는 것은 아니다.

문제 13

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

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

O(n)

O(n\log_2(n))

O(n^2)

O(2^n)

정답 및 해설

전체 시간 복잡도는 $O(n^2)$ 이다.

이중 반복문: 안쪽 반복이 j회씩 실행되므로 $1+2+\cdots+n=\dfrac{n(n+1)}{2}$ 회
단일 반복문: n회
합계: $\dfrac{n(n+1)}{2}+n$ 이며 최고차항이 $n^2$ 이다.

$O(n)$ 은 뒤쪽 단일 반복문만 센 값으로, 이중 반복을 반영하지 못한다.
$O(n\log_2(n))$ 는 반복 범위가 절반씩 줄어드는 구조에서 나오며, 여기서 안쪽 반복은 j까지 선형으로 늘어난다.
$O(2^n)$ 은 지수적 재귀 등에서 나타나며, 다항 횟수만 실행되는 이 코드와 무관하다.

문제 14

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 ( ㉢ );
  }
}

㉠㉡㉢

1a * a / temp * a / temp * temp * a

2a * a / temp * temp / a * a * temp

3a / temp * a / a * a * temp

4a / temp * temp / temp * temp * a

정답 및 해설

㉠은 a, ㉡은 temp * temp, ㉢은 temp * temp * a이다.

x가 1이면 $a^1=a$ 를 반환한다. x가 짝수면 $a^x=(a^{x/2})^2$ 이므로 temp를 제곱하고, 홀수면 $a^x=(a^{(x-1)/2})^2\cdot a$ 이므로 제곱에 a를 한 번 더 곱한다.

예: power(2, 5)는 temp = power(2, 2) = 4이고, 4 * 4 * 2 = 32이다.

㉠을 a * a, ㉡을 temp * a로 둔 조합은 x가 1일 때 $a^2$ 를 반환하고 짝수 지수에서도 temp를 제곱하지 않아 틀린다.
㉠을 a * a, ㉢을 a * a * temp로 둔 조합은 x가 1일 때 $a^2$ 를 반환하고 홀수 지수에서 temp를 제곱하지 않아 틀린다.
㉡을 temp * a, ㉢을 a * a * temp로 둔 조합은 ㉠은 맞지만 짝수·홀수 경우 모두 temp를 제곱하지 않아 거듭제곱 값이 맞지 않는다.

문제 15

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

O(\log_2(n))

O(n)

O(n\log_2(n))

O(n^2)

정답 및 해설

정렬된 배열의 이진 탐색은 $O(\log_2(n))$ 이다.

$O(n)$ 은 처음부터 하나씩 확인하는 순차 탐색의 복잡도다.
$O(n\log_2(n))$ 은 병합 정렬·힙 정렬 같은 비교 정렬의 복잡도다.
$O(n^2)$ 은 삽입·선택 정렬 등의 최악 복잡도로 탐색과 무관하다.

문제 16

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

○

T(1)=27

○

T(n)

은 궁극적으로 감소하지 않는다.
○

T(n)=9T(\frac{n}{3})+8n

(

n \gt 1

이고,

n

은 3의 거듭제곱이다)

\Theta(1)

\Theta(\log_2(n))

\Theta(n)

\Theta(n^2)

정답 및 해설

시간 복잡도는 $\Theta(n^2)$ 이다.

마스터 정리 적용: $a=9,\ b=3,\ f(n)=8n$
$n^{\log_b a}=n^{\log_3 9}=n^2$

$f(n)=8n=O(n^{2-\epsilon})$ ( $\epsilon=1$ )이므로 첫째 경우에 해당해 $T(n)=\Theta(n^2)$ 이다. 초기값 T(1)=27은 상수배에만 영향을 준다.

$\Theta(1)$ 은 n과 무관한 상수 시간으로, 재귀 호출이 9개씩 늘어나는 이 식과 맞지 않는다.
$\Theta(\log_2(n))$ 은 $T(n)=T(n/2)+c$ 처럼 부분 문제가 하나일 때의 결과다.
$\Theta(n)$ 은 비재귀 항 8n만 본 것으로, 지배적인 재귀 부분 $n^2$ 를 놓친 값이다.

문제 17

다음 수식들에 대해 ㉠～㉢에 해당하는 빅오(

O

) 표기가 옳게 짝지어진 것은? (단,

k

는 상수이다)

㉠: $6{,}450{,}254$ , $4\log(n)+3$ , $3n+8{,}230$ , $n\log(n)+4n$ , $2n^2+5n+3$
㉡: $6{,}450{,}254$
㉢: $6{,}450{,}254$ , $4\log(n)+3$ , $3n+8{,}230$ , $n\log(n)+4n$ , $2n^2+5n+3$ , $4n^3+n^2-2n$
묶음 밖: $3 \times 2^n+8n^5$

㉠㉡㉢

O(2^n)

O(1)

O(n^k)

O(n^2)

O(1)

O(n^3)

O(n^2)

O(\log(n))

O(n^k)

O(n^2)

O(\log(n))

O(n^3)

정답 및 해설

각 묶음에서 가장 빠르게 증가하는 항을 취하면 ㉠은 $O(n^2)$ , ㉡은 $O(1)$ , ㉢은 $O(n^3)$ 이다.

빅오 표기는 최고차항만 남기고 계수를 버린다. ㉡의 6,450,254는 n과 무관한 상수이고, ㉠의 최고차항은 $2n^2$ , ㉢의 최고차항은 $4n^3$ 이다.

지수·상수· $n^k$ 조합: ㉠ 묶음에는 지수항이 없으며 ㉢의 차수는 3으로 정해진다.
제곱·로그· $n^k$ 조합: 상수인 ㉡을 로그로 잡았고 ㉢의 차수도 3으로 특정된다.
제곱·로그·세제곱 조합: ㉡은 상수이므로 가장 엄격한 표기는 로그가 아니라 상수 시간이다.

문제 18

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

○

n

1탐욕 알고리즘을 사용할 경우 시간 복잡도는

O(n)

이다.

2탐욕 알고리즘은 문제에 대한 최적해를 계산할 수 없다.

3동적 프로그래밍 알고리즘은 가치÷무게(무게당 가치)를 사용한다.

4동적 프로그래밍 알고리즘은 힙(heap)을 구성하여 최적해를 탐색한다.

정답 및 해설

물건을 쪼갤 수 없는 0-1 배낭 문제에서 탐욕 알고리즘은 최적해를 보장하지 못한다.

예: 용량 50에 (무게 10, 가치 60), (20, 100), (30, 120)이면 무게당 가치 순 탐욕은 160을 얻지만 최적은 뒤의 두 물건을 담은 220이다.

탐욕 알고리즘도 무게당 가치로 정렬해야 하므로 $O(n\log_2(n))$ 이 들며 $O(n)$ 이 아니다.
무게당 가치를 기준으로 고르는 것은 탐욕 알고리즘의 방식이며, 동적 프로그래밍은 물건 수와 용량별 최대 가치 표를 채운다.
힙(우선순위 큐)으로 유망한 노드부터 탐색하는 것은 분기 한정법이며, 동적 프로그래밍은 표를 사용한다.

문제 19

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

1삽입(insertion) 정렬:

\Omega(n)

O(n^2)

2선택(selection) 정렬:

\Omega(n)

O(n^2)

3힙(heap) 정렬:

\Omega(n\log_2(n))

O(n^2)

4퀵(quick) 정렬:

\Omega(n\log_2(n))

O(n\log_2(n))

정답 및 해설

삽입 정렬은 최선 $\Omega(n)$ , 최악 $O(n^2)$ 로 옳게 짝지어져 있다.

이미 정렬된 입력이면 원소마다 한 번만 비교해 선형 시간에 끝나고, 역순 입력이면 매번 앞 원소를 모두 밀어야 해 이차 시간이 된다.

선택 정렬은 입력 상태와 관계없이 남은 구간 전체에서 최솟값을 찾으므로 최선도 $\Omega(n^2)$ 이다.
힙 정렬은 최악에도 $O(n\log_2(n))$ 을 보장하므로 최악 $O(n^2)$ 가 틀리다.
퀵 정렬은 피봇이 계속 한쪽 끝으로 치우치면 최악 $O(n^2)$ 가 되므로 최악 $O(n\log_2(n))$ 가 틀리다.

문제 20

1(b, c)

2(b, g)

3(c, e)

4(d, e)

정답 및 해설

크루스칼 알고리즘에서 다섯 번째로 MST에 포함되는 간선은 (c, e)이다.

가중치 오름차순으로 (a, b) 2, (c, f) 3, (g, f) 4, (b, g) 5가 사이클 없이 채택되어 a, b, g, f, c가 한 집합이 된다.

가중치 6인 (b, c)는 같은 집합의 두 노드를 이어 사이클을 만들므로 버리고, 같은 가중치의 (c, e)가 다섯 번째로 채택된다.

(b, c): 가중치는 같지만 사이클을 만들어 제외된다.
(b, g): 네 번째로 채택된 간선이다.
(d, e): 가중치 8로 (c, e) 다음, 여섯 번째로 채택된다.

문제 21

1b : 1회, c : 1회

2f : 2회, g : 1회

3d : 2회, i : 2회

4e : 3회, h : 1회

정답 및 해설

갱신 횟수가 옳은 것은 e 3회, h 1회이다.

a(0) 확정: b=2, e=11, d=13
b(2) 확정: c=10, e=9, f=5
f(5) 확정: c=6, i=6
c(6)·i(6) 확정: h=7, e=8
h(7) 확정: d=11, g=8
e(8)·g(8) 확정: d=10

∞에서 처음 값이 들어가는 것도 갱신으로 세면 e는 ∞→11→9→8로 3회, h는 ∞→7로 1회다.

b·c 조합: c는 ∞→10→6으로 2회 갱신된다.
f·g 조합: f는 ∞→5로 1회만 갱신된다.
d·i 조합: d는 ∞→13→11→10으로 3회, i는 ∞→6으로 1회다.

문제 22

하노이탑 문제를 해결하기 위한 다음 알고리즘의 빈칸 ㉠, ㉡에 들어갈 코드가 옳게 짝지어진 것은? (단, 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, ( ㉡ ));
  }
}

㉠㉡

1from, to, temp / from, temp, to

2from, to, temp / temp, from, to

3temp, from, to / from, to, temp

4temp, from, to / from, temp, to

정답 및 해설

㉠은 from, to, temp, ㉡은 temp, from, to이다.

매개변수 순서는 (출발, 경유, 도착)이다. 먼저 위쪽 n-1개를 to를 경유해 from에서 temp로 옮기므로 hanoi(n – 1, from, to, temp)이다.

가장 큰 원판을 from에서 to로 옮긴 뒤, temp에 있는 n-1개를 from을 경유해 to로 옮기므로 hanoi(n – 1, temp, from, to)이다.

㉡을 from, temp, to로 둔 조합은 원판을 옮겨 둔 temp가 아니라 이미 비운 from에서 다시 출발하므로 n-1개가 to로 가지 않는다.
㉠을 temp, from, to, ㉡을 from, to, temp로 둔 조합은 첫 호출이 원판이 없는 temp에서 출발하게 되어 위쪽 원판을 치울 수 없다.
㉠을 temp, from, to, ㉡을 from, temp, to로 둔 조합은 두 재귀 호출의 출발 기둥이 모두 잘못되었다.

문제 23

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

m

, 대상 문자열의 길이는

n

m \le n

이다)

1패턴 문자열에 대한 해시 값 1개, 대상 문자열에 대한 해시 값이 최대

n-m+1

개 생성된다.

2문자열의 해시 값을 계산하는 과정에서 호너의 방법(Horner’s rule)을 사용할 수 있다.

3해시 값이 컴퓨터 레지스터의 용량을 초과할 경우, 나머지 연산 (mod)을 사용한다.

4패턴 문자열의 해시 값과 대상 문자열의 일부 문자열에 대한 해시 값이 일치하면 알고리즘을 종료한다.

정답 및 해설

해시 값이 같아도 문자열이 실제로 같다는 보장이 없으므로(해시 충돌), 해시 값이 일치하면 바로 종료한다는 설명이 옳지 않다.

해시 값이 일치하면 해당 위치의 문자를 하나씩 직접 비교해 실제 일치인지 확인하고, 모든 출현 위치를 찾을 때까지 다음 위치로 계속 진행한다.

길이 m인 창을 한 칸씩 옮기므로 대상 문자열의 해시 값은 최대 $n-m+1$ 개, 패턴의 해시 값은 1개다.
문자열을 다항식으로 보고 해시를 계산할 때 호너의 방법을 쓰면 곱셈 횟수를 줄일 수 있다.
해시 값이 너무 커지면 나머지 연산으로 값을 일정 범위로 유지한다.

문제 24

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

m

, 대상 문자열의 길이는

n

m \le n

이다)

1알고리즘의 전처리(preprocessing) 과정을 포함한 시간 복잡도는

O(mn)

이다.

2대상 문자열과 패턴 문자열의 문자들을 각각 비교하며 문자열 매칭 여부를 판단한다.

3매칭이 실패할 경우 미리 생성된 위치 정보를 이용하여 비교를 다시 시작한다.

4대상 문자열과 패턴 문자열에서 일치하는 부분 문자열을 이용하여 비교 횟수를 감소시킨다.

정답 및 해설

KMP는 전처리를 포함해 $O(m+n)$ 이므로 $O(mn)$ 이라는 설명이 옳지 않다.

대상과 패턴의 문자를 하나씩 비교하며 매칭 여부를 판단하는 것은 KMP의 기본 동작이다.
매칭 실패 시 미리 만든 실패 함수 값을 이용해 패턴의 비교 재시작 위치를 정한다.
이미 일치한 접두사 정보를 재활용해 불필요한 비교를 건너뛰므로 비교 횟수가 줄어든다.

문제 25

문자	a	b	d	e	g	i	k
빈도 수	50	4	2	8	1	25	6

㉠㉡㉢㉣

1a / i / b / k

2a / i / k / b

3i / e / d / g

4i / e / k / b

정답 및 해설

허프만 트리에서 ㉠은 i, ㉡은 e, ㉢은 k, ㉣은 b이다.

빈도가 가장 작은 두 노드를 반복해 합치면 g(1)+d(2)=3, 3+b(4)=7, k(6)+7=13, e(8)+13=21, 21+i(25)=46, 46+a(50)=96 순이다.

따라서 루트 오른쪽 문자 노드가 a, 그 아래로 ㉠ i, ㉡ e, ㉢ k가 차례로 붙고, 내부 노드 7의 오른쪽 ㉣이 b, 맨 아래 두 문자 노드가 g와 d이다.

a·i·b·k 조합: a는 루트 바로 아래 문자 노드이고, b(4)는 k(6)보다 먼저 합쳐져 더 깊이 놓인다.
a·i·k·b 조합: a는 루트 바로 아래 문자 노드이므로 ㉠ 자리는 i, ㉡ 자리는 e이다.
i·e·d·g 조합: 가장 드문 g와 d는 맨 아래 두 문자 노드로 묶이고, ㉢·㉣은 k와 b이다.