공무원 9급 - 알고리즘 기출

문항 미리보기

60문항 중 앞 5문항입니다.

1. 1

   [2026] 1 이상인 자연수 x에 대해 1부터 x까지의 합을 구하는 재귀 함수가 있다. if (x <= 1) return 1; 일 때, return x + (가); 의 (가)에 들어갈 올바른 코드는?

   1. 1x + 1
   2. 2x - 1
   3. 3sum(x + 1)
   4. 4sum(x - 1)

   정답sum(x - 1)

   sum(x) = x + sum(x-1) 점화식. 기저 조건 x<=1일 때 1을 반환하므로, x와 함께 sum(x-1)을 재귀 호출해야 1부터 x까지 누적된다.

2. 2

   [2026] 불일치 문자(bad character) 이동표와 일치 접미부(good suffix) 이동표를 모두 사용하는 문자열 매칭 알고리즘은?

   1. 1다익스트라(Dijkstra) 알고리즘
   2. 2라빈-카프(Rabin-Karp) 알고리즘
   3. 3보이어-무어(Boyer-Moore) 알고리즘
   4. 4플로이드-워셜(Floyd-Warshall) 알고리즘

   정답보이어-무어(Boyer-Moore) 알고리즘

   보이어-무어 알고리즘은 패턴의 끝에서부터 비교하며, 불일치가 발생하면 bad character 휴리스틱과 good suffix 휴리스틱 두 가지 이동표를 이용해 최대한 많이 건너뛴다.

3. 3

   [2026] 분할 정복(divide and conquer) 방식으로 동작하는 정렬 알고리즘만을 모두 고르면? ㄱ. 버블 정렬 ㄴ. 병합 정렬 ㄷ. 퀵 정렬

   1. 1ㄴ
   2. 2ㄱ, ㄴ
   3. 3ㄱ, ㄷ
   4. 4ㄴ, ㄷ

   정답ㄴ, ㄷ

   분할 정복으로 동작하는 대표적 정렬 알고리즘은 병합 정렬과 퀵 정렬이다. 버블 정렬은 인접 원소를 반복 교환하는 방식으로 분할 정복이 아니다.

4. 4

   [2026] 빅오(Big-O) 표기법에 대한 설명으로 옳지 않은 것은?

   1. 1O(n^2)은 O(1)을 포함한다
   2. 2O(n^2)은 O(n log n)을 포함한다
   3. 3O(n^2)은 O(n^3)을 포함하지 않는다
   4. 4O(n^2)은 O(n)을 포함하지 않는다

   정답O(n^2)은 O(n)을 포함하지 않는다

   빅오는 점근적 상한을 나타낸다. n <= n^2 이므로 O(n)은 O(n^2)에 포함된다. 따라서 O(n^2)이 O(n)을 포함하지 않는다는 설명은 거짓이다.

5. 5

   [2026] 크루스칼(Kruskal) 알고리즘으로 최소 비용 신장 트리(MST)를 구할 때의 동작 순서로 옳은 것은?

   1. 1정점을 임의로 선택하고 인접한 최소 가중치 간선을 추가
   2. 2간선을 가중치 오름차순으로 정렬한 뒤 사이클이 생기지 않는 간선만 선택
   3. 3모든 정점 쌍의 최단 거리를 갱신
   4. 4깊이 우선 탐색으로 모든 간선을 방문

   정답간선을 가중치 오름차순으로 정렬한 뒤 사이클이 생기지 않는 간선만 선택

   크루스칼 알고리즘은 모든 간선을 가중치 기준 오름차순 정렬 후, 사이클을 형성하지 않는 간선을 작은 것부터 차례로 선택하여 MST를 완성한다. union-find 자료구조로 사이클 검사.