9급 국가직 알고리즘 2024년 기출문제

다음은 빅오($O$) 표기법에 해당하는 설명이다. (가), (나)에 들어갈 관계연산자를 바르게 연결한 것은?

어떤 양의 상수 $c$와 $n_0$이 존재하여 모든 $n$

(가)

$n_0$에 대하여 $f(n)$

(나)

$c\bullet g(n)$을 만족하면 $f(n)$은 $O(g(n))$에 속한다.

(가) (나)

안정 정렬(stable sort) 알고리즘에 해당하지 않는 것은?

다음과 같은 총 20 kg의 분할 가능한 금속 분말을 17 kg의 무게까지 허용 가능한 배낭에 넣으려 할 때, 그리디(greedy) 알고리즘으로 얻을 수 있는 최대 이익은?

금속 분말 이름	A	B	C
무게	10 kg	6 kg	4 kg
이익	200원	300원	400원

입력 크기 $n$에 대한 수행 횟수를 점근적 표기법으로 표현했을 때 옳지 않은 것은?

다음 이진트리(binary tree)가 이진탐색트리(binary search tree)의 조건을 만족하려면 제거되어야 할 단말 노드(leaf node)의 최소 개수는?

$n\times n$ 행렬 $A$와 $n\times n$ 행렬 $B$에 대하여 행렬 곱셈을 하고자 한다. 다음과 같은 행렬 $C$의 각 원소를 구하는 공식을 이용하여 행렬 곱셈 결과인 행렬 $C$를 만들 때 시간복잡도(time complexity)는? (단, $0\le i$, $j\le n-1$이다)

$C_{ij}={\sum }_{k=0}^{n-1}{A}_{ik}{B}_{kj}$

힙(heap)과 힙 정렬에 대한 설명으로 옳은 것만을 모두 고르면? (단, 힙은 이진트리이고, $n$은 원소의 개수를 나타낸다)

ㄱ. 힙은 완전이진트리(complete binary tree) 구조를 가진다.

ㄴ. 힙은 배열로 구현하기에 적합하지 않다.

ㄷ. 힙에 하나의 노드를 추가하는 데 걸리는 시간은 $O(\log n)$이다.

ㄹ. 힙 정렬의 수행시간은 $O(n\log n)$이다.

입력 크기가 $n$인 정렬 알고리즘에 대한 시간복잡도가 바르게 연결되지 않은 것은?

정렬 알고리즘 최악의 경우 평균적인 경우 최선의 경우

다음은 문자들에 대한 빈도수를 나타낸다. 이 문자들에 대한 허프만 코드(Huffman code)를 생성할 경우에 가장 긴 코드를 가진 문자의 비트수는?

문자	a	b	c	d	e	f
빈도수	1	9	18	48	11	12

다음 파이썬 코드의 시간복잡도는? (단, $n$은 1보다 큰 정수이다)

def abc(n) :
    if n == 1 : return 1
    else : return n * abc(n - 1)

다음 그래프에서 생성이 가능한 신장 트리(spanning tree)의 최대 개수는?

위상 정렬(topological sort)을 적용할 때 모든 정점을 포함하는 결과가 생성될 수 없는 그래프는?

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

○ 모든 쌍 최단 거리(all pairs shortest path)를 구하는 알고리즘이다.

○ 음수의 가중치를 가진 간선(edge)이 있어도 수행될 수 있다.

○ 동적 계획법(dynamic programming)의 원리를 이용한다.

○ 시간복잡도는 $O(n^3)$이다. (단, $n$은 정점의 수이다)

다음 C언어로 작성된 함수의 입력값으로 13이 입력될 경우 출력되는 결과는?

void foo(int n) {
    if(n != 0){
        foo(n/2);
        printf("%d", n%2);
    }
}

텍스트 문자열 01001에 대하여 패턴 문자열 001을 찾기 위해 브루트－포스(brute-force) 문자열 검색 알고리즘을 사용할 경우, 문자를 비교한 총 횟수는? (단, 패턴 문자열이 한번 검색되면 더 이상 검색하지 않는다)

다음 중 그리디 알고리즘에 해당하는 것만을 모두 고르면?

ㄱ. 라빈－카프(Rabin-Karp) 알고리즘

ㄴ. 병합 정렬 알고리즘

ㄷ. 다익스트라 알고리즘

ㄹ. 플로이드－워셜 알고리즘

퀵 정렬 시 시간복잡도가 최악의 경우가 되는 것으로 가장 적절한 것은?

분할 정복(divide-conquer) 문제 해결 기법을 이용하여 토너먼트 방식으로 64개의 축구팀 중 1등을 결정하기 위해 치르게 되는 최소의 경기 횟수는? (단, 모든 경기는 팀별 1 : 1 방식으로 진행되며 무승부 및 기권은 없다)

다음 설명의 (가)에 들어갈 용어로 옳은 것은? (단, P ≠ NP이다)

어떤 문제 A가 다음을 모두 만족하면

(가)

이다.

○ 문제 A는 NP에 속한다.

○ 모든 NP 문제들은 다항식 시간에 문제 A로 변환할 수 있다.

다음 의사코드(pseudo-code)로 표현된 알고리즘의 수행시간을 $T(n)$으로 나타낼 때, $T(n)$의 계산식과 $T(n)$의 점근적 복잡도로 옳은 것은? (단, $n$은 1보다 큰 정수이고 $c$는 양의 상수이다)

algo(n)
{
    if (n ≤ 1) return 0;
    return 1 + algo(n / 2);
}