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

24년 1회차

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

1 / 1

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

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

24년 1회차

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

문제 1

정점이 6개인 무방향 완전 그래프의 간선의 개수는?

212

315

421

정답 및 해설

정점이 6개인 무방향 완전 그래프의 간선 수는 15개이다.

완전 그래프는 서로 다른 모든 정점 쌍이 간선 하나로 연결되므로, 간선 수는 정점 2개를 고르는 조합의 수와 같다.

$\dfrac{n(n-1)}{2} = \dfrac{6 \times 5}{2} = 15$

6개는 정점 6개를 한 바퀴 잇는 사이클 그래프의 간선 수에 불과하다.
12개는 모든 정점의 차수가 4인 그래프의 간선 수로, 완전 그래프의 차수 5보다 작다.
21개는 정점이 7개인 완전 그래프의 간선 수이다.

문제 2

큐에 다음 함수를 적용한 결과로 (가) ∼ (다)에 들어갈 내용을 바르게 연결한 것은?

enqueue(e): 큐의 제 위치에 객체 e를 삽입한다.
dequeue(): 큐의 제 위치에서 객체를 삭제한다. 빈 큐일 경우에는 “error”를 출력한다.

연산순서	함수	출력	큐 저장공간
1	dequeue()	“error”	()
2	enqueue(1)		(1)
3	enqueue(2)		(1, 2)
4	enqueue(5)		(1, 2, 5)
5	dequeue()		(가)
6	enqueue(7)		(나)
7	dequeue()		(다)

(가) (나) (다)

1(1, 2) (1, 2, 7) (1, 2)

2(2, 5) (2, 5, 7) (5, 7)

3(2, 5) (5, 7) (7)

4(2, 5, 1) (2, 5, 1, 7) (5, 1, 7, 2)

정답 및 해설

(가)~(다)는 차례로 (2, 5) → (2, 5, 7) → (5, 7)이다.

큐는 선입선출(FIFO) 구조로, 삭제는 맨 앞에서, 삽입은 맨 뒤에서 일어난다.

(1, 2, 5)에서 dequeue로 맨 앞의 1이 빠져 (2, 5), enqueue(7)로 뒤에 7이 붙어 (2, 5, 7), 다시 dequeue로 맨 앞의 2가 빠져 (5, 7)이 된다.

(1, 2) → (1, 2, 7) → (1, 2)는 맨 뒤에서 꺼내는 스택(LIFO) 방식으로 처리한 결과이다.
(2, 5) → (5, 7) → (7)은 enqueue(7)에서도 원소를 하나 삭제한 것처럼 처리해 연산 정의와 맞지 않는다.
(2, 5, 1)로 시작하는 결과는 삭제한 1을 다시 뒤에 넣은 회전처럼 처리한 것으로, 삭제 연산의 정의와 맞지 않는다.

문제 3

다음 최대 힙에 대한 설명으로 옳지 않은 것은?

1완전 이진 트리이어야 한다.

2노드 A는 가장 큰 키 값을 가져야 한다.

3노드 B는 노드 F보다 큰 키 값을 가져야 한다.

4노드 B와 노드 D가 같은 키 값을 가질 수 있다.

정답 및 해설

옳지 않은 설명은 노드 B가 노드 F보다 큰 키 값을 가져야 한다는 것이다.

최대 힙은 완전 이진 트리이면서 부모의 키가 자식의 키보다 크거나 같다는 조건만 만족하면 된다. B는 A의 왼쪽 서브트리, F는 C의 자식으로 서로 조상·자손 관계가 아니므로 둘 사이의 크기는 정해지지 않는다.

완전 이진 트리 조건: 힙은 배열로 표현하기 위해 마지막 레벨을 왼쪽부터 채운 완전 이진 트리여야 한다.
루트 A의 키: 모든 노드의 조상이므로 가장 큰 키를 가진다.
B와 D의 키가 같은 경우: 부모가 자식보다 크거나 같으면 되므로 같은 키도 허용된다.

문제 4

그리디 알고리즘으로 최적의 해가 보장되지 않는 것은?

1허프만(Huffman) 코딩

2최소 신장 트리

3다익스트라(Dijkstra) 최단 경로

40-1 배낭(knapsack) 문제

정답 및 해설

그리디로 최적해가 보장되지 않는 것은 0-1 배낭 문제이다.

물건을 쪼갤 수 없으므로 단위 무게당 가치가 큰 순으로 담으면 남는 용량을 낭비해 최적을 놓칠 수 있어, 동적 계획법으로 풀어야 한다. 물건을 쪼갤 수 있는 분할 배낭 문제는 그리디로 최적해를 얻는다.

허프만 코딩은 빈도가 가장 작은 두 노드를 반복 병합하는 그리디로 최적 접두 코드를 만든다.
최소 신장 트리는 크루스칼·프림 알고리즘이 가장 가벼운 안전 간선을 고르는 그리디로 최적해를 보장한다.
다익스트라 최단 경로는 간선 가중치가 음수가 아니면 거리가 가장 짧은 정점부터 확정하는 그리디로 최적해를 보장한다.

문제 5

다음 C 코드에서 사용한 재귀 알고리즘의 시간 복잡도는? (단, n은 배열의 크기이다)

int S(int A[ ], int n){
    if( n <= 0 )  return 0;
    else return A[n-1] + S(A, n/2);
}

\Theta(\log n)

\Theta(n)

\Theta(n\log n)

\Theta(n^2)

정답 및 해설

이 재귀 알고리즘의 시간 복잡도는 $\Theta(\log n)$ 이다.

호출 한 번마다 덧셈 하나의 상수 작업을 하고, 크기를 절반으로 줄여 한 번만 재귀하므로 점화식은 $T(n) = T(n/2) + \Theta(1)$ 이다.

n이 0 이하가 될 때까지 절반씩 줄어드는 횟수는 약 $\log_2 n$ 회이므로 전체 시간은 $\Theta(\log n)$ 이다.

$\Theta(n)$ 은 크기를 1씩 줄이는 재귀 $T(n)=T(n-1)+\Theta(1)$ 의 복잡도이다.
$\Theta(n\log n)$ 은 두 번 재귀하고 선형 작업을 하는 $T(n)=2T(n/2)+\Theta(n)$ 의 복잡도이다.
$\Theta(n^2)$ 은 크기를 1씩 줄이며 매번 선형 작업을 하는 $T(n)=T(n-1)+\Theta(n)$ 의 복잡도이다.

문제 6

1부터 n까지 합을 구하는 다음 파이썬 프로그램의 빈칸에 들어갈 내용은? (단, n은 n≥1인 정수이다)

def sum(n):
    ret = 0
    for (          ):
        ret += i
    return ret

1i in range(-1, n+1)

2i in range(0, n)

3i in range(1, n)

4i in range(1, n+1)

정답 및 해설

빈칸에는 i in range(1, n+1)이 들어간다.

파이썬 range(a, b)는 a부터 b-1까지의 정수를 만들므로, 1부터 n까지 더하려면 끝값을 n+1로 주어야 한다.

range(-1, n+1)은 -1과 0이 함께 더해져 결과가 1 작아진다.
range(0, n)은 0부터 n-1까지라 마지막 n이 빠진다.
range(1, n)은 1부터 n-1까지라 마지막 n이 빠진다.

문제 7

연산 이론상의 문제 유형에 대한 설명으로 옳지 않은 것은?

1P는 다항식 시간에 해결할 수 있는 문제군이다.

2NP는 비결정론적 다항식 시간에 해결할 수 있는 문제군이다.

3어떤 NP-Complete 문제에 대해서 다항식 시간에 해결할 수 있는 알고리즘을 찾아내면, 다른 모든 NP-Complete 문제도 다항식 시간에 해를 구할 수 있다.

4NP-Complete 문제들 중에는 NP에 속하지 않는 문제도 있다.

정답 및 해설

옳지 않은 것은 NP-Complete 문제 중에 NP에 속하지 않는 문제가 있다는 설명이다.

NP-Complete는 정의상 NP에 속하면서 모든 NP 문제가 다항식 시간에 환원되는 문제이므로, 모든 NP-Complete 문제는 NP에 속한다. NP에 속하지 않을 수 있는 것은 NP-Hard 문제이다.

P를 다항식 시간에 해결할 수 있는 문제군으로 설명한 것은 옳다.
NP를 비결정론적 다항식 시간에 해결할 수 있는(해를 다항식 시간에 검증할 수 있는) 문제군으로 설명한 것은 옳다.
모든 NP 문제가 각 NP-Complete 문제로 환원되므로, 하나를 다항식 시간에 풀면 다른 NP-Complete 문제도 다항식 시간에 풀린다는 설명은 옳다.

문제 8

다음 fib() 함수는 피보나치 수열을 계산하는 C 코드이다. fib(17)을 실행할 때 fib(8)과 fib(10)이 각각 호출되는 횟수를 바르게 연결한 것은?

int fib(int n){
    if(n==1 || n==2) return 1;
    else return (fib(n-1) + fib(n-2));
}

fib(8) fib(10)

152번 13번

252번 21번

355번 13번

455번 21번

정답 및 해설

fib(17) 실행 시 fib(8)은 55회, fib(10)은 21회 호출된다.

fib(k)를 호출하는 것은 fib(k+1)과 fib(k+2)뿐이므로, 호출 횟수를 C(k)라 하면 $C(k)=C(k+1)+C(k+2)$ , $C(17)=C(16)=1$ 이 되어 피보나치 수열을 이룬다. 즉 $C(k)=F(18-k)$ 이다.

$C(8)=F(10)=55$
$C(10)=F(8)=21$

52회·13회 조합은 두 값이 모두 틀리다. 13회는 fib(11)의 호출 횟수이다.
52회·21회 조합은 fib(10)은 맞지만 fib(8)을 55회가 아닌 52회로 잡아 틀리다.
55회·13회 조합은 fib(8)은 맞지만 13회는 fib(11)의 호출 횟수이다.

문제 9

다음 이진 검색 트리에서 노드 이동 또는 포인터 변경의 횟수를 최소화하면서 노드를 삭제하는 과정의 설명으로 옳지 않은 것은?

1노드 8을 삭제하려면 노드 15에서 노드 8을 가리키는 포인터를 NIL(또는 NULL)로 변경한다.

2노드 25를 삭제하려면 그 자리에 노드 30을 놓는다.

3노드 50을 삭제하려면 노드 40이 노드 60을 직접 가리키도록 포인터를 변경한다.

4노드 60을 삭제하려면 그 자리에 노드 55 또는 노드 66을 놓는다.

정답 및 해설

옳지 않은 설명은 노드 25를 삭제할 때 그 자리에 노드 30을 놓는다는 것이다.

25는 왼쪽 자식 20과 오른쪽 자식 30을 모두 가지므로, 그 자리에는 왼쪽 서브트리의 최댓값 20이나 오른쪽 서브트리의 최솟값 27이 와야 한다. 30을 올리면 30의 왼쪽에 있던 27·29와 20을 함께 재배치해야 해 이동 횟수가 최소가 되지 않는다.

노드 8 삭제: 자식이 없는 리프이므로 부모 15의 해당 포인터만 NIL로 바꾸면 된다.
노드 50 삭제: 오른쪽 자식 60 하나만 가지므로 부모 40이 60을 직접 가리키게 하면 된다.
노드 60 삭제: 자식이 둘이므로 선행자 55나 후계자 66을 그 자리에 놓는다.

문제 10

레드－블랙 트리로 옳은 것은? (단, 외부 노드(leaf)는 표시하지 않고, 블랙 노드는 검정색으로, 레드 노드는 흰색으로 나타낸 것이다)

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

레드-블랙 트리는 루트 35 아래 레드 20(자식 블랙 10·블랙 25, 25의 오른쪽 레드 30)과 블랙 50(자식 레드 40·레드 60)이 놓인 트리이다.

이 트리는 이진 검색 트리 순서를 지키고, 레드 노드의 자식이 모두 블랙이며, 루트에서 모든 외부 노드까지의 블랙 노드 수가 2개로 같다.

루트 30의 왼쪽 블랙 10 아래 레드 20, 그 아래 레드 25가 이어진 트리: 레드 노드가 연속해 레드 자식을 가질 수 없다는 조건을 어긴다.
루트 30의 오른쪽 블랙 65 아래 레드 40, 그 아래 블랙 50이 있는 트리: 50을 거치는 경로만 블랙 노드가 3개가 되어 블랙 높이가 다르다.
루트 30의 오른쪽 레드 50 아래 블랙 40의 오른쪽에 55가 있는 트리: 55가 50의 왼쪽 서브트리에 있어 이진 검색 트리 순서를 어긴다.

문제 11

해시 테이블에 대한 설명으로 옳지 않은 것은?

1충돌이 발생하지 않는다면 상수 시간

O(1)

에 검색과 저장이 가능하다.

2키 값을 입력으로 받아 해시 테이블상의 주소를 리턴하는 해시 함수는 나누기 방법뿐만 아니라 곱하기 방법으로도 만들 수 있다.

3저장 원소의 총수를 해시 테이블의 크기로 나눈 적재율(load factor)은 해시 테이블의 성능에 중요한 영향을 미친다.

4충돌을 해결하기 위한 별도 체이닝과 오픈 주소 방법은 모두 추가적인 저장 공간을 필요로 하지 않는다.

정답 및 해설

옳지 않은 것은 별도 체이닝과 오픈 주소 방법 모두 추가 저장 공간이 필요 없다는 설명이다.

별도 체이닝은 충돌한 원소를 테이블 밖의 연결 리스트에 매달므로 노드와 포인터를 위한 추가 공간이 필요하다. 추가 공간 없이 테이블 내부의 빈 칸을 찾아 저장하는 것은 오픈 주소 방법이다.

충돌이 없으면 해시 함수 계산 한 번으로 주소가 정해지므로 검색·저장이 $O(1)$ 이라는 설명은 옳다.
해시 함수를 나누기(제산) 방법뿐 아니라 곱하기(승산) 방법으로도 만들 수 있다는 설명은 옳다.
적재율이 높을수록 충돌이 잦아져 성능이 떨어지므로 적재율이 성능에 중요한 영향을 준다는 설명은 옳다.

문제 12

프림(Prim) 알고리즘을 적용하여 다음 그래프의 정점 A에서 시작하는 최소 신장 트리를 구할 때, 마지막으로 선택되는 정점은?

정답 및 해설

프림 알고리즘으로 선택되는 마지막 정점은 C이다.

매 단계 트리와 바깥 정점을 잇는 최소 간선을 고르면 B(7), D(8), E(4), H(3) 순으로 붙는다. 이때 남은 후보는 B–F 9, D–C 10, H–C 11, H–G 14이므로 F가 9로 선택된다.

이어서 F–G 1로 G가 붙고, 마지막으로 G–C 2로 C가 선택된다.

F: 다섯 번째로 선택되며 B–F 간선 9가 D–C 10보다 작아 C보다 먼저 붙는다.
G: F가 들어온 직후 가중치 1인 F–G 간선으로 여섯 번째에 선택된다.
H: E가 들어온 직후 E–H 간선 3으로 네 번째에 선택된다.

문제 13

다음 그래프에 다익스트라 알고리즘을 적용하여 구한 정점 a에서 정점 f까지 최단 경로의 거리는?

110

211

312

413

정답 및 해설

정점 a에서 f까지의 최단 거리는 10이며, 경로는 a→b→c→e→d→f이다.

a에서 b까지 1, b→c 간선 2로 c까지 3이 되어 직행 간선 a→c 5보다 짧다. c→e 1로 e까지 4가 되고, e→d 2로 d까지 6이 되어 a→d 8보다 짧다.

f로 가는 간선은 d→f 4와 e→f 7이므로 6+4=10이 4+7=11보다 작다.

11: e에서 f로 바로 가는 경로의 거리로, d를 거치는 경로보다 1 길다.
12: a→d 직행 간선 8에 d→f 4를 더한 거리로 최단이 아니다.
13: 어떤 최단 경로 갱신 과정에서도 f의 최종 거리로 남지 않는다.

문제 14

다음 파이썬 프로그램의 실행 결과는?

def test(n):
    if(n<0):
        return 0
    return n+test(n-2)

print(test(5))

410

정답 및 해설

실행 결과는 9이다.

test(n)은 n이 음수가 될 때까지 n을 2씩 줄이며 더한다.

test(5) = 5 + test(3)
= 5 + 3 + test(1)
= 5 + 3 + 1 + test(-1)
= 9 + 0 = 9

5는 첫 항만 더하고 재귀 결과를 빠뜨린 값이다.
8은 5+3까지만 더하고 test(1)의 1을 빠뜨린 값이다.
10은 1부터 4까지의 합으로, 2씩 감소하는 5+3+1과 맞지 않는다.

문제 15

다음 그래프에 크루스칼(Kruskal) 알고리즘을 적용하여 최소 신장 트리를 만들 때, 마지막으로 최소 신장 트리에 포함되는 간선은? (단, (i, j)는 정점 i와 정점 j를 잇는 간선이다)

1(a, b)

2(a, c)

3(b, c)

4(c, d)

정답 및 해설

크루스칼 알고리즘에서 마지막으로 포함되는 간선은 (c, d)이다.

가중치 순으로 (a, c) 1, (h, g) 1, (a, e) 2, (b, c) 2, (e, g) 2를 채택하면 a, b, c, e, g, h가 하나로 묶인다. 가중치 3에서는 (h, e)가 사이클을 만들어 버리고 (g, f)를 채택한다.

가중치 4·5의 (h, c), (a, b), (c, g)는 모두 사이클을 만들고, d를 처음 연결하는 (c, d) 5가 일곱 번째 간선으로 채택되어 신장 트리가 완성된다.

(a, b): a와 b가 이미 (a, c)·(b, c)로 연결되어 있어 사이클을 만들므로 제외된다.
(a, c): 가중치 1로 가장 먼저 채택되는 간선이다.
(b, c): 가중치 2로 초반에 채택되는 간선이다.

문제 16

주어진 동전의 집합에 대하여 가장 적은 개수의 동전으로 거스름돈을 만드는 문제를 그리디 알고리즘을 이용해서 해결할 수 있는 경우는? (단, 거스름돈은 10의 배수이다)

110, 50, 60, 200

210, 40, 50, 100

310, 50, 100, 130

410, 50, 100, 200

정답 및 해설

그리디로 최소 개수를 보장하는 동전 집합은 10, 50, 100, 200이다.

각 동전이 바로 아래 동전의 배수(50=10×5, 100=50×2, 200=100×2)이면, 큰 동전 하나를 작은 동전 여러 개로 바꿔도 개수가 줄지 않으므로 큰 동전부터 고르는 그리디가 최적이 된다.

10, 50, 60, 200: 100원을 그리디는 60+10×4로 5개를 쓰지만 50×2의 2개가 최적이다.
10, 40, 50, 100: 80원을 그리디는 50+10×3으로 4개를 쓰지만 40×2의 2개가 최적이다.
10, 50, 100, 130: 150원을 그리디는 130+10×2로 3개를 쓰지만 100+50의 2개가 최적이다.

문제 17

다음 그림의 허프만 트리를 이용하여 인코딩한 일부 데이터의 코드를 문자열로 디코딩한 것은? (단, 노드의 왼쪽 자식 연결 간선에는 0, 오른쪽 자식 연결 간선에는 1이 부여된다)

압축 데이터 코드

1abbedcb

2abcde

3adebcb

4adebd

정답 및 해설

압축 코드를 디코딩한 문자열은 adebcb이다.

트리에서 왼쪽 0, 오른쪽 1을 따라가면 a=00, b=01, c=100, d=101, e=11이다. 허프만 코드는 접두어 코드이므로 앞에서부터 리프에 닿을 때마다 끊어 읽는다.

00 | 101 | 11 | 01 | 100 | 01 로 나누면 a, d, e, b, c, b가 된다.

abbedcb: 둘째 문자를 01로 읽었으나 실제 둘째 묶음은 101(d)이다.
abcde: 각 문자 코드를 순서대로 이으면 00 01 100 101 11이 되어 주어진 코드와 다르다.
adebd: 다섯째 묶음 100은 d가 아니라 c이고, 마지막 01(b)이 빠졌다.

문제 18

알파벳 순으로 정렬된 다음 배열에 대하여 이진 탐색으로 원소 P를 찾으려고 할 때, 비교해야 할 원소의 개수는?

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
C	E	G	H	J	L	M	N	P	Q	S	T	V	W	Z

정답 및 해설

원소 P를 찾기까지 4개의 원소와 비교한다.

이진 탐색은 범위의 중간 인덱스 $\lfloor (\mathrm{low}+\mathrm{high})/2 \rfloor$ 의 원소와 비교하며 범위를 절반씩 줄인다. 비교 순서는 N → T → Q → P이다.

범위 0~14, 중간 7(N) < P → 범위 8~14
중간 11(T) > P → 범위 8~10
중간 9(Q) > P → 범위 8~8
중간 8(P) 일치 → 탐색 종료

2개는 N, T까지만 비교한 상태로 아직 P에 도달하지 않았다.
3개는 Q까지만 비교한 상태로 범위 8~8의 P가 남아 있다.
5개는 P를 찾은 뒤에도 비교를 계속한 값으로, 일치하는 순간 탐색은 끝난다.

문제 19

그림과 같은 상태의 크기 13인 해시 테이블에 이중(double) 해싱 방법으로 원소 14를 삽입하고 이어서 원소 20을 삽입할 때, 원소 20의 저장 주소는? (단, 해시 함수 h(k,i) = (h₁(k) + i·h₂(k)) mod 13, 충돌 횟수 i = 0, 1, 2, ... 이고, h₁(k) = k mod 13, h₂(k) = 1 + (k mod 11)이다)

주소
0
1	66
2
3
4	69
5	18
6
7	72
8
9
10
11	50
12

410

정답 및 해설

원소 20은 주소 8에 저장된다.

이중 해싱은 충돌할 때마다 $h_2(k)$ 만큼 건너뛰며 빈 칸을 찾는다.

14 삽입: $h_1(14)=1$ , $h_2(14)=1+3=4$
i=0 → 1(66 있음), i=1 → 5(18 있음), i=2 → $(1+2 \cdot 4) \bmod 13 = 9$ (빈칸) → 14는 주소 9에 저장

20 삽입: $h_1(20)=7$ , $h_2(20)=1+9=10$
i=0 → 7(72 있음)
i=1 → $17 \bmod 13 = 4$ (69 있음)
i=2 → $27 \bmod 13 = 1$ (66 있음)
i=3 → $37 \bmod 13 = 11$ (50 있음)
i=4 → $47 \bmod 13 = 8$ (빈칸) → 저장

주소 6은 20의 탐사 순서 7, 4, 1, 11, 8에 나타나지 않는다.
주소 9는 앞서 삽입한 14가 차지한 자리이며 20의 탐사 순서에도 없다.
주소 10은 $h_2(20)$ 값과 혼동한 것으로, 20의 탐사 순서에 나타나지 않는다.

문제 20

다음 AVL 트리에 대해 노드 4, 5, 6을 차례대로 삽입한 결과는? (단, 리밸런싱을 위한 회전 횟수는 최소로 한다)

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

삽입 결과는 루트 7, 왼쪽 2(자식 1과 5, 5의 자식 4·6), 오른쪽 8(오른쪽 자식 9)인 트리이다.

4는 7의 왼쪽에 들어가 루트 8의 왼쪽 높이가 오른쪽보다 2 커지고, 경로가 왼쪽→오른쪽이므로 LR 이중 회전으로 7이 루트가 되어 7(2(1, 4), 8(-, 9))이 된다.

5는 4의 오른쪽에 들어가도 균형이 유지된다. 6이 5의 오른쪽에 들어가면 노드 4에서 RR 불균형이 생겨 좌회전 한 번으로 5(4, 6)이 된다.

루트가 6인 트리: 노드 7의 오른쪽에 9, 그 왼쪽에 8이 매달려 7의 좌우 높이 차가 2가 되므로 AVL 트리가 아니다.
루트 7의 왼쪽 자식이 5인 트리: 6 삽입 때 불균형은 노드 4에서만 생기므로 2가 5 아래로 내려가는 회전은 일어나지 않는다.
루트가 4인 트리: 4를 삽입할 때 LR 회전으로 루트가 7이 되며, 이후 삽입에서 루트가 다시 바뀌지 않는다.

문제 21

다음 파이썬 프로그램의 실행 결과는?

a=[29,88,60,26,40,74,43,22,61,40]
def partition():
    i = -1
    n = len(a)
    for j in range(0, n-2):
        if a[j] <= a[n-1]:
            i += 1
            b = a[i]
            a[i] = a[j]
            a[j] = b
    b = a[i+1]
    a[i+1] = a[n-1]
    a[n-1] = b

partition()
print(a)

129 22 26 40 40 74 43 88 61 60

229 22 40 26 40 74 43 88 61 60

329 26 22 40 40 74 43 60 61 88

429 26 40 22 40 74 43 88 61 60

정답 및 해설

실행 결과는 29 26 40 22 40 74 43 88 61 60이다.

마지막 원소 a[9]=40을 피벗으로 삼아 피벗 이하인 원소를 앞쪽으로 교환하는 로무토 분할이다. 단, 반복이 range(0, n-2)이므로 j=0~7만 검사한다.

j=0: 29 ≤ 40 → i=0, 제자리
j=3: 26 → i=1, a[1]과 교환 → 29 26 60 88 40 …
j=4: 40 → i=2, a[2]와 교환 → 29 26 40 88 60 …
j=7: 22 → i=3, a[3]과 교환 → 29 26 40 22 60 74 43 88 61 40
끝으로 a[4]와 a[9] 교환 → 29 26 40 22 40 74 43 88 61 60

29 22 26 40 40 74 43 88 61 60은 교환이 일어난 순서(26 → 40 → 22)를 무시하고 앞부분을 다르게 배치한 결과이다.
29 22 40 26 40 74 43 88 61 60은 22가 26보다 앞에 있어, 26이 먼저 a[1]로 교환되는 진행과 맞지 않는다.
29 26 22 40 40 74 43 60 61 88은 22와 40의 순서가 바뀌었고, 마지막 교환으로 a[4]의 60이 맨 끝에 와야 하는데 88이 와 있다.

문제 22

점근적 표기의 정의로 옳지 않은 것은?

O(g(n))

= {

f(n)

| 모든

n \ge n_0

에 대하여

f(n) \le c \cdot g(n)

인 양의 상수

c

와

n_0

가 존재한다}

\Omega(g(n))

= {

f(n)

| 모든

n \ge n_0

에 대하여

c \cdot g(n) \le f(n)

인 양의 상수

c

와

n_0

가 존재한다}

\Theta(g(n))

= {

f(n)

\lim_{n \to \infty} \frac{f(n)}{g(n)}

= 0}

\omega(g(n))

= {

f(n)

\lim_{n \to \infty} \frac{f(n)}{g(n)}

= ∞}

정답 및 해설

옳지 않은 것은 $\Theta(g(n))$ 를 극한값이 0인 함수의 집합으로 정의한 것이다.

$\lim_{n \to \infty} f(n)/g(n) = 0$ 은 f가 g보다 엄격히 느리게 증가한다는 뜻으로 little-o, 즉 $o(g(n))$ 의 정의이다.

$\Theta(g(n))$ 는 모든 $n \ge n_0$ 에 대하여 $c_1 g(n) \le f(n) \le c_2 g(n)$ 인 양의 상수 $c_1, c_2, n_0$ 가 존재하는 함수의 집합이다.

$O(g(n))$ 를 $c \cdot g(n)$ 이 f(n)의 상한이 되는 함수의 집합으로 정의한 것은 옳다.
$\Omega(g(n))$ 를 $c \cdot g(n)$ 이 f(n)의 하한이 되는 함수의 집합으로 정의한 것은 옳다.
$\omega(g(n))$ 를 극한값이 무한대인, 즉 f가 g보다 엄격히 빠르게 증가하는 함수의 집합으로 정의한 것은 옳다.

문제 23

배열 A를 오름차순으로 정렬하기 위해 5, 3, 1의 간격을 사용하여 셸(Shell) 정렬을 수행할 때, 간격 3에 대한 처리까지 수행을 완료한 후의 배열 A의 상태로 옳은 것은?

i	0	1	2	3	4	5	6	7	8	9	10
A[i]	9	18	26	21	4	17	13	2	6	24	8

14 9 13 26 6 8 18 24 2 17 21

26 4 2 8 13 9 18 17 21 24 26

39 2 6 13 4 17 21 8 26 24 18

49 18 26 4 17 21 2 6 13 8 24

정답 및 해설

간격 3까지 처리한 배열은 6 4 2 8 13 9 18 17 21 24 26이다.

셸 정렬은 간격 h만큼 떨어진 원소끼리 부분 배열을 만들어 각각 삽입 정렬한다.

간격 5: (9, 17, 8) → (8, 9, 17), (18, 13) → (13, 18), (26, 2) → (2, 26), (21, 6) → (6, 21), (4, 24) 유지
→ 8 13 2 6 4 9 18 26 21 24 17

간격 3: 인덱스 0·3·6·9의 (8, 6, 18, 24) → (6, 8, 18, 24), 인덱스 1·4·7·10의 (13, 4, 26, 17) → (4, 13, 17, 26), 인덱스 2·5·8의 (2, 9, 21) 유지
→ 6 4 2 8 13 9 18 17 21 24 26

4 9 13 26 6 8 18 24 2 17 21은 간격 3 부분 배열의 정렬 결과와 맞지 않는다. 인덱스 0에는 해당 그룹의 최솟값 6이 와야 한다.
9 2 6 13 4 17 21 8 26 24 18은 간격 5 처리를 건너뛰고 원래 배열에 간격 3만 적용한 결과이다.
9 18 26 4 17 21 2 6 13 8 24는 간격으로 떨어진 원소가 아니라 이웃한 세 원소씩 묶어 정렬한 결과이다.

문제 24

다음 C 코드에 해당하는 문자열 탐색 방법은? (단, s1은 입력 문자열, s2는 s1에서 찾고자 하는 패턴 문자열이고, n1은 s1의 길이, n2는 s2의 길이를 나타낸다)

int match(char *s1, char *s2) {
    int pt = 0, p = 0;
    while(pt != n1 && p != n2) {
        if (s1[pt] == s2[p]) {
            pt++;
            p++;
        } else {
            pt = pt - p + 1;
            p = 0;
        }
    }
    if (p == n2) return pt-p;
    else return -1;
}

1브루트－포스(brute-force) 알고리즘

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

3오토마타를 이용한 매칭 알고리즘

4보이어－무어(Boyer-Moore) 알고리즘

정답 및 해설

이 코드는 브루트-포스(brute-force) 알고리즘이다.

문자가 일치하면 두 포인터를 함께 전진하고, 불일치하면 pt = pt - p + 1로 이번 비교 시작 위치의 다음 칸으로 되돌아가 패턴을 처음(p = 0)부터 다시 비교한다. 모든 시작 위치를 하나씩 시도하므로 최악 $O(n_1 n_2)$ 이다.

라빈-카프는 패턴과 텍스트 구간의 해시값을 비교하는데, 코드에 해시 계산이 없다.
오토마타 매칭은 상태 전이표를 미리 만들어 텍스트를 되돌아가지 않고 한 번 훑는데, 코드는 pt를 뒤로 되돌린다.
보이어-무어는 패턴을 오른쪽 끝부터 비교하고 불일치 문자 정보로 크게 건너뛰는데, 코드는 왼쪽부터 비교하고 한 칸씩만 이동한다.

문제 25

다음은 텍스트에서 패턴과 일치하는 문자열을 찾기 위한 KMP(Knuth Morris Pratt) 알고리즘에서의 전처리 과정을 구현한 파이썬 프로그램이다. 패턴이 abcbabca인 경우, 아래 표의 (가) ∼ (라)에 들어갈 숫자를 바르게 연결한 것은?

def preprocess(pn: str):
    pt = 1
    k = 0
    pi = [0] * (len(pn) + 1)
    pi[pt-1] = -1
    pi[pt] = 0
    while pt != len(pn):
        if pn[pt] == pn[k]:
            k += 1
            pt += 1
            pi[pt] = k
        elif k == 0:
            pt += 1
            pi[pt] = k
        else:
            k = pi[k]
    print(pi)
pattern = 'abcbabca'
preprocess(pattern)

i	0	1	2	3	4	5	6	7	8
pn[i]	a	b	c	b	a	b	c	a
pi[i]	-1	0	0	0	0	(가)	(나)	(다)	(라)

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

11 1 1 1

21 2 3 1

31 2 3 0

43 3 3 0

정답 및 해설

(가)~(라)는 차례로 1, 2, 3, 1이다.

pi[i]는 패턴 앞 i글자에서 접두사와 접미사가 일치하는 최대 길이이다(pi[0] = -1).

pi[5]: abcba → a 일치 → 1
pi[6]: abcbab → ab 일치 → 2
pi[7]: abcbabc → abc 일치 → 3
pi[8]: abcbabca → 코드에서 pn[7]=a ≠ pn[3]=b라 k = pi[3] = 0으로 돌아간 뒤 pn[7] = pn[0] = a가 일치 → 1

1, 1, 1, 1은 (나)·(다)에서 일치 길이가 ab, abc로 늘어나는 것을 반영하지 않았다.
1, 2, 3, 0은 마지막 a가 첫 글자 a와 일치하는 것을 놓쳤다.
3, 3, 3, 0은 abcba의 접두사·접미사 일치가 a 하나뿐이라 (가)부터 맞지 않는다.

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

24년 1회차

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

문제 1

정점이 6개인 무방향 완전 그래프의 간선의 개수는?

212

315

421

정답 및 해설

정점이 6개인 무방향 완전 그래프의 간선 수는 15개이다.

완전 그래프는 서로 다른 모든 정점 쌍이 간선 하나로 연결되므로, 간선 수는 정점 2개를 고르는 조합의 수와 같다.

$\dfrac{n(n-1)}{2} = \dfrac{6 \times 5}{2} = 15$

6개는 정점 6개를 한 바퀴 잇는 사이클 그래프의 간선 수에 불과하다.
12개는 모든 정점의 차수가 4인 그래프의 간선 수로, 완전 그래프의 차수 5보다 작다.
21개는 정점이 7개인 완전 그래프의 간선 수이다.

문제 2

큐에 다음 함수를 적용한 결과로 (가) ∼ (다)에 들어갈 내용을 바르게 연결한 것은?

enqueue(e): 큐의 제 위치에 객체 e를 삽입한다.
dequeue(): 큐의 제 위치에서 객체를 삭제한다. 빈 큐일 경우에는 “error”를 출력한다.

연산순서	함수	출력	큐 저장공간
1	dequeue()	“error”	()
2	enqueue(1)		(1)
3	enqueue(2)		(1, 2)
4	enqueue(5)		(1, 2, 5)
5	dequeue()		(가)
6	enqueue(7)		(나)
7	dequeue()		(다)

(가) (나) (다)

1(1, 2) (1, 2, 7) (1, 2)

2(2, 5) (2, 5, 7) (5, 7)

3(2, 5) (5, 7) (7)

4(2, 5, 1) (2, 5, 1, 7) (5, 1, 7, 2)

정답 및 해설

(가)~(다)는 차례로 (2, 5) → (2, 5, 7) → (5, 7)이다.

큐는 선입선출(FIFO) 구조로, 삭제는 맨 앞에서, 삽입은 맨 뒤에서 일어난다.

(1, 2, 5)에서 dequeue로 맨 앞의 1이 빠져 (2, 5), enqueue(7)로 뒤에 7이 붙어 (2, 5, 7), 다시 dequeue로 맨 앞의 2가 빠져 (5, 7)이 된다.

(1, 2) → (1, 2, 7) → (1, 2)는 맨 뒤에서 꺼내는 스택(LIFO) 방식으로 처리한 결과이다.
(2, 5) → (5, 7) → (7)은 enqueue(7)에서도 원소를 하나 삭제한 것처럼 처리해 연산 정의와 맞지 않는다.
(2, 5, 1)로 시작하는 결과는 삭제한 1을 다시 뒤에 넣은 회전처럼 처리한 것으로, 삭제 연산의 정의와 맞지 않는다.

문제 3

다음 최대 힙에 대한 설명으로 옳지 않은 것은?

1완전 이진 트리이어야 한다.

2노드 A는 가장 큰 키 값을 가져야 한다.

3노드 B는 노드 F보다 큰 키 값을 가져야 한다.

4노드 B와 노드 D가 같은 키 값을 가질 수 있다.

정답 및 해설

옳지 않은 설명은 노드 B가 노드 F보다 큰 키 값을 가져야 한다는 것이다.

완전 이진 트리 조건: 힙은 배열로 표현하기 위해 마지막 레벨을 왼쪽부터 채운 완전 이진 트리여야 한다.
루트 A의 키: 모든 노드의 조상이므로 가장 큰 키를 가진다.
B와 D의 키가 같은 경우: 부모가 자식보다 크거나 같으면 되므로 같은 키도 허용된다.

문제 4

그리디 알고리즘으로 최적의 해가 보장되지 않는 것은?

1허프만(Huffman) 코딩

2최소 신장 트리

3다익스트라(Dijkstra) 최단 경로

40-1 배낭(knapsack) 문제

정답 및 해설

그리디로 최적해가 보장되지 않는 것은 0-1 배낭 문제이다.

허프만 코딩은 빈도가 가장 작은 두 노드를 반복 병합하는 그리디로 최적 접두 코드를 만든다.
최소 신장 트리는 크루스칼·프림 알고리즘이 가장 가벼운 안전 간선을 고르는 그리디로 최적해를 보장한다.
다익스트라 최단 경로는 간선 가중치가 음수가 아니면 거리가 가장 짧은 정점부터 확정하는 그리디로 최적해를 보장한다.

문제 5

다음 C 코드에서 사용한 재귀 알고리즘의 시간 복잡도는? (단, n은 배열의 크기이다)

int S(int A[ ], int n){
    if( n <= 0 )  return 0;
    else return A[n-1] + S(A, n/2);
}

\Theta(\log n)

\Theta(n)

\Theta(n\log n)

\Theta(n^2)

정답 및 해설

이 재귀 알고리즘의 시간 복잡도는 $\Theta(\log n)$ 이다.

호출 한 번마다 덧셈 하나의 상수 작업을 하고, 크기를 절반으로 줄여 한 번만 재귀하므로 점화식은 $T(n) = T(n/2) + \Theta(1)$ 이다.

n이 0 이하가 될 때까지 절반씩 줄어드는 횟수는 약 $\log_2 n$ 회이므로 전체 시간은 $\Theta(\log n)$ 이다.

$\Theta(n)$ 은 크기를 1씩 줄이는 재귀 $T(n)=T(n-1)+\Theta(1)$ 의 복잡도이다.
$\Theta(n\log n)$ 은 두 번 재귀하고 선형 작업을 하는 $T(n)=2T(n/2)+\Theta(n)$ 의 복잡도이다.
$\Theta(n^2)$ 은 크기를 1씩 줄이며 매번 선형 작업을 하는 $T(n)=T(n-1)+\Theta(n)$ 의 복잡도이다.

문제 6

1부터 n까지 합을 구하는 다음 파이썬 프로그램의 빈칸에 들어갈 내용은? (단, n은 n≥1인 정수이다)

def sum(n):
    ret = 0
    for (          ):
        ret += i
    return ret

1i in range(-1, n+1)

2i in range(0, n)

3i in range(1, n)

4i in range(1, n+1)

정답 및 해설

빈칸에는 i in range(1, n+1)이 들어간다.

파이썬 range(a, b)는 a부터 b-1까지의 정수를 만들므로, 1부터 n까지 더하려면 끝값을 n+1로 주어야 한다.

range(-1, n+1)은 -1과 0이 함께 더해져 결과가 1 작아진다.
range(0, n)은 0부터 n-1까지라 마지막 n이 빠진다.
range(1, n)은 1부터 n-1까지라 마지막 n이 빠진다.

문제 7

연산 이론상의 문제 유형에 대한 설명으로 옳지 않은 것은?

1P는 다항식 시간에 해결할 수 있는 문제군이다.

2NP는 비결정론적 다항식 시간에 해결할 수 있는 문제군이다.

3어떤 NP-Complete 문제에 대해서 다항식 시간에 해결할 수 있는 알고리즘을 찾아내면, 다른 모든 NP-Complete 문제도 다항식 시간에 해를 구할 수 있다.

4NP-Complete 문제들 중에는 NP에 속하지 않는 문제도 있다.

정답 및 해설

옳지 않은 것은 NP-Complete 문제 중에 NP에 속하지 않는 문제가 있다는 설명이다.

P를 다항식 시간에 해결할 수 있는 문제군으로 설명한 것은 옳다.
NP를 비결정론적 다항식 시간에 해결할 수 있는(해를 다항식 시간에 검증할 수 있는) 문제군으로 설명한 것은 옳다.
모든 NP 문제가 각 NP-Complete 문제로 환원되므로, 하나를 다항식 시간에 풀면 다른 NP-Complete 문제도 다항식 시간에 풀린다는 설명은 옳다.

문제 8

다음 fib() 함수는 피보나치 수열을 계산하는 C 코드이다. fib(17)을 실행할 때 fib(8)과 fib(10)이 각각 호출되는 횟수를 바르게 연결한 것은?

int fib(int n){
    if(n==1 || n==2) return 1;
    else return (fib(n-1) + fib(n-2));
}

fib(8) fib(10)

152번 13번

252번 21번

355번 13번

455번 21번

정답 및 해설

fib(17) 실행 시 fib(8)은 55회, fib(10)은 21회 호출된다.

$C(8)=F(10)=55$
$C(10)=F(8)=21$

52회·13회 조합은 두 값이 모두 틀리다. 13회는 fib(11)의 호출 횟수이다.
52회·21회 조합은 fib(10)은 맞지만 fib(8)을 55회가 아닌 52회로 잡아 틀리다.
55회·13회 조합은 fib(8)은 맞지만 13회는 fib(11)의 호출 횟수이다.

문제 9

다음 이진 검색 트리에서 노드 이동 또는 포인터 변경의 횟수를 최소화하면서 노드를 삭제하는 과정의 설명으로 옳지 않은 것은?

1노드 8을 삭제하려면 노드 15에서 노드 8을 가리키는 포인터를 NIL(또는 NULL)로 변경한다.

2노드 25를 삭제하려면 그 자리에 노드 30을 놓는다.

3노드 50을 삭제하려면 노드 40이 노드 60을 직접 가리키도록 포인터를 변경한다.

4노드 60을 삭제하려면 그 자리에 노드 55 또는 노드 66을 놓는다.

정답 및 해설

옳지 않은 설명은 노드 25를 삭제할 때 그 자리에 노드 30을 놓는다는 것이다.

노드 8 삭제: 자식이 없는 리프이므로 부모 15의 해당 포인터만 NIL로 바꾸면 된다.
노드 50 삭제: 오른쪽 자식 60 하나만 가지므로 부모 40이 60을 직접 가리키게 하면 된다.
노드 60 삭제: 자식이 둘이므로 선행자 55나 후계자 66을 그 자리에 놓는다.

문제 10

레드－블랙 트리로 옳은 것은? (단, 외부 노드(leaf)는 표시하지 않고, 블랙 노드는 검정색으로, 레드 노드는 흰색으로 나타낸 것이다)

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

레드-블랙 트리는 루트 35 아래 레드 20(자식 블랙 10·블랙 25, 25의 오른쪽 레드 30)과 블랙 50(자식 레드 40·레드 60)이 놓인 트리이다.

이 트리는 이진 검색 트리 순서를 지키고, 레드 노드의 자식이 모두 블랙이며, 루트에서 모든 외부 노드까지의 블랙 노드 수가 2개로 같다.

루트 30의 왼쪽 블랙 10 아래 레드 20, 그 아래 레드 25가 이어진 트리: 레드 노드가 연속해 레드 자식을 가질 수 없다는 조건을 어긴다.
루트 30의 오른쪽 블랙 65 아래 레드 40, 그 아래 블랙 50이 있는 트리: 50을 거치는 경로만 블랙 노드가 3개가 되어 블랙 높이가 다르다.
루트 30의 오른쪽 레드 50 아래 블랙 40의 오른쪽에 55가 있는 트리: 55가 50의 왼쪽 서브트리에 있어 이진 검색 트리 순서를 어긴다.

문제 11

해시 테이블에 대한 설명으로 옳지 않은 것은?

1충돌이 발생하지 않는다면 상수 시간

O(1)

에 검색과 저장이 가능하다.

2키 값을 입력으로 받아 해시 테이블상의 주소를 리턴하는 해시 함수는 나누기 방법뿐만 아니라 곱하기 방법으로도 만들 수 있다.

3저장 원소의 총수를 해시 테이블의 크기로 나눈 적재율(load factor)은 해시 테이블의 성능에 중요한 영향을 미친다.

4충돌을 해결하기 위한 별도 체이닝과 오픈 주소 방법은 모두 추가적인 저장 공간을 필요로 하지 않는다.

정답 및 해설

옳지 않은 것은 별도 체이닝과 오픈 주소 방법 모두 추가 저장 공간이 필요 없다는 설명이다.

충돌이 없으면 해시 함수 계산 한 번으로 주소가 정해지므로 검색·저장이 $O(1)$ 이라는 설명은 옳다.
해시 함수를 나누기(제산) 방법뿐 아니라 곱하기(승산) 방법으로도 만들 수 있다는 설명은 옳다.
적재율이 높을수록 충돌이 잦아져 성능이 떨어지므로 적재율이 성능에 중요한 영향을 준다는 설명은 옳다.

문제 12

프림(Prim) 알고리즘을 적용하여 다음 그래프의 정점 A에서 시작하는 최소 신장 트리를 구할 때, 마지막으로 선택되는 정점은?

정답 및 해설

프림 알고리즘으로 선택되는 마지막 정점은 C이다.

이어서 F–G 1로 G가 붙고, 마지막으로 G–C 2로 C가 선택된다.

F: 다섯 번째로 선택되며 B–F 간선 9가 D–C 10보다 작아 C보다 먼저 붙는다.
G: F가 들어온 직후 가중치 1인 F–G 간선으로 여섯 번째에 선택된다.
H: E가 들어온 직후 E–H 간선 3으로 네 번째에 선택된다.

문제 13

다음 그래프에 다익스트라 알고리즘을 적용하여 구한 정점 a에서 정점 f까지 최단 경로의 거리는?

110

211

312

413

정답 및 해설

정점 a에서 f까지의 최단 거리는 10이며, 경로는 a→b→c→e→d→f이다.

a에서 b까지 1, b→c 간선 2로 c까지 3이 되어 직행 간선 a→c 5보다 짧다. c→e 1로 e까지 4가 되고, e→d 2로 d까지 6이 되어 a→d 8보다 짧다.

f로 가는 간선은 d→f 4와 e→f 7이므로 6+4=10이 4+7=11보다 작다.

11: e에서 f로 바로 가는 경로의 거리로, d를 거치는 경로보다 1 길다.
12: a→d 직행 간선 8에 d→f 4를 더한 거리로 최단이 아니다.
13: 어떤 최단 경로 갱신 과정에서도 f의 최종 거리로 남지 않는다.

문제 14

다음 파이썬 프로그램의 실행 결과는?

def test(n):
    if(n<0):
        return 0
    return n+test(n-2)

print(test(5))

410

정답 및 해설

실행 결과는 9이다.

test(n)은 n이 음수가 될 때까지 n을 2씩 줄이며 더한다.

test(5) = 5 + test(3)
= 5 + 3 + test(1)
= 5 + 3 + 1 + test(-1)
= 9 + 0 = 9

5는 첫 항만 더하고 재귀 결과를 빠뜨린 값이다.
8은 5+3까지만 더하고 test(1)의 1을 빠뜨린 값이다.
10은 1부터 4까지의 합으로, 2씩 감소하는 5+3+1과 맞지 않는다.

문제 15

1(a, b)

2(a, c)

3(b, c)

4(c, d)

정답 및 해설

크루스칼 알고리즘에서 마지막으로 포함되는 간선은 (c, d)이다.

가중치 4·5의 (h, c), (a, b), (c, g)는 모두 사이클을 만들고, d를 처음 연결하는 (c, d) 5가 일곱 번째 간선으로 채택되어 신장 트리가 완성된다.

(a, b): a와 b가 이미 (a, c)·(b, c)로 연결되어 있어 사이클을 만들므로 제외된다.
(a, c): 가중치 1로 가장 먼저 채택되는 간선이다.
(b, c): 가중치 2로 초반에 채택되는 간선이다.

문제 16

110, 50, 60, 200

210, 40, 50, 100

310, 50, 100, 130

410, 50, 100, 200

정답 및 해설

그리디로 최소 개수를 보장하는 동전 집합은 10, 50, 100, 200이다.

10, 50, 60, 200: 100원을 그리디는 60+10×4로 5개를 쓰지만 50×2의 2개가 최적이다.
10, 40, 50, 100: 80원을 그리디는 50+10×3으로 4개를 쓰지만 40×2의 2개가 최적이다.
10, 50, 100, 130: 150원을 그리디는 130+10×2로 3개를 쓰지만 100+50의 2개가 최적이다.

문제 17

압축 데이터 코드

1abbedcb

2abcde

3adebcb

4adebd

정답 및 해설

압축 코드를 디코딩한 문자열은 adebcb이다.

트리에서 왼쪽 0, 오른쪽 1을 따라가면 a=00, b=01, c=100, d=101, e=11이다. 허프만 코드는 접두어 코드이므로 앞에서부터 리프에 닿을 때마다 끊어 읽는다.

00 | 101 | 11 | 01 | 100 | 01 로 나누면 a, d, e, b, c, b가 된다.

abbedcb: 둘째 문자를 01로 읽었으나 실제 둘째 묶음은 101(d)이다.
abcde: 각 문자 코드를 순서대로 이으면 00 01 100 101 11이 되어 주어진 코드와 다르다.
adebd: 다섯째 묶음 100은 d가 아니라 c이고, 마지막 01(b)이 빠졌다.

문제 18

알파벳 순으로 정렬된 다음 배열에 대하여 이진 탐색으로 원소 P를 찾으려고 할 때, 비교해야 할 원소의 개수는?

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
C	E	G	H	J	L	M	N	P	Q	S	T	V	W	Z

정답 및 해설

원소 P를 찾기까지 4개의 원소와 비교한다.

이진 탐색은 범위의 중간 인덱스 $\lfloor (\mathrm{low}+\mathrm{high})/2 \rfloor$ 의 원소와 비교하며 범위를 절반씩 줄인다. 비교 순서는 N → T → Q → P이다.

범위 0~14, 중간 7(N) < P → 범위 8~14
중간 11(T) > P → 범위 8~10
중간 9(Q) > P → 범위 8~8
중간 8(P) 일치 → 탐색 종료

2개는 N, T까지만 비교한 상태로 아직 P에 도달하지 않았다.
3개는 Q까지만 비교한 상태로 범위 8~8의 P가 남아 있다.
5개는 P를 찾은 뒤에도 비교를 계속한 값으로, 일치하는 순간 탐색은 끝난다.

문제 19

주소
0
1	66
2
3
4	69
5	18
6
7	72
8
9
10
11	50
12

410

정답 및 해설

원소 20은 주소 8에 저장된다.

이중 해싱은 충돌할 때마다 $h_2(k)$ 만큼 건너뛰며 빈 칸을 찾는다.

14 삽입: $h_1(14)=1$ , $h_2(14)=1+3=4$
i=0 → 1(66 있음), i=1 → 5(18 있음), i=2 → $(1+2 \cdot 4) \bmod 13 = 9$ (빈칸) → 14는 주소 9에 저장

주소 6은 20의 탐사 순서 7, 4, 1, 11, 8에 나타나지 않는다.
주소 9는 앞서 삽입한 14가 차지한 자리이며 20의 탐사 순서에도 없다.
주소 10은 $h_2(20)$ 값과 혼동한 것으로, 20의 탐사 순서에 나타나지 않는다.

문제 20

다음 AVL 트리에 대해 노드 4, 5, 6을 차례대로 삽입한 결과는? (단, 리밸런싱을 위한 회전 횟수는 최소로 한다)

1[그림]

2[그림]

3[그림]

4[그림]

정답 및 해설

삽입 결과는 루트 7, 왼쪽 2(자식 1과 5, 5의 자식 4·6), 오른쪽 8(오른쪽 자식 9)인 트리이다.

5는 4의 오른쪽에 들어가도 균형이 유지된다. 6이 5의 오른쪽에 들어가면 노드 4에서 RR 불균형이 생겨 좌회전 한 번으로 5(4, 6)이 된다.

루트가 6인 트리: 노드 7의 오른쪽에 9, 그 왼쪽에 8이 매달려 7의 좌우 높이 차가 2가 되므로 AVL 트리가 아니다.
루트 7의 왼쪽 자식이 5인 트리: 6 삽입 때 불균형은 노드 4에서만 생기므로 2가 5 아래로 내려가는 회전은 일어나지 않는다.
루트가 4인 트리: 4를 삽입할 때 LR 회전으로 루트가 7이 되며, 이후 삽입에서 루트가 다시 바뀌지 않는다.

문제 21

다음 파이썬 프로그램의 실행 결과는?

a=[29,88,60,26,40,74,43,22,61,40]
def partition():
    i = -1
    n = len(a)
    for j in range(0, n-2):
        if a[j] <= a[n-1]:
            i += 1
            b = a[i]
            a[i] = a[j]
            a[j] = b
    b = a[i+1]
    a[i+1] = a[n-1]
    a[n-1] = b

partition()
print(a)

129 22 26 40 40 74 43 88 61 60

229 22 40 26 40 74 43 88 61 60

329 26 22 40 40 74 43 60 61 88

429 26 40 22 40 74 43 88 61 60

정답 및 해설

실행 결과는 29 26 40 22 40 74 43 88 61 60이다.

마지막 원소 a[9]=40을 피벗으로 삼아 피벗 이하인 원소를 앞쪽으로 교환하는 로무토 분할이다. 단, 반복이 range(0, n-2)이므로 j=0~7만 검사한다.

29 22 26 40 40 74 43 88 61 60은 교환이 일어난 순서(26 → 40 → 22)를 무시하고 앞부분을 다르게 배치한 결과이다.
29 22 40 26 40 74 43 88 61 60은 22가 26보다 앞에 있어, 26이 먼저 a[1]로 교환되는 진행과 맞지 않는다.
29 26 22 40 40 74 43 60 61 88은 22와 40의 순서가 바뀌었고, 마지막 교환으로 a[4]의 60이 맨 끝에 와야 하는데 88이 와 있다.

문제 22

점근적 표기의 정의로 옳지 않은 것은?

O(g(n))

= {

f(n)

| 모든

n \ge n_0

에 대하여

f(n) \le c \cdot g(n)

인 양의 상수

c

와

n_0

가 존재한다}

\Omega(g(n))

= {

f(n)

| 모든

n \ge n_0

에 대하여

c \cdot g(n) \le f(n)

인 양의 상수

c

와

n_0

가 존재한다}

\Theta(g(n))

= {

f(n)

\lim_{n \to \infty} \frac{f(n)}{g(n)}

= 0}

\omega(g(n))

= {

f(n)

\lim_{n \to \infty} \frac{f(n)}{g(n)}

= ∞}

정답 및 해설

옳지 않은 것은 $\Theta(g(n))$ 를 극한값이 0인 함수의 집합으로 정의한 것이다.

$\lim_{n \to \infty} f(n)/g(n) = 0$ 은 f가 g보다 엄격히 느리게 증가한다는 뜻으로 little-o, 즉 $o(g(n))$ 의 정의이다.

$\Theta(g(n))$ 는 모든 $n \ge n_0$ 에 대하여 $c_1 g(n) \le f(n) \le c_2 g(n)$ 인 양의 상수 $c_1, c_2, n_0$ 가 존재하는 함수의 집합이다.

$O(g(n))$ 를 $c \cdot g(n)$ 이 f(n)의 상한이 되는 함수의 집합으로 정의한 것은 옳다.
$\Omega(g(n))$ 를 $c \cdot g(n)$ 이 f(n)의 하한이 되는 함수의 집합으로 정의한 것은 옳다.
$\omega(g(n))$ 를 극한값이 무한대인, 즉 f가 g보다 엄격히 빠르게 증가하는 함수의 집합으로 정의한 것은 옳다.

문제 23

i	0	1	2	3	4	5	6	7	8	9	10
A[i]	9	18	26	21	4	17	13	2	6	24	8

14 9 13 26 6 8 18 24 2 17 21

26 4 2 8 13 9 18 17 21 24 26

39 2 6 13 4 17 21 8 26 24 18

49 18 26 4 17 21 2 6 13 8 24

정답 및 해설

간격 3까지 처리한 배열은 6 4 2 8 13 9 18 17 21 24 26이다.

셸 정렬은 간격 h만큼 떨어진 원소끼리 부분 배열을 만들어 각각 삽입 정렬한다.

간격 5: (9, 17, 8) → (8, 9, 17), (18, 13) → (13, 18), (26, 2) → (2, 26), (21, 6) → (6, 21), (4, 24) 유지
→ 8 13 2 6 4 9 18 26 21 24 17

4 9 13 26 6 8 18 24 2 17 21은 간격 3 부분 배열의 정렬 결과와 맞지 않는다. 인덱스 0에는 해당 그룹의 최솟값 6이 와야 한다.
9 2 6 13 4 17 21 8 26 24 18은 간격 5 처리를 건너뛰고 원래 배열에 간격 3만 적용한 결과이다.
9 18 26 4 17 21 2 6 13 8 24는 간격으로 떨어진 원소가 아니라 이웃한 세 원소씩 묶어 정렬한 결과이다.

문제 24

int match(char *s1, char *s2) {
    int pt = 0, p = 0;
    while(pt != n1 && p != n2) {
        if (s1[pt] == s2[p]) {
            pt++;
            p++;
        } else {
            pt = pt - p + 1;
            p = 0;
        }
    }
    if (p == n2) return pt-p;
    else return -1;
}

1브루트－포스(brute-force) 알고리즘

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

3오토마타를 이용한 매칭 알고리즘

4보이어－무어(Boyer-Moore) 알고리즘

정답 및 해설

이 코드는 브루트-포스(brute-force) 알고리즘이다.

라빈-카프는 패턴과 텍스트 구간의 해시값을 비교하는데, 코드에 해시 계산이 없다.
오토마타 매칭은 상태 전이표를 미리 만들어 텍스트를 되돌아가지 않고 한 번 훑는데, 코드는 pt를 뒤로 되돌린다.
보이어-무어는 패턴을 오른쪽 끝부터 비교하고 불일치 문자 정보로 크게 건너뛰는데, 코드는 왼쪽부터 비교하고 한 칸씩만 이동한다.

문제 25

def preprocess(pn: str):
    pt = 1
    k = 0
    pi = [0] * (len(pn) + 1)
    pi[pt-1] = -1
    pi[pt] = 0
    while pt != len(pn):
        if pn[pt] == pn[k]:
            k += 1
            pt += 1
            pi[pt] = k
        elif k == 0:
            pt += 1
            pi[pt] = k
        else:
            k = pi[k]
    print(pi)
pattern = 'abcbabca'
preprocess(pattern)

i	0	1	2	3	4	5	6	7	8
pn[i]	a	b	c	b	a	b	c	a
pi[i]	-1	0	0	0	0	(가)	(나)	(다)	(라)

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

11 1 1 1

21 2 3 1

31 2 3 0

43 3 3 0

정답 및 해설

(가)~(라)는 차례로 1, 2, 3, 1이다.

pi[i]는 패턴 앞 i글자에서 접두사와 접미사가 일치하는 최대 길이이다(pi[0] = -1).

1, 1, 1, 1은 (나)·(다)에서 일치 길이가 ab, abc로 늘어나는 것을 반영하지 않았다.
1, 2, 3, 0은 마지막 a가 첫 글자 a와 일치하는 것을 놓쳤다.
3, 3, 3, 0은 abcba의 접두사·접미사 일치가 a 하나뿐이라 (가)부터 맞지 않는다.