9급 데이터 알고리즘 기출문제 해설·정답

9급 데이터 알고리즘 기출문제 해설

총 80문항 · 문제·정답·해설·개념 무료 학습

이 회차는 80문항입니다. 자료를 읽고 푸는 문항이 48문항입니다. 풀이가 붙은 문항이 80문항입니다.

▶ CertLab에서 풀어보기

알고리즘의 조건에 대한 설명으로 옳은 것만을 모두 고르면?

ㄱ. 모든 명령은 모호하지 않고 명확해야 한다.

ㄴ. 모든 명령은 실행 가능한 연산이어야 한다.

ㄷ. 모든 명령은 반복적으로 무한히 실행되어야 한다.

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

정답 2번

🔍 보기별 해설

ㄱ은 명령이 모호하지 않아야 한다는 명확성 조건으로 참이다. 다만 실행 가능성을 말한 ㄴ도 참인데 그것이 빠져 있어 참인 진술을 하나 놓친 묶음이므로 옳지 않다.
명령이 모호하지 않아야 한다는 명확성과 실제로 수행할 수 있는 연산이어야 한다는 실행 가능성은 둘 다 알고리즘의 조건이다. 무한 반복을 뺀 두 진술의 묶음이 맞다.
ㄴ은 참이지만 ㄷ은 알고리즘이 유한한 단계를 거친 뒤 반드시 끝나야 한다는 종료성과 정면으로 어긋난다. 참인 ㄱ까지 빠진 묶음이므로 옳지 않다.
세 진술 가운데 ㄷ은 무한히 실행하라는 뜻이어서 거짓이다. 알고리즘은 입력을 받아 유한 단계 뒤에 출력을 내고 끝나야 하므로 ㄷ을 포함한 묶음은 옳지 않다.

🧮 풀이

甲은 요리 레시피에 「적당히 볶는다」라고만 적힌 것을 보고 사람마다 다르게 읽히는 명령은 알고리즘이 될 수 없다고 생각했다. 「중불에서 3분 볶는다」처럼 한 가지로만 읽히는 문장으로 고쳐 적어 두었다.
甲은 길 찾기 순서도에서 「왼쪽으로 돈다」는 명령이 뜻도 분명하고 실제로 할 수 있어 명확성과 실행 가능성을 함께 갖췄다고 표시했다. 반면 「목적지를 마음으로 느낀다」는 칸은 수행할 수 없어 지우고 다른 명령으로 바꿔 넣었다.
甲은 로봇 청소기가 방을 끝없이 돌기만 하고 멈추지 않는 동작 기록을 보았다. 동작 하나하나는 실행할 수 있어도 끝나지 않는 명령의 나열은 알고리즘이 아니라고 보고 종료 조건 한 줄을 추가했다.
甲은 세 진술을 카드 한 장씩에 옮겨 순서도에 하나씩 대 보았다. 명확성과 실행 가능성 카드는 통과했지만 무한 실행 카드는 유한 단계 뒤에 끝나야 한다는 조건과 맞지 않아 옆으로 치워 두었다.

알고리즘은 명령이 명확하고 실행 가능해야 하며 유한한 단계 안에 끝나야 한다. 무한 반복은 조건이 아니다. 정답은 2번.

알고리즘의 수행 시간 분석에 대한 설명으로 옳지 않은 것은?

1. 알고리즘의 수행 시간은 컴퓨터 성능에 관계없이 명확하게 정의되어야 한다.
2. 알고리즘의 시간복잡도는 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다.
3. 최선의 경우의 알고리즘 수행 시간은 모든 입력의 수행 시간에 대한 상한이 된다.
4. 알고리즘의 수행 시간 분석에는 최악의 경우, 평균의 경우, 최선의 경우가 있다.

정답 3번

🔍 보기별 해설

실제로 재는 초 단위 시간은 컴퓨터마다 달라 알고리즘 자체의 성능을 견주기 어렵다. 그래서 하드웨어와 무관하게 정의해야 한다는 원칙을 말한 진술이므로 맞다.
시간복잡도는 덧셈이나 비교 같은 기본 연산이 몇 번 일어나는지를 입력 크기 n에 대한 함수로 나타낸 것이다. 이렇게 셈해야 기계와 상관없이 견줄 수 있으므로 맞다.
가장 유리한 입력에서의 수행 시간은 다른 입력들의 수행 시간보다 짧거나 같은 하한이 된다. 모든 입력을 덮는 상한은 가장 불리한 최악의 경우가 맡으므로 옳지 않다(정답).
입력이 가장 불리한 최악, 가능한 모든 입력의 기댓값을 보는 평균, 가장 유리한 최선의 세 관점으로 수행 시간을 분석한다. 시간복잡도 분석의 표준 구분이므로 맞다.

🧮 풀이

甲은 같은 정렬 프로그램을 오래된 노트북과 최신 서버에서 돌려 걸린 시간이 열 배 넘게 다른 것을 보았다. 초 단위 값은 기계에 따라 흔들리니 연산 횟수로 세어야 한다고 적어 두었다.
甲은 배열에서 값을 찾는 반복문을 한 줄씩 짚으며 비교 연산이 몇 번 실행되는지 세었다. 원소가 n개면 최대 n번이라는 식을 만들어 입력 크기에 대한 함수로 공책에 옮겨 적었다.
甲은 이미 정렬된 배열에 삽입 정렬을 돌렸을 때 비교가 n번 정도로 끝나는 것을 확인했다. 이 값은 가장 유리한 경우라 다른 입력의 시간보다 작아 상한이 아닌 하한임을 표에 표시했다.
甲은 순차 탐색에서 찾는 값이 맨 앞에 있을 때와 맨 뒤에 있을 때, 중간에 있을 때의 비교 횟수를 나눠 세었다. 각각 최선, 최악, 평균이라 이름 붙여 세 칸짜리 표에 정리해 두었다.

최선의 경우는 다른 입력의 수행 시간보다 짧은 하한이고, 모든 입력을 덮는 상한은 최악의 경우가 맡는다.

다음은 그래프에서 너비 우선 탐색(breadth first search) 알고리즘이 동작하는 과정이다. (가) ～ (다)에 들어갈 내용을 바르게 연결한 것은?

[단계 1] 시작 정점을 ‘visited’로 표시하고 (가) 에(서) (나) 한다.

[단계 2] (가) 에(서) 정점을 (다) 하고, 제거한 정점의 인접 정점 중 아직 방문하지 않은 곳들은 ‘visited’로 표시하고 (가) 에(서) (나) 한다.

[단계 3] (가) 가/이 비워질 때까지 [단계 2]를 반복한다. (가) (나) (다)

1. Queue Dequeue Enqueue
2. Queue Enqueue Dequeue
3. Stack Pop Push
4. Stack Push Pop

정답 2번

🔍 보기별 해설

너비 우선 탐색이 큐를 쓴다는 점은 맞지만 (나)와 (다)가 서로 뒤바뀌었다. 시작 정점을 큐에 넣는 동작이 먼저이고 꺼내는 동작이 그다음인데 넣기 자리에 꺼내기를 써서 옳지 않다.
너비 우선 탐색은 가까운 정점부터 차례로 다루려고 먼저 들어간 것을 먼저 꺼내는 큐를 쓴다. 시작 정점과 새 인접 정점은 큐에 넣고 정점은 큐에서 꺼내는 순서이므로 옳다(정답).
스택은 나중에 넣은 것을 먼저 꺼내는 구조라 가장 깊은 곳까지 파고드는 깊이 우선 탐색에 어울린다. 너비 우선 탐색에 쓰는 자료구조가 아니므로 옳지 않다.
넣고 꺼내는 이름은 짝지어 놓았지만 자료구조가 후입선출이라 방문 순서가 층별로 퍼지지 않고 깊이를 따라간다. 너비 우선 탐색에는 큐가 필요하므로 옳지 않다.

🧮 풀이

甲은 은행 창구에서 번호표를 뽑은 사람이 아직 없는데 번호부터 부르는 순서도를 그려 놓고 이상하다고 느꼈다. 줄에 세우는 일이 앞이고 부르는 일이 뒤이니 두 동작 이름을 맞바꿔 다시 적었다.
甲은 놀이공원 입구에서 먼저 도착한 사람이 먼저 입장하는 줄을 한참 관찰했다. 줄 끝에 서는 것을 넣기, 맨 앞 사람이 들어가는 것을 꺼내기로 나누어 적고 탐색 순서와 견주어 보았다.
甲은 접시를 쌓아 두고 맨 위 접시부터 집어 쓰는 식당 주방을 지켜보았다. 마지막에 올린 것을 먼저 쓰는 이 방식이 Push와 Pop으로 부르는 스택의 동작임을 공책에 메모했다.
甲은 미로에서 갈림길을 만날 때마다 한 길로 끝까지 들어가는 자신의 걸음을 지도에 그렸다. 스택에 좌표를 넣었다 꺼내는 이 경로가 층별로 퍼지지 않고 깊게 파고드는 모양임을 표시했다.

너비 우선 탐색은 큐를 쓴다. 시작 정점과 새 인접 정점은 Enqueue로 넣고 정점은 Dequeue로 꺼낸다.

입력 크기 n 에 대한 수행 횟수를 빅오(big-oh) 표기법으로 표현했을 때 옳지 않은 것은?

1. n^4 ＋2^n ＋5 - > O (n^4)
2. 3n^2 ＋8n＋7 - > O (n^2)
3. 2n^2 ＋2n log n＋4n - > O (n^2)
4. 3n＋5n log n＋2 - > O (n log n)

정답 1번

🔍 보기별 해설

지수 함수 2^n은 n이 커질수록 다항식 n^4보다 훨씬 빠르게 커져 결국 가장 큰 항이 된다. 이 식의 빅오는 2^n이어야 하는데 n^4으로 적었으므로 옳지 않다(정답).
3n^2+8n+7에서 가장 빨리 자라는 항은 n^2이고 앞의 계수 3과 낮은 차수의 항은 버린다. 결과가 O(n^2)이 되는 올바른 표기이므로 맞다.
2n^2, 2n log n, 4n 가운데 n^2이 가장 빨리 커지고 n log n과 n은 그보다 작다. 계수를 떼면 O(n^2)이 남는 올바른 표기이므로 맞다.
3n, 5n log n, 2 중에서는 n log n이 가장 빨리 커지므로 나머지 항과 계수를 버린다. 남는 O(n log n)이 정확한 표기이므로 맞다.

🧮 풀이

甲은 n이 10이면 n^4이 만이고 2^n이 천이십사이지만 n이 40이 되면 2^n이 훨씬 커지는 표를 만들었다. 큰 n에서는 지수 항이 지배하니 결과를 O(2^n)으로 고쳐 적었다.
甲은 3n^2+8n+7에 n=1000을 넣어 각 항이 내는 값을 견주었다. n^2 항이 삼백만인데 나머지는 팔천 남짓이라 수백 배 차이가 나는 것을 보고 계수를 뗀 n^2만 남겼다.
甲은 2n^2과 2n log n을 n=1024에서 견주어 앞의 값은 약 이백만이고 뒤의 값은 약 이만임을 계산했다. n^2이 지배한다고 보고 결과를 O(n^2)로 적어 두었다.
甲은 3n+5n log n+2에서 n log n과 n을 나란히 놓고 n이 커질수록 log n 배만큼 벌어지는 것을 그래프로 그렸다. 더 빠르게 자라는 n log n만 남기고 상수와 계수를 지웠다.

빅오는 가장 빨리 커지는 항만 남긴다. 2^n은 n^4보다 빨리 커지므로 결과는 O(n^4)이 아니라 O(2^n)이다.

다음 의사코드(pseudo code)가 설명하는 정렬 알고리즘은?

○ 입력: 크기가 n인 배열 A

○ 출력: 정렬된 배열 A for i = 0 to n-2 min = i for j = i+1 to n-1 if(A[j] < A[min]) min = j A[i] ↔ A[min] return A

1. 버블 정렬(bubble sort)
2. 삽입 정렬(insertion sort)
3. 선택 정렬(selection sort)
4. 퀵 정렬(quick sort)

정답 3번

🔍 보기별 해설

버블 정렬은 이웃한 두 원소를 비교해 계속 자리를 바꾸며 큰 값을 뒤로 밀어낸다. 코드는 이웃 비교 없이 최솟값의 위치만 찾아 한 번 바꾸므로 옳지 않다.
삽입 정렬은 뒤쪽 원소를 앞의 정렬된 구간에서 알맞은 자리를 찾아 끼워 넣고 나머지를 뒤로 밀어낸다. 코드에는 원소를 밀어 자리를 만드는 과정이 없으므로 옳지 않다.
바깥 반복마다 나머지 구간에서 가장 작은 원소의 위치 min을 찾고 그것을 i번 자리와 한 번 맞바꾼다. 이 동작이 선택 정렬 그 자체이므로 옳다(정답).
퀵 정렬은 피벗을 정해 작은 값과 큰 값으로 나눈 뒤 양쪽을 재귀로 정렬한다. 코드에는 피벗도 분할도 재귀 호출도 없으므로 옳지 않다.

🧮 풀이

甲은 5, 1, 4에서 인접한 두 수를 비교해 5와 1을 바꾸고 다시 5와 4를 바꾸며 가장 큰 수가 끝으로 흘러가는 과정을 그렸다. 이웃끼리만 바꾸는 이 움직임을 코드와 견주어 보았다.
甲은 카드 게임에서 손에 든 카드들 사이에 새로 받은 카드를 알맞은 자리에 끼워 넣는 모습을 떠올렸다. 뒤 카드들을 한 칸씩 밀어 자리를 만드는 동작을 코드에서 찾지 못해 표에 가위표를 쳤다.
甲은 29, 10, 14, 37, 13에서 가장 작은 10의 위치를 찾아 맨 앞 29와 한 번 맞바꾸는 과정을 손으로 따라갔다. 이어 남은 구간에서 다시 최솟값을 찾아 둘째 자리와 바꾸며 단계마다 적어 두었다.
甲은 6, 2, 9, 4, 7에서 첫 원소 6을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 모으는 그림을 그렸다. 나뉜 양쪽을 다시 같은 방식으로 정렬한다는 것을 화살표로 표시했다.

반복마다 남은 구간의 최솟값 위치를 찾아 맨 앞과 한 번 맞바꾸는 코드는 선택 정렬이다.

다음 fib() 함수는 피보나치 수열을 계산한다. fib(6)을 실행할 때, fib() 함수의 호출 횟수는? (단, fib(6)의 호출은 제외한다)

int fib(int n)

{

if(n == 0) return 0;

if(n == 1) return 1;

return ( fib(n-1) + fib(n-2) );

}

1. 21번
2. 22번
3. 23번
4. 24번

정답 4번

🔍 보기별 해설

fib(6)은 fib(5)와 fib(4)를 부르고 두 호출의 전체 횟수가 15와 9이므로 합이 24다. 21은 이보다 3이 모자라 fib(2) 하나를 뿌리째 빠뜨린 값이므로 옳지 않다.
fib(5)에서 15번, fib(4)에서 9번의 호출이 일어나므로 합은 24가 된다. 22는 여기서 잎 호출 두 개를 빠뜨린 값으로 실제 호출 횟수와 맞지 않아 옳지 않다.
fib(5)의 15번과 fib(4)의 9번을 더하면 24번이다. 23은 여기서 호출을 하나 더 빼먹은 값으로 최초 호출 하나만 제외한다는 조건을 넘어서 세었으므로 옳지 않다.
호출 횟수는 C(n)=1+C(n-1)+C(n-2)이고 C(0)=C(1)=1에서 시작해 9, 15, 25로 늘어난다. 25번에서 fib(6)의 최초 호출 하나를 제외하면 24이므로 옳다(정답).

🧮 풀이

甲은 fib(6)의 호출 트리를 그리다 오른쪽 가지의 fib(2) 하나를 통째로 빼먹은 채 세어 21이라고 적었다. 층마다 호출 수를 다시 더해 보니 세 곳이 비어 있어 가지를 채워 넣었다.
甲은 fib(5)가 부르는 호출을 세다 fib(1) 호출 두 개를 빠뜨려 13으로 적었다. 이 값에 fib(4)의 9를 더해 22를 얻은 뒤 트리의 잎을 하나씩 짚으며 모자란 두 개를 찾아 채웠다.
甲은 fib(6)의 호출이 모두 25번이고 최초 호출을 빼면 24라는 풀이를 보았다. 자기 계산에서는 잎 호출 하나를 더 빼서 23이 나온 것을 발견하고 트리의 잎을 모두 다시 세어 표시했다.
甲은 호출 횟수 C(n)이 1+C(n-1)+C(n-2)임을 세워 C(2)부터 C(6)까지 3, 5, 9, 15, 25를 표로 채웠다. 마지막 25에서 처음 호출 하나를 제외한 24를 답 칸에 적어 넣었다.

호출 횟수는 C(n)=1+C(n-1)+C(n-2)로 C(6)이 25번이며, 최초 호출을 빼면 24번이다.

(가) ～ (다)에 들어갈 점근 표기법은?

○ n ≥ n_0 인 모든 n 에 대해 c_1 g(n) ≤ f(n) ≤ c_2 g(n) 을 만족하는 양의 상수 c_1 , c_2 , n_0 가 존재하기만 하면 f(n) = (가) 이다.

○ n ≥ n_0 인 모든 n 에 대해 f(n) ≤ cg(n) 인 조건을 만족하는 양의 상수 c 와 n_0 가 존재하기만 하면 f(n) = (나) 이다.

○ n ≥ n_0 인 모든 n 에 대해 f(n) ≥ cg(n) 을 만족하는 양의 상수 c 와 n_0 가 존재하기만 하면 f(n) = (다) 이다. (가) (나) (다)

1. Ω(g(n)) O (g(n)) Θ(g(n))
2. Ω(g(n)) Θ(g(n)) O (g(n))
3. Θ(g(n)) O (g(n)) Ω(g(n))
4. Θ(g(n)) Ω(g(n)) O (g(n))

정답 3번

🔍 보기별 해설

첫 조건은 상수 c1과 c2로 위와 아래를 모두 묶으므로 Θ다. 그런데 하한만 나타내는 Ω를 넣고 O와 Θ를 뒤로 보내 세 칸이 모두 어긋났으므로 옳지 않다.
세 칸이 전부 잘못 놓였다. 첫 조건은 위아래를 함께 조이는 Θ, 둘째 조건은 위로만 막는 O인데 각각 Ω와 Θ를 넣어 정의와 맞지 않으므로 옳지 않다.
c1 g(n) ≤ f(n) ≤ c2 g(n)처럼 위아래를 함께 묶는 것은 Θ, f(n) ≤ c g(n)처럼 위로만 막는 것은 O, f(n) ≥ c g(n)처럼 아래로만 받치는 것은 Ω다. 세 정의와 맞으므로 옳다(정답).
첫 조건의 Θ는 맞지만 둘째와 셋째가 서로 바뀌었다. f(n) ≤ c g(n)인 상한 조건은 O이고 f(n) ≥ c g(n)인 하한 조건은 Ω이므로 옳지 않다.

🧮 풀이

甲은 c1과 c2 두 상수가 등장하는 첫 조건 옆에 하한만 나타내는 Ω 카드를 놓았다. 위와 아래를 함께 묶는 조건에 Ω는 어울리지 않아 그 카드를 치우고 다른 카드를 놓았다.
甲은 세 조건 옆에 Ω, Θ, O 카드를 차례로 붙여 놓고 둘째 조건의 부등호를 읽었다. f(n) ≤ c g(n)이라는 한쪽 부등호는 위로 막는 상한이지 조임이 아니라서 세 장을 모두 떼어 순서를 고쳐 놓았다.
甲은 f(n)=3n^2+2n을 두고 c1=3, c2=4, n0=2로 위아래를 함께 조이는 것을 확인했다. 이어 한쪽만 만족해도 되는 상한과 하한 조건을 하나씩 검증해 Θ, O, Ω 순으로 카드를 붙여 두었다.
甲은 첫 조건에는 Θ를 붙였지만 둘째 조건에 Ω를, 셋째 조건에 O를 붙여 두었다. 부등호 방향을 손가락으로 짚어 보니 위쪽 묶음이 O이고 아래쪽 묶음이 Ω라 두 카드를 서로 바꿨다.

위아래를 함께 조이는 것이 Θ, 위로 막는 것이 O, 아래로 받치는 것이 Ω이다.

다음 재귀함수 power()는 xn을 계산한다. 빈칸에 들어갈 내용은?

double power(double x, int n)

{

if (n == 0) return 1;

return x *

}

1. power(x, n);
2. power(x, n-1);
3. power(x-1, n);
4. power(x-1, n-1);

정답 2번

🔍 보기별 해설

인자를 하나도 줄이지 않고 같은 호출을 되풀이하면 종료 조건 n이 0에 영원히 닿지 못한다. 호출이 끝없이 쌓여 스택이 넘치고 값도 구하지 못하므로 옳지 않다.
x^n은 x에 x^(n-1)을 곱한 것과 같으므로 지수를 하나 줄여 부르는 것이 맞는 점화식이다. n이 0에 이르면 1을 돌려주며 끝나니 곱셈이 n번 쌓여 x^n이 되므로 옳다(정답).
밑만 하나씩 줄이고 지수를 그대로 두면 n이 0에 다가가지 못해 재귀가 끝나지 않는다. 밑이 변해 x^n과도 무관한 값이 만들어지므로 옳지 않다.
지수는 줄지만 밑까지 함께 줄어 x에 (x-1)^(n-1)을 곱하는 꼴이 된다. 이는 x^n과 다른 값이라 거듭제곱 계산이 되지 않으므로 옳지 않다.

🧮 풀이

甲은 x=2, n=3을 넣고 power(2, 3)이 다시 power(2, 3)을 부르는 상황을 손으로 따라갔다. 호출이 조금도 줄지 않고 계속 쌓이는 것을 보고 종료 조건 n==0에 닿을 수 없다고 적어 두었다.
甲은 2의 3제곱을 2×2의 2제곱, 다시 2×2×2의 1제곱으로 펼쳐 곱셈 세 번과 종료값 1로 8이 되는 순서를 그렸다. 지수가 하나씩 줄어드는 호출 사슬을 칸마다 옮겨 적었다.
甲은 밑만 3, 2, 1로 줄어들고 지수는 2에 머무는 호출 표를 만들었다. n==0에 닿지 않은 채 밑이 음수로 내려가는 것을 보고 이 코드는 빈칸에 쓸 수 없다고 표시했다.
甲은 3의 3제곱을 3 × power(2, 2)로 계산하면 12가 나와 27과 다르다는 것을 확인했다. 밑과 지수를 함께 줄이면 값이 어긋난다고 적고 빈칸 후보에서 지웠다.

x^n = x × x^(n-1)이므로 지수를 하나 줄여 부르면 n이 0에 닿아 재귀가 끝난다.

힙 정렬(heap sort)을 수행하기 위해 다음 데이터를 왼쪽부터 차례대로 하나씩 삽입하여 최소힙(min heap)을 구성하였다. 이후 루트를 한 번 삭제하고 최소힙 특성을 유지하기 위해 재조정한 후, 루트의 왼쪽 자식 노드의 값은?

4, 6, 8, 3, 7, 1, 5, 2, 9

1. 3
2. 4
3. 5
4. 6

정답 2번

🔍 보기별 해설

삽입을 마친 최소힙은 1, 2, 3, 4, 7, 8, 5, 6, 9이다. 루트를 지우고 재조정한 뒤에도 3은 루트 2의 오른쪽 자식 자리에 남아 왼쪽 자식이 아니므로 옳지 않다.
삽입으로 만든 힙에서 루트 1을 지우고 마지막 값 9를 올려 내리면 배열은 2, 4, 3, 6, 7, 8, 5, 9가 된다. 루트 2의 왼쪽 자식은 인덱스 1의 값 4이므로 옳다(정답).
5는 재조정을 마친 배열에서 인덱스 6에 있어 오른쪽 자식 3의 오른쪽 아래에 놓인 노드다. 루트의 바로 아래 자식이 아니라 손자 자리이므로 옳지 않다.
6은 재조정을 마친 배열의 인덱스 3에 있어 루트 왼쪽 자식 4 밑의 왼쪽 손자 자리에 놓인다. 루트의 자식이 아니라 손자이므로 옳지 않다.

🧮 풀이

甲은 재조정을 마친 트리에서 루트 2의 오른쪽 가지 끝을 손가락으로 짚어 3이 그 자리에 있음을 보았다. 3은 오른쪽 자식이라고 적고 왼쪽 자식 자리에는 4가 놓인다고 옆에 써 넣었다.
甲은 4, 6, 8, 3, 7, 1, 5, 2, 9를 넣으며 부모보다 작으면 위로 올려 최소힙을 만든 뒤 루트를 지웠다. 마지막 값 9를 루트에 올려 내리는 과정을 따라가 루트 아래 왼쪽에 4가 놓이는 것을 확인했다.
甲은 재조정된 배열의 인덱스 6에 5가 있는 것을 부모 계산식 (i-1)/2로 짚어 보았다. 부모가 인덱스 2의 3이므로 5는 루트의 자식이 아닌 손자임을 트리 그림 옆에 표시했다.
甲은 인덱스 3에 있는 6의 부모를 (3-1)/2로 계산해 인덱스 1의 4임을 얻었다. 6은 루트 바로 아래가 아니라 한 칸 더 내려간 손자라 왼쪽 자식 후보에서 지워 버렸다.

삽입 뒤 최소힙은 1,2,3,4,7,8,5,6,9이고, 루트를 지우고 재조정하면 2,4,3,6,7,8,5,9라 루트의 왼쪽 자식은 4다.

다음 조건으로 퀵 정렬(quick sort)을 수행할 때, 처음 데이터 교환이 발생하는 배열의 인덱스 쌍은?

○ 데이터를 오름차순으로 정렬한다.

○ low는 왼쪽에서 오른쪽으로 탐색할 때, high는 오른쪽에서 왼쪽으로 탐색할 때 사용되는 변수이다.

○ 정렬할 데이터(A[])는 다음과 같으며, 피벗(pivot)의 초기값은 A[0]이고, low와 high의 초기값은 각각 1과 8이다.

1. 1, 8
2. 2, 6
3. 2, 7
4. 3, 8

정답 2번

🔍 보기별 해설

A[1]=5는 피벗 23보다 작아 low가 멈추지 않고 지나친다. A[8]=78도 피벗보다 커서 high가 멈추지 않으니 1과 8은 교환 후보가 될 수 없어 옳지 않다.
low는 5를 지나 인덱스 2의 91에서 멈추고 high는 78과 42를 지나 인덱스 6의 18에서 멈춘다. low가 high보다 작아 두 원소를 맞바꾸므로 옳다(정답).
low는 2에서 멈추는 것이 맞지만 high는 인덱스 7의 42가 피벗 23보다 커서 멈추지 않고 더 왼쪽으로 내려가야 한다. 실제 멈춤은 6이므로 옳지 않다.
인덱스 3의 10은 피벗보다 작아 low가 멈출 자리가 아니고 low는 이미 2에서 멈춘다. 인덱스 8의 78도 피벗보다 커서 high가 멈추지 않으므로 옳지 않다.

🧮 풀이

甲은 배열 표에서 인덱스 1의 값 5와 인덱스 8의 값 78에 각각 표시를 하고 피벗 23과 크기를 견주었다. 5는 23에 못 미치고 78은 23을 넘어 두 값 모두 화살표가 멈출 자리가 아니라고 적었다.
甲은 low를 인덱스 1부터 오른쪽으로 옮겨 5를 지나 91에서 멈추게 하고, high를 8부터 왼쪽으로 옮겨 78과 42를 지나 18에서 멈추게 화살표로 그렸다. 두 화살이 엇갈리기 전이라 2번과 6번을 바꾸기로 하고 동그라미를 쳤다.
甲은 high를 8에서 7까지 옮기다 A[7]=42를 보고 멈췄다. 42가 피벗 23보다 커서 멈출 이유가 없다는 점을 짚고 그 화살표를 한 칸 더 왼쪽인 인덱스 6으로 옮겨 그렸다.
甲은 low 화살표를 인덱스 3에 그렸다가 A[3]=10이 피벗보다 작아 멈추지 않는다는 것을 알아챘다. 그 앞의 A[2]=91에서 멈춰야 하므로 화살표를 인덱스 2로 옮겨 다시 그렸다.

피벗 23에서 low는 5를 지나 인덱스 2의 91에서 멈추고 high는 78과 42를 지나 인덱스 6의 18에서 멈춘다. 처음 교환은 (2, 6)이다.

9급 데이터 기출 80문항 · 자동복습과 예상점수까지 무료로 →

재귀 알고리즘에 대한 설명으로 옳지 않은 것은?

1. 재귀호출은 함수가 자기 자신을 호출하는 것이다.
2. 재귀함수는 재귀호출이 끝나는 종료 조건이 있어야 한다.
3. 재귀함수로 작성된 병합 정렬(merge sort) 알고리즘은 반복문을 이용하여 구현할 수 있다.
4. 재귀함수는 실행 시간과 메모리 공간 사용 측면에서 반복문보다 효율성이 높다.

정답 4번

🔍 보기별 해설

함수가 자기 자신을 다시 부르는 것이 재귀호출의 정의다. 팩토리얼이나 피보나치 같은 정의를 그대로 코드로 옮기는 방식이므로 맞다.
재귀함수에는 더 이상 호출하지 않고 값을 돌려주는 종료 조건이 있어야 한다. 그것이 없으면 호출이 끝없이 이어져 스택이 넘치므로 맞다.
재귀로 쓴 병합 정렬도 길이 1부터 2, 4, 8로 묶어 가는 상향식으로 바꾸면 반복문만으로 구현할 수 있다. 재귀는 반복문으로 옮길 수 있다는 설명이므로 맞다.
재귀는 호출마다 스택에 프레임이 쌓여 메모리를 더 쓰고 호출 비용도 든다. 반복문보다 효율이 높다는 진술은 사실과 반대이므로 옳지 않다(정답).

🧮 풀이

甲은 factorial(n)이 factorial(n-1)을 부르는 코드를 읽고 함수 안에서 자기 이름을 다시 부르는 줄에 밑줄을 그었다. 이것이 재귀호출이라고 여백에 적어 두었다.
甲은 종료 조건 줄을 지운 factorial을 돌렸다가 호출이 끝없이 쌓이다 스택 오버플로 오류가 나는 것을 화면으로 보았다. n==0에서 멈추는 줄을 다시 살려 넣고 재실행해 보았다.
甲은 병합 정렬을 재귀 없이 바닥부터 길이 1, 2, 4로 묶어 가며 합치는 반복문 코드로 옮겨 짰다. 결과가 재귀판과 같은 정렬 배열임을 확인하고 두 코드를 나란히 저장해 두었다.
甲은 1부터 n까지의 합을 재귀와 반복문으로 각각 구해 n이 클 때 실행해 보았다. 재귀판은 호출 스택이 쌓여 멈추고 반복문판은 끝까지 돌아 메모리도 적게 쓴 결과를 표로 만들었다.

재귀는 호출마다 스택 프레임이 쌓여 반복문보다 시간과 메모리를 더 쓰는 경우가 많다. 효율이 높다는 말은 틀렸다.

동적 계획(dynamic programming) 알고리즘에 대한 설명으로 옳지 않은 것은?

1. 최적화 문제에 적용할 수 있는 알고리즘이다.
2. 상위 문제의 해를 분할하여 하위 문제의 해를 구한다.
3. 최적해를 구하는 방법을 재귀적으로 정의한다.
4. 한 번 계산된 부분 문제들의 해는 재사용을 위해 저장된다.

정답 2번

🔍 보기별 해설

동적 계획법은 최적 부분구조를 가진 최적화 문제에 적용하는 방법이다. 최대 이익이나 최소 비용처럼 최적값을 구하는 문제에 쓰이므로 맞다.
동적 계획법은 작은 부분 문제의 해를 먼저 구하고 그것을 조합해 큰 문제의 해를 만드는 상향식이 기본이다. 상위 문제의 해를 분할하는 서술은 분할정복 쪽 설명이므로 옳지 않다(정답).
큰 문제의 최적해를 더 작은 문제의 최적해로 나타내는 점화식을 세워 재귀적으로 정의한다. 동적 계획법의 핵심 절차를 옳게 말했으므로 맞다.
같은 부분 문제가 여러 번 나오므로 한 번 계산한 해를 표나 배열에 저장해 두고 다시 꺼내 쓴다. 이 저장과 재사용이 동적 계획법의 특징이므로 맞다.

🧮 풀이

甲은 배낭 문제에서 물건을 넣는 조합 가운데 가치가 가장 큰 것을 찾는 것이 최적화 문제임을 확인하고 동적 계획법 표를 그렸다. 최댓값을 채워 가는 칸 옆에 최적화라고 적었다.
甲은 fib(5)를 fib(0)과 fib(1)에서 출발해 fib(2), fib(3), fib(4)를 차례로 올라가며 구했다. 작은 값을 쌓아 큰 값을 만드는 방향을 화살표로 그려 두었다.
甲은 최장 공통 부분 수열에서 D[i][j]를 앞 칸 값 세 개로 정하는 점화식을 적었다. 큰 문제의 최적값이 작은 문제의 최적값으로 정의됨을 식 바로 옆에 메모해 두었다.
甲은 fib를 재귀로만 풀 때 fib(3)이 여러 번 다시 계산되는 것을 호출 트리로 확인했다. 그 자리에 배열 칸을 만들어 값을 적어 두고 다음 호출에서는 그 칸부터 읽도록 코드를 고쳐 썼다.

동적 계획법은 작은 부분 문제의 해를 저장해 두었다가 조합해 큰 문제의 해를 만든다. 큰 해를 쪼개어 작은 해를 얻는다는 말은 틀렸다.

다음 이진 탐색 트리(binary search tree)에서 키 48을 검색할 때, 방문하는 노드의 순서는?

1. 55 － 15 － 28 － 30 － 48
2. 55 － 60 － 90 － 15 － 28 － 30 － 48
3. 55 － 15 － 8 － 3 － 28 － 18 － 16 － 30 － 48
4. 55 － 15 － 60 － 8 － 28 － 90 － 3 － 18 － 30 － 16 － 48

정답 1번

🔍 보기별 해설

48은 55보다 작아 왼쪽 15로 가고, 15보다 커서 오른쪽 28로, 28보다 커서 오른쪽 30으로, 30보다 커서 오른쪽 48에 이른다. 한 갈래만 따라간 경로가 이 순서이므로 옳다(정답).
48이 55보다 작은데 오른쪽 가지의 60과 90을 살펴볼 이유가 없다. 이진 탐색 트리는 비교 결과에 따라 한쪽 가지만 따라가므로 이런 경로는 나올 수 없어 옳지 않다.
48은 15보다 크므로 15에서 왼쪽 8과 3으로 내려갈 수 없고 오른쪽 28로 가야 한다. 큰 값을 왼쪽에서 찾는 경로이므로 옳지 않다.
이 순서는 층마다 왼쪽부터 노드를 모두 읽은 너비 우선 순회일 뿐이다. 이진 탐색 트리의 검색은 한 경로만 따라가므로 모든 노드를 훑는 이 순서는 옳지 않다.

🧮 풀이

甲은 48을 찾는 동안 지나간 노드에 번호를 매겨 보았다. 뿌리 55에서 시작해 15, 28, 30을 거쳐 48에서 멈추니 모두 다섯 칸이었고 갈림길마다 한쪽 가지만 골랐다는 점을 표시했다.
甲은 55에서 60과 90을 지나 15로 되돌아가는 경로를 그려 보고 이상함을 느꼈다. 48이 55보다 작은데 오른쪽 가지를 살펴볼 이유가 없어 그 구간에 굵은 가위표를 쳤다.
甲은 15에서 왼쪽 8과 3으로 내려가는 경로를 따라가다 48이 15보다 큰데 왼쪽으로 갈 수 없음을 알아챘다. 그 갈래를 지우고 15의 오른쪽 28로 옮겨 경로를 다시 그렸다.
甲은 층마다 왼쪽부터 노드를 읽어 55, 15, 60, 8, 28, 90, 3, 18, 30, 16, 48로 적었다. 이는 모든 노드를 훑는 너비 우선 순서일 뿐 탐색 경로가 아니어서 후보에서 뺐다.

이진 탐색 트리는 각 노드에서 키가 작으면 왼쪽, 크면 오른쪽 한 갈래만 따라간다. 48은 55, 15, 28, 30, 48 순으로 방문한다.

다음 정렬 알고리즘의 평균 시간복잡도를 바르게 연결한 것은?

(가) 선택 정렬 (나) 삽입 정렬 (다) 퀵 정렬 (라) 버블 정렬 (가) (나) (다) (라)

1. O (n) O (n^2) O (n logn) O (n^2)
2. O (n) O (n^2) O (n^2) O (n logn)
3. O (n^2) O (n logn) O (n) O (n^2)
4. O (n^2) O (n^2) O (n logn) O (n^2)

정답 4번

🔍 보기별 해설

선택 정렬은 입력이 어떻든 남은 구간을 끝까지 훑어 최솟값을 찾으므로 비교가 늘 n(n-1)/2번이다. 정렬이 되어 있어도 줄지 않아 O(n)이 될 수 없으므로 옳지 않다.
선택 정렬을 O(n), 퀵 정렬을 O(n^2), 버블 정렬을 O(n log n)으로 적은 세 곳이 모두 틀렸다. 선택과 버블은 O(n^2)이고 퀵은 평균 O(n log n)이므로 옳지 않다.
삽입 정렬의 평균은 원소마다 앞 구간을 절반쯤 훑으므로 O(n^2)이지 O(n log n)이 아니다. 퀵 정렬을 O(n)으로 적은 것도 틀렸으므로 옳지 않다.
선택 정렬과 삽입 정렬, 버블 정렬은 평균 O(n^2)이고 퀵 정렬은 분할이 균형을 이루어 평균 O(n log n)이다. 네 칸이 모두 맞게 연결되었으므로 옳다(정답).

🧮 풀이

甲은 선택 정렬에서 비교 횟수를 세어 n(n-1)/2로 정해진 것을 보고 입력이 정렬돼 있어도 줄지 않음을 확인했다. O(n)이라고 적어 둔 칸을 지우고 n^2으로 고쳐 썼다.
甲은 표를 채우며 선택 정렬에 O(n), 퀵 정렬에 O(n^2), 버블 정렬에 O(n log n)을 적었다가 무작위 입력 1만 개에 돌려 시간을 재 보았다. 세 값이 모두 실측과 맞지 않아 지우고 다시 썼다.
甲은 삽입 정렬 평균을 O(n log n)이라 적었다가 무작위 배열에서 원소마다 앞 구간을 절반쯤 훑는 횟수를 세어 보았다. 그 횟수가 n^2에 비례한다는 것을 알고 정정했고 퀵 정렬에 적은 O(n)도 함께 고쳤다.
甲은 네 정렬을 입력 1만 개와 2만 개로 돌려 시간이 몇 배로 느는지 비교했다. 선택, 삽입, 버블은 네 배 안팎으로, 퀵은 두 배를 조금 넘게 늘 것으로 보고 각각 n^2과 n log n이라 표에 적었다.

선택·삽입·버블 정렬은 평균 O(n^2), 퀵 정렬은 평균 O(n log n)이다.

(가)에 들어갈 내용은?

○ (가) 는 사용되는 문자가 N개일 때, 문자열 검색을 빠르게 실행할 수 있도록 설계된 N진 트리이다.

○ (가) 를 이용한 문자열 검색은 루트 노드에서 시작하여 탐색키의 첫 번째 문자에 연관된 링크를 따라 노드를 찾아가고 그 노드에서 다시 두 번째 문자에 연관된 링크를 따라 노드를 찾아가는 과정을 검색이 완료될 때까지 반복한다.

1. AVL 트리(AVL tree)
2. B＋ 트리(B＋ tree)
3. 레드－블랙 트리(red-black tree)
4. 트라이(trie)

정답 4번

🔍 보기별 해설

AVL 트리는 이진 탐색 트리에 회전으로 높이 균형을 맞춘 구조다. 노드마다 자식이 왼쪽과 오른쪽 둘뿐이라 문자 종류 수만큼 갈라지는 N진 트리가 아니므로 옳지 않다.
B+ 트리는 한 노드에 키 여러 개를 담고 리프끼리 이어 범위 검색에 강한 디스크용 다진 탐색 트리다. 글자마다 링크를 따라가는 구조가 아니므로 옳지 않다.
레드-블랙 트리는 노드에 색을 칠하고 규칙으로 균형을 유지하는 이진 탐색 트리다. 자식이 둘뿐이고 문자별 링크를 쓰지 않으므로 옳지 않다.
트라이는 문자마다 링크를 하나씩 두어 루트에서 탐색키의 첫 글자, 둘째 글자 순으로 따라 내려가며 문자열을 찾는다. 설명과 정확히 맞으므로 옳다(정답).

🧮 풀이

甲은 정수 키 1부터 5까지를 차례로 넣고 회전으로 균형을 맞추는 AVL 트리를 그렸다. 노드마다 자식이 왼쪽과 오른쪽 둘뿐이어서 알파벳 수만큼 갈라지는 구조와 다르다고 표시했다.
甲은 데이터베이스 인덱스가 한 노드에 키 수백 개를 담고 리프끼리 이어진 그림을 보았다. 범위 조회에 쓰는 구조이지 글자별 링크를 따라가는 구조가 아니라고 그림 옆에 적었다.
甲은 레드-블랙 트리 노드에 빨강과 검정 색을 칠하며 회전과 색 바꾸기로 높이를 맞추는 과정을 연습했다. 두 자식만 가지는 이진 구조라 글자 수만큼 가지가 뻗는 트리가 아님을 확인했다.
甲은 cat, car, dog를 넣은 트리를 그려 루트에서 c를 따라가고 다시 a를 지나 t와 r로 갈라지는 링크를 이었다. 검색어 car를 글자별로 따라 내려가 보며 사전 자동완성이 이런 구조라고 적었다.

문자 하나마다 링크 하나를 따라 내려가며 문자열을 찾는 N진 트리는 트라이(trie)다.

다음에서 설명하는 알고리즘 설계 기법에 해당하지 않는 것은?

문제를 해결할 때 여러 경우 중 하나를 결정해야 할 때마다 현재 순간에 최적이라고 생각되는 것을 선택하면서 문제의 최종해에 도달한다.

1. 다익스트라(Dijkstra) 알고리즘
2. 프림(Prim) 알고리즘
3. 플로이드－워셜(Floyd-Warshall) 알고리즘
4. 허프만(Huffman) 코딩 알고리즘

정답 3번

🔍 보기별 해설

다익스트라는 아직 확정하지 않은 정점 가운데 거리가 가장 짧은 것을 매번 골라 확정한다. 순간마다 최선을 고르는 그리디에 해당한다.
프림 알고리즘은 지금까지 만든 트리에 붙는 간선 중 가장 가벼운 것을 매번 골라 붙인다. 각 단계에서 최선을 선택하는 그리디에 해당한다.
플로이드-워셜은 중간 정점을 하나씩 늘려 가며 앞 단계 표를 D[i][j]=min(D[i][j], D[i][k]+D[k][j])로 갱신하는 동적 계획법이다. 그리디 기법이 아니므로 해당하지 않는다(정답).
허프만 코딩은 빈도가 가장 낮은 두 노드를 반복해서 합쳐 트리를 만든다. 매 단계에서 지금 가장 좋은 선택을 하는 그리디에 해당한다.

🧮 풀이

甲은 출발점에서 아직 정해지지 않은 정점 가운데 거리가 가장 작은 정점을 고르는 일을 반복하며 표를 채웠다. 매번 현재 최선을 고른 뒤 그 값을 바꾸지 않는 방식이 그리디임을 적어 두었다.
甲은 여러 도시를 잇는 도로망을 새로 놓는 상황에서 이미 놓인 길에 이어지는 후보 중 비용이 가장 낮은 도로를 매번 골랐다. 한 번 놓은 길을 다시 바꾸지 않는 이 규칙을 공책 첫 줄에 적어 두었다.
甲은 세 도시 A, B, C에서 A와 C 사이 거리를 A, B, C를 거치는 경로와 견주어 짧은 값으로 갱신하는 표를 만들었다. 중간 도시를 하나씩 늘리며 이전 표 값을 다시 쓰는 방식이 동적 계획법이라고 옆에 썼다.
甲은 글자 빈도 5, 9, 12, 13, 16, 45에서 가장 작은 두 값을 합쳐 새 노드로 만드는 일을 반복해 트리를 그렸다. 매번 가장 낮은 빈도 둘을 고르는 규칙이 허프만 코딩의 그리디 선택임을 표시했다.

다익스트라·프림·허프만은 매번 현재 최선을 고르는 그리디이고, 플로이드-워셜은 동적 계획법이다.

다음 그래프에서 Kruskal 알고리즘을 사용하여 최소 신장 트리(minimum spanning tree)를 찾을 때, 최소 신장 트리의 간선을 나열한 것은?

1. (a,b) (a,f) (b,c) (c,d) (c,e) (f,g) (g,h)
2. (a,b) (a,f) (b,c) (c,d) (e,g) (f,g) (g,h)
3. (a,b) (b,c) (c,d) (c,e) (c,h) (f,g) (g,h)
4. (a,b) (b,c) (c,d) (c,e) (e,g) (f,g) (g,h)

정답 3번

🔍 보기별 해설

이 나열은 (a,f) 9를 포함하고 (c,h) 4를 빼서 합이 35다. 가중치 4짜리 c-h가 두 무리를 이을 수 있는데 더 무거운 간선을 쓴 신장 트리라 최소가 아니므로 옳지 않다.
이 나열은 가장 가벼운 간선 c-e(2)를 빼고 e-g(6)를 넣어 합이 39가 된다. 신장 트리이긴 해도 최소 가중치가 아니므로 옳지 않다.
간선을 2, 2, 3, 4, 4, 6, 7, 8 순으로 보며 사이클이 안 생기면 고른다. c-e, g-h, f-g, a-b, c-h를 고르고 e-g는 건너뛴 뒤 c-d, b-c로 일곱 개를 채워 합이 30이므로 옳다(정답).
이 나열은 c-h(4) 대신 e-g(6)를 써서 합이 32다. 신장 트리이긴 하지만 정답보다 2가 무거워 크루스칼이 만들어 내는 최소 신장 트리가 아니므로 옳지 않다.

🧮 풀이

甲은 첫째 보기의 간선 가중치를 4, 9, 8, 7, 2, 3, 2로 더해 35를 얻었다. 최소라면 4짜리 c-h 간선이 있어야 하는데 9짜리 a-f가 들어 있어 더 가벼운 조합이 가능함을 표시했다.
甲은 둘째 보기의 합을 구하다 c-e 간선(2)이 빠지고 e-g(6)가 들어간 것을 보았다. 합이 39로 나와 가장 가벼운 간선 c-e를 버렸다는 점에 굵게 밑줄을 그었다.
甲은 간선 열두 개를 가벼운 것부터 한 줄로 세워 놓고 앞에서부터 하나씩 살폈다. 두 끝점이 이미 이어진 간선은 건너뛰어 e-g가 걸러졌고, 합 30인 일곱 개가 차자 남은 간선을 더 보지 않았다.
甲은 넷째 보기에서 c-h 대신 e-g(6)를 쓰는 조합의 합을 32로 구했다. 정답과 2 차이 나는 이 조합에는 c-h(4)가 없다는 것을 확인하고 후보 목록에서 지웠다.

크루스칼은 가벼운 간선부터 사이클이 안 생기면 고른다. 결과는 c-e, g-h, f-g, a-b, c-h, c-d, b-c 일곱 개로 합 30이다.

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

1. 이진 탐색(binary search)을 위해 분할정복을 적용할 수 없다.
2. 분할정복을 사용한 대표적인 정렬 방법에는 병합 정렬(merge sort)이 있다.
3. 문제를 작은 문제로 분할하고 그 문제들의 해를 병합한다.
4. 분할된 문제들이 서로 중첩되지 않는 경우에 적합하다.

정답 1번

🔍 보기별 해설

이진 탐색은 가운데 원소와 견주어 탐색 범위를 절반으로 나누고 한쪽만 다시 탐색하는 분할정복의 대표 사례다. 적용할 수 없다는 진술은 사실과 반대이므로 옳지 않다(정답).
병합 정렬은 배열을 반으로 나누어 각각 정렬한 뒤 하나로 합치는 분할정복 정렬이다. 대표적인 예를 옳게 든 진술이므로 맞다.
분할정복은 문제를 작은 문제로 나누고 각각 푼 뒤 그 해를 병합해 전체 해를 얻는 기법이다. 세 단계를 옳게 요약했으므로 맞다.
분할된 문제들이 서로 겹치지 않을 때 분할정복이 알맞고 겹칠 때는 결과를 저장하는 동적 계획법이 낫다. 적용 조건을 옳게 말한 진술이므로 맞다.

🧮 풀이

甲은 정렬된 배열 2, 5, 8, 12, 16, 23에서 23을 찾으며 가운데 값과 견주어 왼쪽 절반을 버렸다. 남은 절반에서 같은 일을 되풀이하는 이 방식이 분할정복이라고 적었다.
甲은 원소 8개짜리 배열을 4개, 2개, 1개로 나눈 뒤 다시 두 조각씩 합치며 정렬하는 그림을 그렸다. 반으로 나누고 합치는 이 흐름이 병합 정렬이라고 그림 옆에 이름을 붙여 두었다.
甲은 큰 문제를 둘로 나누고 각각 푼 뒤 결과를 합치는 세 단계를 화살표로 이어 그렸다. 세 단계에 나눔, 풂, 합침이라는 이름을 차례로 붙이고 예제 문제 하나를 그 순서대로 풀어 보았다.
甲은 피보나치를 나누어 풀 때 같은 fib(3)이 여러 번 나오는 것을 호출 트리에서 확인했다. 부분 문제가 겹치는 이런 경우에는 결과를 저장하는 방식이 더 낫다고 옮겨 놓았다.

이진 탐색은 중간 원소와 견주어 절반을 버리는 대표적인 분할정복이다. 적용할 수 없다는 말이 틀렸다.

입력으로 길이 n 의 텍스트 문자열(T)과 길이 m 의 패턴 문자열(P)이 있을 때, 문자열 매칭(string matching) 알고리즘에 대한 설명으로 옳지 않은 것은?

1. 브루트－포스(brute-force) 방식의 수행 시간은 O (mn) 이다.
2. 라빈－카프(Rabin-Karp) 알고리즘은 P의 해시(hash) 값을 이용한다.
3. 보이어－무어(Boyer-Moore) 알고리즘은 P의 각 문자를 왼쪽에서 오른쪽으로 스캔하면서 T와 비교한다.
4. KMP(Knuth-Morris-Pratt) 알고리즘은 P의 각 문자에 대해 매칭 실패 시 비교를 다시 시작할 위치를 계산해 놓는다.

정답 3번

🔍 보기별 해설

브루트-포스는 텍스트의 모든 시작 위치에서 패턴을 처음부터 다시 견주므로 최악에 m×n번 비교한다. 수행 시간이 O(mn)이라는 진술은 맞다.
라빈-카프는 패턴의 해시값을 먼저 구해 두고 텍스트의 같은 길이 창의 해시값과 견주다가 값이 같을 때만 글자를 확인한다. 해시를 이용한다는 진술은 맞다.
보이어-무어는 패턴의 맨 오른쪽 글자부터 왼쪽으로 견주며 불일치가 나면 미리 만든 표로 패턴을 여러 칸 밀어 낸다. 왼쪽에서 오른쪽으로 스캔한다는 진술은 옳지 않다(정답).
KMP는 패턴을 미리 분석해 접두사와 접미사가 겹치는 길이를 담은 실패 표를 만든다. 불일치가 나면 처음으로 돌아가지 않고 표가 알려 주는 위치에서 이어 비교하므로 맞다.

🧮 풀이

甲은 텍스트 AAAAB에서 패턴 AAB를 찾을 때 시작 위치마다 처음부터 다시 견주며 비교 횟수를 세었다. 최악에 n과 m을 곱한 만큼으로 늘어남을 식으로 공책에 적어 두었다.
甲은 패턴 abc의 해시값을 계산해 두고 텍스트에서 세 글자 창을 한 칸씩 밀며 해시를 갱신해 견주었다. 값이 같은 창에서만 글자를 하나씩 확인하는 순서를 표로 만들어 두었다.
甲은 텍스트 위에 패턴 카드를 올려 놓고 카드의 맨 오른쪽 글자부터 왼쪽으로 견주었다. 글자가 다르면 카드를 여러 칸 밀어 내는 방식이라 왼쪽부터 재는 설명이 틀렸음을 알고 화살표 방향을 고쳤다.
甲은 패턴 ABABC의 접두사와 접미사가 겹치는 길이를 칸마다 적은 실패 표를 미리 만들었다. 중간에서 글자가 어긋나면 패턴의 처음이 아니라 표에 적힌 위치로 돌아가 이어 견주었다.

보이어-무어는 패턴을 오른쪽 끝에서 왼쪽으로 비교하며 불일치 때 크게 건너뛴다.

백트래킹(backtracking)에 대한 설명으로 옳은 것만을 모두 고르면?

ㄱ. 너비 우선 탐색(breadth first search) 방식을 기반으로 한다.

ㄴ. 문제를 해결하는 과정에서 해를 더 이상 얻지 못하는 상황이 되면 직전 상황으로 되돌아가서 다시 해를 탐색하는 기법이다.

ㄷ. 적용할 수 있는 대표적인 문제로는 미로 찾기, N－여왕 문제 등이 있다.

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

정답 3번

🔍 보기별 해설

ㄱ의 너비 우선 탐색 기반이라는 말은 틀렸다. 백트래킹은 깊이 우선으로 한 갈래를 끝까지 파고들다 되돌아가며, 참인 ㄴ과 ㄷ이 빠진 묶음이기도 하므로 옳지 않다.
ㄴ은 막다른 곳에서 직전 상황으로 돌아가 다시 탐색한다는 백트래킹의 정의라 참이다. 미로 찾기와 N-여왕 문제를 대표 사례로 든 ㄷ도 참인데 빠졌으므로 옳지 않다.
막히면 직전 상황으로 되돌아가 다시 탐색한다는 ㄴ과 미로 찾기, N-여왕 문제가 대표 적용 사례라는 ㄷ이 모두 옳다. 너비 우선이라는 ㄱ은 빠진 이 묶음이 맞다.
ㄴ과 ㄷ은 참이지만 ㄱ이 섞여 있다. 백트래킹은 깊이 우선 방식에 기반하므로 너비 우선 탐색이라는 ㄱ은 거짓이고 그것을 포함한 묶음은 옳지 않다.

🧮 풀이

甲은 큐로 가까운 칸부터 층별로 미로를 훑는 그림과 한 길로 깊이 들어가는 그림을 나란히 그렸다. 백트래킹의 움직임은 뒤쪽 그림에 가깝다고 보고 앞 그림에 지운 표시를 했다.
甲은 스도쿠 칸에 숫자를 넣다가 같은 줄에 중복이 생기면 방금 넣은 숫자를 지우고 다른 숫자를 넣어 보았다. 막히면 되돌아가서 다시 시도하는 과정을 화살표로 공책에 적었다.
甲은 4×4 체스판에 여왕 넷을 놓다가 막히면 바로 앞 말의 자리를 옮겨 보았다. 미로 찾기에서도 막다른 길을 되짚는 같은 방식이 쓰인다고 두 사례를 표 맨 위에 적어 두었다.
甲은 세 진술을 백트래킹 설명 카드와 하나씩 대 보았다. 너비 우선이라는 첫 진술만 깊이 우선의 성질과 어긋나 그 카드는 따로 밀어 두고 나머지 둘만 정답 후보로 남겨 놓았다.

백트래킹은 깊이 우선으로 탐색하다 막히면 직전 상황으로 되돌아가는 기법이며 미로 찾기, N-여왕 문제에 쓴다. 정답은 3번.

9급 데이터 기출 80문항 · 자동복습과 예상점수까지 무료로 →

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

어떤 양의 상수 c 와 n_0 이 존재하여 모든 n (가) n_0 에 대하여 f(n) (나) c · g(n) 을 만족하면 f(n) 은 O (g(n)) 에 속한다. (가) (나)

1. ≥ ≥
2. ≤ ≤
3. ≤ ≥
4. ≥ ≤

정답 4번

🔍 보기별 해설

(가)는 맞지만 (나)에 ≥를 쓰면 f(n)이 c·g(n) 이상이라는 하한 조건이 되어 Ω의 정의가 된다. 빅오는 위로 막는 것이므로 옳지 않다.
(나)의 ≤는 맞지만 (가)에 ≤를 쓰면 n이 n0 이하인 작은 범위에서만 성립한다는 뜻이 된다. 점근 표기는 n이 충분히 큰 범위를 다루므로 옳지 않다.
두 관계연산자를 모두 정의와 반대 방향으로 적었다. 작은 n에서만 성립하고 하한을 주는 식이라 어떤 함수에도 상한을 주지 못하므로 옳지 않다.
n이 n0 이상인 모든 곳에서 f(n)이 c·g(n) 이하이면 f(n)은 O(g(n))에 속한다. 큰 n에서 위로 막는다는 정의와 정확히 맞으므로 옳다(정답).

🧮 풀이

甲은 c=1일 때 f(n) ≥ g(n)이 성립함을 보이고 이를 빅오 증명이라고 적었다. 그러나 이 식은 하한 표기인 Ω의 정의와 같다는 지적을 받고 부등호를 뒤집어 다시 적었다.
甲은 n ≤ n0인 작은 n에서만 f(n) ≤ c g(n)이 맞는 사례를 표로 만들었다. n이 커지면 어긋나는 함수여서 점근 표기로는 쓸 수 없다고 표 아래에 적어 두었다.
甲은 조건을 n ≤ n0, f(n) ≥ c g(n)으로 적은 답안을 채점해 보았다. 두 부등호가 모두 정의와 반대 방향이라 어느 함수에도 상한을 주지 못한다고 판단해 붉은 펜으로 고쳤다.
甲은 f(n)=3n+2와 g(n)=n에 c=4, n0=2를 넣어 n이 2 이상일 때 3n+2 ≤ 4n이 성립함을 확인했다. 큰 n에서 위로 막는다는 뜻을 부등호로 옮겨 공식을 공책에 적었다.

빅오는 n이 n0 이상인 모든 곳에서 f(n) ≤ c·g(n)이 성립하는 상한 표기다.

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

1. 퀵 정렬(quick sort)
2. 버블 정렬(bubble sort)
3. 삽입 정렬(insertion sort)
4. 병합 정렬(merge sort)

정답 1번

🔍 보기별 해설

퀵 정렬은 피벗을 기준으로 분할하며 멀리 떨어진 원소를 맞바꾸므로 같은 값의 앞뒤 순서가 뒤집힐 수 있다. 안정 정렬에 해당하지 않는다(정답).
버블 정렬은 이웃한 두 원소가 같으면 자리를 바꾸지 않으므로 같은 값의 원래 순서가 그대로 남는다. 안정 정렬에 해당하므로 맞다.
삽입 정렬은 새 원소를 삽입할 때 같은 값을 만나면 그 뒤에 멈추어 순서를 유지한다. 안정 정렬에 해당하는 대표적인 알고리즘이므로 맞다.
병합 정렬은 두 조각을 합칠 때 값이 같으면 왼쪽 조각의 원소를 먼저 옮기므로 원래 순서가 지켜진다. 안정 정렬에 해당하므로 맞다.

🧮 풀이

甲은 5a, 5b, 2를 마지막 값 2를 피벗으로 나누어 피벗을 맨 앞 5a와 맞바꾸는 과정을 따라갔다. 결과 2, 5b, 5a에서 두 5의 순서가 뒤집힌 것을 색으로 표시했다.
甲은 4a, 4b, 1에 버블 정렬을 돌려 이웃한 4a와 4b는 같아서 바꾸지 않고 1만 앞으로 옮기는 것을 보았다. 결과에서 4a가 4b보다 앞에 남은 것을 확인해 두었다.
甲은 성적표를 이름순으로 정렬해 둔 뒤 점수순으로 삽입 정렬했다. 새 카드를 넣을 때 같은 점수를 만나면 그 뒤에 멈추므로 같은 점수 학생들이 원래 이름 순서를 그대로 지킨 것을 확인해 기록해 두었다.
甲은 3a, 1, 3b, 2를 두 조각으로 갈라 각각 정렬한 뒤 하나로 이었다. 같은 3이 만나는 자리에서 왼쪽 조각의 3a를 먼저 놓아 결과가 1, 2, 3a, 3b가 되는 것을 확인했다.

퀵 정렬은 멀리 떨어진 원소를 교환하므로 같은 값의 원래 순서가 뒤바뀔 수 있어 안정 정렬이 아니다.

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

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

1. 600원
2. 750원
3. 840원
4. 900원

정답 3번

🔍 보기별 해설

물건을 쪼갤 수 없다고 보고 A와 C를 통째로 넣은 값이다. 문제의 금속 분말은 분할 가능하므로 남은 3kg도 채울 수 있어 이 값은 최대가 아니므로 옳지 않다.
A와 C를 통째로 넣고 B를 3kg 덜어 넣은 값이다. 하지만 kg당 이익이 가장 낮은 A를 통째로 싣는 것은 그리디 선택이 아니라서 최대가 아니므로 옳지 않다.
kg당 이익은 A 20원, B 50원, C 100원이다. C 4kg으로 400원, B 6kg으로 300원, 남은 7kg을 A로 채워 140원을 더하면 840원이므로 옳다(정답).
900원은 세 물건 전부의 이익을 더한 값이다. 세 물건이 모두 20kg이어서 17kg 한도를 넘으므로 실제로 담을 수 없는 값이라 옳지 않다.

🧮 풀이

甲은 물건을 쪼갤 수 없다는 조건으로 A와 C를 넣어 14kg에 600원이라 계산했다. 남는 3kg에 B를 덜어 넣을 수 있다는 문제 조건을 다시 읽고 값을 새로 고쳐 적었다.
甲은 A와 C를 통째로 싣고 남는 3kg에 B를 덜어 넣은 조합을 계산해 750원을 얻었다. 그러나 kg당 이익이 낮은 물건을 먼저 고른 순서가 마음에 걸려 다른 순서로 표를 다시 그려 보았다.
甲은 kg당 이익 20, 50, 100원을 구해 100원짜리 C 4kg, 50원짜리 B 6kg, 남은 7kg의 A를 차례로 담았다. 400, 300, 140원을 더해 840원으로 합계를 적었다.
甲은 세 물건의 이익 200, 300, 400을 더해 900원을 얻은 뒤 배낭에 넣을 수 있는 무게를 확인했다. 세 물건이 20kg으로 17kg을 넘으니 900원은 담을 수 없는 값이라 지웠다.

분할 가능한 배낭은 kg당 이익이 큰 순으로 담는다. C 4kg 400, B 6kg 300, A 7kg 140으로 840원이다.

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

1. n^3 + 10 - > Θ (n^3)
2. n^2 + 100n rarrow O(n^3)
3. 4n logn + 2logn rarrow Θ (n logn)
4. 2n^2 + logn + 1000 - > Ω (n^2 logn)

정답 4번

🔍 보기별 해설

n^3에 상수 10이 더해진 식은 n이 커질수록 상수가 무시되어 위아래를 n^3이 함께 조인다. Θ(n^3)이 정확한 표기이므로 맞다.
n^2+100n은 n^3보다 느리게 자라므로 n^3이 위로 막는 상한이 될 수 있다. O(n^3)은 성립하는 표기이므로 맞다.
4n log n에서 계수 4와 낮은 차수의 2 log n을 버리면 n log n이 남아 위아래를 함께 조인다. Θ(n log n)이 성립하므로 맞다.
2n^2+log n+1000은 n^2 항이 지배하므로 n^2 log n보다 느리게 자란다. 하한이 이 식보다 크게 자랄 수는 없으니 Ω(n^2 log n)은 성립하지 않아 옳지 않다(정답).

🧮 풀이

甲은 n^3+10에서 상수 10이 n이 커질수록 무시되는 것을 확인했다. n이 3 이상이면 n^3 ≤ n^3+10 ≤ 2n^3이 성립해 n^3이 위아래를 함께 묶는다고 적어 두었다.
甲은 n^2+100n에 n=1000을 넣어 약 백십만이 나오고 n^3은 십억임을 계산했다. 상한으로서 n^3이 충분히 크다는 점에서 O(n^3) 표기가 성립함을 확인해 두었다.
甲은 4n log n에서 계수 4를, 2 log n에서 낮은 차수를 지우는 과정을 적었다. 남은 n log n으로 위아래를 함께 조이는 Θ 표기가 성립한다고 식 옆에 표시했다.
甲은 2n^2+log n+1000에 n=1024를 넣어 약 이백십만이라 n^2 log n인 약 천만보다 훨씬 작음을 계산했다. 하한이 이 함수보다 크면 Ω가 성립하지 않으므로 이 보기는 틀렸다고 표시했다.

가장 빨리 자라는 항을 남기면 2n^2+log n+1000은 Θ(n^2)이라 Ω(n^2 log n)이 될 수 없다.

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

1. 1
2. 2
3. 3
4. 4

정답 3번

🔍 보기별 해설

규칙을 어기는 리프는 한 곳이 아니다. 루트 7의 왼쪽 서브트리에 8이 있고, 4의 왼쪽 서브트리에 6이 있으며, 8의 왼쪽 자식으로 9가 있어 하나만 지워서는 해결되지 않으므로 옳지 않다.
8과 6만 지워도 오른쪽 가지의 8 아래 왼쪽에 9가 남아 있다. 왼쪽 자식은 부모보다 작아야 하는데 9가 더 커서 여전히 조건이 깨지므로 옳지 않다.
루트 7의 왼쪽 서브트리에 놓인 리프 8, 4의 왼쪽 서브트리에 놓인 6, 8의 왼쪽 자식인 9가 각각 조건을 어긴다. 세 리프를 제거해야 하므로 옳다(정답).
리프는 1, 6, 8, 9 네 개이지만 1은 2의 왼쪽에서 조건을 지킨다. 지킬 필요 없는 리프까지 지우면 최소가 아니므로 옳지 않다.

🧮 풀이

甲은 리프 6, 8, 9 가운데 4의 오른쪽 자식인 8 하나만 지운 트리를 그려 다시 검사했다. 6이 4의 왼쪽 서브트리 안에서 4보다 크고 9가 8의 왼쪽에 남아 있어 여전히 규칙을 어긴다고 적었다.
甲은 리프 6과 8을 지운 트리를 다시 검사했다. 루트의 오른쪽 자식 8 아래에 9가 여전히 왼쪽으로 붙어 있어 부모보다 큰 자식이 남았다는 점을 붉은 펜으로 그림 위에 표시했다.
甲은 각 노드를 왼쪽 서브트리의 모든 값은 작고 오른쪽의 모든 값은 큰지 점검했다. 8은 7의 왼쪽에, 6은 4의 왼쪽에, 9는 8의 왼쪽에 놓여 어긋난 세 리프에 동그라미를 쳤다.
甲은 리프 네 개 1, 6, 8, 9를 모두 지운 트리를 그렸다. 1은 2의 왼쪽에 있어 원래부터 문제가 없던 노드라 지울 필요가 없다고 적고 지운 개수를 세 개로 다시 정리했다.

7의 왼쪽 서브트리의 8, 4의 왼쪽 서브트리의 6, 8의 왼쪽 자식 9가 규칙을 어겨 리프 3개를 제거해야 한다.

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

C_ij = Σ(k = 0~n - 1) A_ik B_kj

1. Θ (n^2)
2. Θ (n^3)
3. Θ (2^n)
4. Θ (n logn)

정답 2번

🔍 보기별 해설

n^2은 결과 행렬 C의 원소 수일 뿐이다. 원소마다 k를 0부터 n-1까지 돌며 n번 곱하고 더해야 하므로 총 연산은 n^2에 머물지 않아 옳지 않다.
C의 원소가 n^2개이고 각 원소를 구하는 데 k에 대한 합이 n번의 곱셈을 요구한다. 세 겹 반복으로 n^2 × n이 되어 Θ(n^3)이므로 옳다(정답).
2^n은 부분집합을 모두 나열할 때처럼 지수로 늘어나는 경우다. 행렬 곱은 i, j, k 세 겹 반복으로 끝나는 다항 시간이라 옳지 않다.
n log n은 병합 정렬처럼 분할하여 합치는 알고리즘의 시간이다. 행렬 곱은 원소마다 n번씩 계산해야 하므로 그보다 훨씬 많아 옳지 않다.

🧮 풀이

甲은 3×3 행렬에서 결과 칸이 아홉 개라는 점만 세고 9번만 계산하면 된다고 공책에 적었다. 그러나 칸 하나마다 곱셈이 세 번씩 필요하다는 것을 알고 27번으로 고쳐 셌다.
甲은 i, j, k 세 반복문을 겹쳐 쓴 행렬 곱 코드를 돌리며 곱셈 횟수를 세었다. n=10에서 1000번, n=20에서 8000번으로 여덟 배 늘어나는 것을 표로 적었다.
甲은 원소가 n개인 집합의 모든 부분집합을 만드는 코드가 2^n번 돌아가는 예를 읽었다. 행렬 곱의 세 겹 반복문은 n을 지수로 쓰지 않는 다항 코드라는 점을 대비해 표에 적었다.
甲은 병합 정렬 코드가 n log n번 연산으로 끝나는 것을 직접 돌려 확인했다. 행렬 곱은 결과 칸마다 n번씩 곱하고 더해야 하니 그보다 훨씬 많다고 코드 옆에 적어 두었다.

행렬 곱은 결과 원소 n^2개를 각각 n번의 곱셈으로 구하므로 Θ(n^3)이다.

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

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

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

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

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

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

정답 4번

🔍 보기별 해설

ㄱ은 옳지만 ㄴ이 틀렸다. 힙은 완전이진트리라 인덱스 i의 자식이 2i+1, 2i+2로 계산되어 배열로 구현하기에 알맞으므로 이 묶음은 옳지 않다.
ㄱ과 ㄹ은 참이지만 ㄷ도 참인데 빠졌다. 삽입은 맨 끝에 넣고 부모와 견주며 올라가 높이 log n번이면 끝나므로 세 진술을 모두 담지 못한 묶음은 옳지 않다.
ㄴ은 힙이 배열에 적합하지 않다는 진술로 거짓이다. 완전이진트리라 배열 인덱스만으로 부모와 자식을 찾으므로 ㄴ을 포함한 묶음은 옳지 않다.
ㄱ 완전이진트리, ㄷ 삽입 O(log n), ㄹ 힙 정렬 O(n log n)은 모두 참이고 ㄴ만 거짓이다. 참인 세 진술로 이루어진 이 묶음이 맞다.

🧮 풀이

甲은 힙을 포인터로 연결한 노드로만 짜야 한다는 문장을 읽고 의심했다. 인덱스 i의 자식이 2i+1, 2i+2이므로 배열로도 쉽게 만들 수 있다는 것을 표로 만들어 그 문장을 지웠다.
甲은 ㄱ과 ㄹ만 고른 답을 검산하다 힙 삽입 과정을 그려 보았다. 새 값을 맨 끝에 놓고 부모와 견주며 올라가는 횟수가 높이 log n이라는 것을 보고 ㄷ도 참이라 답에 더해야 한다고 적었다.
甲은 ㄴ과 ㄷ을 고른 답안을 채점했다. ㄴ을 근거로 삼은 부분에 빨간 줄을 긋고 인덱스로 부모와 자식을 찾는 식을 함께 써서 배열에 힙이 잘 어울린다는 설명을 옆에 적어 두었다.
甲은 힙 정렬이 원소 n개를 넣고 꺼내면서 각각 log n이 드는 것을 식으로 써 보았다. 합이 n log n이 되어 ㄱ, ㄷ, ㄹ에 표시하고 ㄴ은 지운 뒤 답 칸에 옮겨 적었다.

힙은 완전이진트리라 배열 구현에 알맞고 삽입은 O(log n), 힙 정렬은 O(n log n)이다. 정답은 4번.

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

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

1. 삽입 정렬(insertion sort) O(n^2) O(n^2) O(n)
2. 선택 정렬(selection sort) O(n^2) O(n^2) O(n logn)
3. 퀵 정렬 O(n^2) O(n logn) O(n logn)
4. 병합 정렬 O(n logn) O(n logn) O(n logn)

정답 2번

🔍 보기별 해설

삽입 정렬은 정렬된 입력에서 각 원소를 앞 원소와 한 번만 비교해 O(n)이고 거꾸로 정렬된 최악과 평균은 O(n^2)이다. 연결이 옳으므로 맞다.
선택 정렬은 입력이 어떻든 남은 구간에서 최솟값을 끝까지 찾으므로 최선의 경우도 n(n-1)/2번 비교한다. 최선을 O(n log n)으로 적은 것은 옳지 않다(정답).
퀵 정렬은 분할이 치우치는 최악에 O(n^2)이고 평균과 최선에서는 균형이 잡혀 O(n log n)이다. 세 값이 옳게 연결되어 있으므로 맞다.
병합 정렬은 항상 절반으로 나누고 합치는 비용이 n이어서 세 경우가 모두 O(n log n)이다. 세 값이 옳게 연결되어 있으므로 맞다.

🧮 풀이

甲은 1부터 n까지 이미 오름차순인 배열에 삽입 정렬을 돌려 보았다. 원소마다 바로 앞 값과 한 번 견주면 끝나 n번 안팎이었고, 거꾸로 놓인 배열에서는 n^2에 가깝게 늘어나는 것을 표로 적었다.
甲은 정렬된 배열과 뒤집힌 배열에 선택 정렬을 돌리며 비교 횟수를 세었다. 둘 다 같은 n(n-1)/2번이라 최선에 n log n이 나올 수 없다는 것을 표에 적어 두었다.
甲은 피벗을 가운데로 잡을 때와 가장자리로 잡을 때 퀵 정렬 비교 횟수를 그려 보았다. 가장자리면 n^2, 가운데면 n log n 층이 되는 것을 그림 옆에 나누어 적었다.
甲은 병합 정렬 트리가 항상 log n층이고 층마다 합치는 비용이 n인 그림을 그렸다. 입력이 어떻든 층 수와 비용이 같아 세 경우가 모두 n log n이라고 그림 옆에 적었다.

선택 정렬은 입력과 상관없이 항상 n(n-1)/2번 비교하므로 최선의 경우도 O(n^2)이다.

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

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

1. 2
2. 3
3. 4
4. 5

정답 3번

🔍 보기별 해설

문자가 여섯 개인데 2비트로는 서로 다른 코드 네 개까지만 만들 수 있다. 허프만 코드는 접두어 규칙을 지켜야 하므로 모든 문자가 2비트 이하일 수 없어 옳지 않다.
e, f, c는 세 칸 아래이지만 빈도가 가장 작은 a와 b는 10으로 합쳐진 뒤 더 아래로 내려가 있다. 가장 긴 코드가 3비트일 수 없으므로 옳지 않다.
1과 9를 합쳐 10, 10과 11을 합쳐 21, 12와 18을 합쳐 30, 21과 30을 합쳐 51, 48과 51을 합쳐 99를 만든다. 빈도 1과 9의 문자가 루트에서 네 칸이라 4비트이므로 옳다(정답).
5비트까지 깊어지려면 빈도가 두 배씩 뛰는 사슬형 병합이 필요하다. 이 문제는 10, 11, 12, 18처럼 빈도가 가까워 균형 있게 합쳐지므로 5비트는 옳지 않다.

🧮 풀이

甲은 문자 6개를 2비트로 표현하려면 만들 수 있는 코드가 최대 4개뿐이라는 것을 셌다. 여섯 문자를 다 담을 수 없어 2가 답이 될 수 없다고 판단하고 보기 옆에 가위표를 쳐 두었다.
甲은 완성된 트리에서 e, f, c가 루트로부터 세 칸 아래에 있는 것을 세고 3이 최댓값이라 적었다. 그러나 a와 b는 10으로 묶여 더 아래로 내려가 있어 3이 최댓값이 아님을 그림으로 확인했다.
甲은 빈도가 가장 작은 두 값부터 반복해 합치며 10, 21, 30, 51, 99를 차례로 만들어 트리를 그렸다. 1과 9가 붙은 잎이 뿌리에서 네 단계 아래에 놓인 것을 세어 코드 길이가 4비트라고 적었다.
甲은 빈도가 두 배씩 뛰는 예에서 사슬형 트리로 깊이가 깊어지는 것을 그렸다. 이번 빈도는 10, 11, 12, 18처럼 가까워 그런 사슬이 안 생기니 5비트까지는 안 간다고 표시했다.

가장 작은 빈도 두 개씩 합치면 빈도 1과 9의 문자가 루트에서 네 칸 아래에 놓여 가장 긴 코드는 4비트다.

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

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

1. O(1)
2. O(logn)
3. O(n)
4. Θ (2^n)

정답 3번

🔍 보기별 해설

입력이 커지면 호출도 n번으로 늘어나므로 수행 시간이 입력과 무관한 상수일 수 없다. abc(n)은 abc(n-1)을 반복해 부르므로 O(1)은 옳지 않다.
O(log n)은 매번 입력을 절반으로 줄일 때 나오는 시간이다. 이 코드는 n을 하나씩만 줄이므로 호출이 n번 이어져 로그 시간이 아니므로 옳지 않다.
호출마다 곱셈 한 번이 들고 n이 하나씩 줄어 n번 호출되므로 T(n)=T(n-1)+c를 펼치면 cn이 된다. 시간은 n에 비례하므로 옳다(정답).
지수 시간은 호출이 두 갈래로 갈라지는 피보나치형 재귀에서 나온다. 이 코드는 호출이 한 갈래뿐이라 Θ(2^n)까지 커지지 않으므로 옳지 않다.

🧮 풀이

甲은 n=5로 abc(5)를 따라가며 abc(4), abc(3), abc(2), abc(1)까지 부르는 횟수를 세었다. 입력이 커질수록 호출 수도 커지므로 상수가 아니라고 적었다.
甲은 이진 탐색이 매번 절반씩 줄어 로그 시간이 되는 그림을 그리고 abc(n)과 견주었다. abc는 n에서 1씩만 줄어 호출이 n번 이어지므로 그 그림과는 다르다고 적었다.
甲은 abc(n)의 수행 시간을 T(n)=T(n-1)+c로 세워 n번 펼쳐 보았다. c가 n번 더해지므로 T(n)=cn이라 O(n)임을 식으로 적고 답 칸에 표시해 두었다.
甲은 피보나치 재귀가 fib(n-1)과 fib(n-2) 두 개를 함께 부르며 호출이 두 배 가까이 늘어나는 트리를 그렸다. abc는 호출을 하나만 하니 그런 지수 증가가 없다고 적었다.

abc(n)은 abc(n-1)을 한 번씩만 부르며 n에서 1까지 내려가므로 T(n)=T(n-1)+c, 즉 O(n)이다.

9급 데이터 기출 80문항 · 자동복습과 예상점수까지 무료로 →

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

1. 4
2. 8
3. 16
4. 32

정답 3번

🔍 보기별 해설

4는 정점의 수일 뿐이다. 간선 6개에서 3개를 고르는 방법만 20가지이고 그중 사이클이 되는 4가지만 빼도 16가지가 남아 4로는 너무 적으므로 옳지 않다.
8은 실제 신장 트리 수 16의 절반이다. 간선 세 개를 고르는 20가지에서 사이클인 삼각형 4가지만 빼면 나머지가 모두 신장 트리이므로 옳지 않다.
정점이 네 개인 완전그래프의 신장 트리는 간선 세 개의 조합 20가지에서 삼각형 4가지를 뺀 16개다. 케일리의 공식 4의 2제곱과도 같으므로 옳다(정답).
32는 간선 세 개를 고르는 조합의 총수 20을 넘는 값이다. 신장 트리는 그 20가지 안에서만 나오므로 32가 될 수 없어 옳지 않다.

🧮 풀이

甲은 정점이 4개라는 점만 보고 답을 4라고 적었다. 그림의 간선이 여섯 개이고 그중 세 개씩 고르는 방법이 20가지나 되는 것을 세어 보고 4로는 너무 적다고 고쳐 적었다.
甲은 간선 여섯 개에서 세 개를 고르는 20가지 가운데 절반쯤만 신장 트리일 것이라 짐작해 8을 적어 보았다. 삼각형 4가지만 빼면 16가지가 남는 것을 확인하고 8이 부족하다고 정정했다.
甲은 간선 6개에서 3개를 고르는 20가지에서 세 정점이 이루는 삼각형 4가지를 사이클로 지웠다. 남은 16가지가 모두 신장 트리이며 케일리의 공식 4의 2제곱과 같다고 적었다.
甲은 정점 4개인 완전그래프의 신장 트리가 32개일 것이라는 친구의 말을 듣고 20가지 간선 조합보다 많을 수 없다고 반박했다. 간선 3개 조합이 20가지뿐이므로 상한이 20이라고 적어 보여 주었다.

정점 4개의 완전그래프 신장 트리는 간선 6개에서 3개를 고르는 20가지에서 삼각형 4가지를 뺀 16개다.

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

정답 3번

🔍 보기별 해설

첫째 그림은 사이클이 없는 방향 그래프다. 진입 차수 0인 A부터 차례로 지워 가면 남는 정점이 끊기지 않고 모두 뽑히므로 옳지 않다.
둘째 그림은 A에서 D, E, B, F를 지나 C와 G로 이어져 사이클이 없다. 정점을 지워 갈 때마다 진입 차수 0인 정점이 남아 일곱 정점이 모두 나오므로 옳지 않다.
셋째 그림은 B에서 F, F에서 C, C에서 다시 B로 돌아오는 사이클이 있다. 진입 차수 0인 정점이 A뿐이고 그 뒤로는 하나도 남지 않아 모든 정점을 포함하는 결과가 생성될 수 없으므로 옳다(정답).
넷째 그림은 E에서 D, A, B를 거쳐 C, G, F로 이어지는 한 방향 사슬로 사이클이 없다. 모든 정점을 순서대로 뽑을 수 있으므로 옳지 않다.

🧮 풀이

甲은 첫째 그림에서 진입 차수 0인 A를 지우고 그다음 B와 D, 이어서 나머지를 차례로 지워 나갔다. 일곱 정점이 하나도 남지 않고 다 나오는 것을 보고 이 그림을 후보에서 지워 두었다.
甲은 둘째 그림에서 E에서 B로 향하는 간선을 발견하고 A, D, E를 먼저 지운 뒤 B, F, C, G 순으로 이어 지웠다. 순환 없이 모두 뽑히자 그림 아래 위상 순서를 적어 두었다.
甲은 셋째 그림에서 진입 차수 0인 정점이 A뿐인 것을 보고 A를 지웠다. 이후 진입 차수가 0이 되는 정점이 더는 없어 여섯 정점이 남은 채 멈추자 여기에 사이클이 있다고 적었다.
甲은 넷째 그림에서 E와 D, A를 지나 B, C, G, F까지 이어지는 한 줄 순서를 찾았다. 화살표가 한 방향으로만 이어진 사슬이라 모든 정점이 포함된다고 결론지어 적었다.

위상 정렬은 사이클이 없는 방향 그래프에서만 모든 정점을 늘어놓을 수 있다. 셋째 그림에는 B, F, C를 도는 사이클이 있다.

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

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

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

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

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

1. 프림(Prim) 알고리즘
2. 플로이드－워셜(Floyd-Warshall) 알고리즘
3. 다익스트라(Dijkstra) 알고리즘
4. KMP(Knuth-Morris-Pratt) 알고리즘

정답 2번

🔍 보기별 해설

프림은 모든 정점을 잇는 최소 가중치 신장 트리를 만드는 알고리즘이다. 정점 쌍마다 최단 거리를 구하는 설명과 맞지 않으므로 옳지 않다.
플로이드-워셜은 중간 정점을 하나씩 늘려 가며 모든 정점 쌍의 최단 거리를 표로 갱신하는 동적 계획법이다. 삼중 반복문이라 O(n^3)이고 음수 간선도 허용하므로 옳다(정답).
다익스트라는 한 출발점에서 다른 모든 정점까지의 최단 거리를 구하는 그리디 알고리즘이다. 음수 간선이 있으면 이미 확정한 값이 틀릴 수 있어 설명과 맞지 않으므로 옳지 않다.
KMP는 텍스트에서 패턴 문자열을 찾는 문자열 매칭 알고리즘이다. 그래프의 최단 거리와는 관계가 없는 알고리즘이므로 옳지 않다.

🧮 풀이

甲은 도시 지도에서 도로를 가장 싼 것부터 붙여 모든 도시를 잇는 최소 비용 망을 만들었다. 이는 두 도시 사이 최단 거리를 구한 것이 아니라 신장 트리를 만든 것이라 설명과 다르다고 표시했다.
甲은 정점 세 개짜리 표에서 중간 정점 k를 하나씩 바꿔 가며 D[i][j]를 D[i][k]+D[k][j]와 견주었다. 세 겹 반복이라 n^3이며 음수 사이클만 없으면 음수 간선이 있어도 계산이 끝나는 것을 확인했다.
甲은 한 도시에서 나머지 도시들까지 가는 최단 거리를 우선순위 큐로 구하는 코드를 돌렸다. 간선 하나를 음수로 바꾸자 먼저 확정해 둔 값이 뒤집힐 수 있다는 점이 걸려 음수 간선에는 쓰지 못한다고 적어 두었다.
甲은 텍스트에서 패턴을 찾는 실패 표를 만들어 KMP로 비교해 보았다. 그래프가 아니라 문자열을 다루는 알고리즘이라 모든 쌍 최단 거리와는 상관이 없다고 노트 옆에 적었다.

모든 쌍 최단 거리, 음수 간선 허용, 동적 계획법, O(n^3)이면 플로이드-워셜이다.

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

void foo(int n) {

if(n != 0){

foo(n/2);

printf("%d", n%2);

}

1. 1010
2. 1011
3. 1100
4. 1101

정답 4번

🔍 보기별 해설

1010은 십진수 10의 이진 표기다. 13은 6, 3, 1로 절반씩 줄며 나머지가 되돌아오면서 1, 1, 0, 1 순으로 찍히므로 옳지 않다.
1011은 printf를 재귀 호출 앞에 두었을 때 낮은 자리부터 찍히는 역순 결과다. 이 코드는 호출이 돌아온 뒤 출력하므로 높은 자리부터 나와 1101이 되어 옳지 않다.
1100은 십진수 12의 이진 표기다. 13은 가장 낮은 자리 나머지가 13%2=1이어야 하는데 이 값은 0으로 끝나므로 옳지 않다.
foo(13)은 foo(6), foo(3), foo(1), foo(0)을 차례로 부른 뒤 되돌아오며 1%2, 3%2, 6%2, 13%2를 찍는다. 출력이 1, 1, 0, 1 순이라 1101이므로 옳다(정답).

🧮 풀이

甲은 10을 이진수로 바꾸면 1010이 되는 것을 확인하고 13과 혼동하지 않도록 나눗셈 표로 다시 계산했다. 13을 2로 나눈 몫과 나머지를 적어 값이 10이 아님을 확인했다.
甲은 printf를 재귀 호출 앞으로 옮긴 코드를 돌려 13에서 1, 0, 1, 1 순으로 찍히는 것을 보았다. 원래 코드는 돌아오며 찍어 순서가 뒤집히므로 1011이 나오지 않는다고 적었다.
甲은 12를 2로 나눠 몫과 나머지를 적으니 가장 낮은 자리 나머지가 0이라는 것을 발견했다. 13은 그 자리가 1이어야 하므로 1100은 12의 이진수라고 옆에 표시했다.
甲은 13을 반으로 나누며 6, 3, 1, 0까지 내려가는 호출 목록을 세로로 적었다. 맨 아래에서 위로 올라오며 나머지를 하나씩 찍어 1101이 만들어지는 것을 표에 옮겼다.

foo(13)은 13, 6, 3, 1까지 내려간 뒤 되돌아오며 나머지 1, 1, 0, 1을 출력해 이진수 1101이 된다.

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

1. 1
2. 3
3. 5
4. 6

정답 4번

🔍 보기별 해설

1은 첫 위치에서 한 번 비교하고 끝나는 경우의 값이다. 첫 글자가 맞은 뒤 둘째 글자에서 어긋나고 패턴을 밀어 다시 견주어야 하므로 비교가 훨씬 많아 옳지 않다.
3은 패턴을 밀어 본 시작 위치의 수일 뿐 비교 횟수가 아니다. 위치마다 견주는 글자 수가 달라 실제 합은 그보다 크므로 옳지 않다.
5는 시작 위치 2에서 001을 견주는 세 번의 비교 가운데 마지막 하나를 빠뜨린 값이다. 셋째 글자 1과 1이 같은지도 견주어야 하므로 옳지 않다.
위치 0에서는 0과 0이 맞고 1과 0이 어긋나 2번, 위치 1에서는 1과 0이 어긋나 1번, 위치 2에서는 세 글자가 모두 맞아 3번이다. 합이 6번이므로 옳다(정답).

🧮 풀이

甲은 텍스트 01001 위에 패턴 001을 올려 놓고 맨 앞 두 칸만 견주어 끝났다고 가정했다. 첫 칸이 맞은 뒤 둘째 칸이 어긋나 패턴을 한 칸 밀어 다시 견주어야 해서 1은 될 수 없다고 적었다.
甲은 패턴을 밀어 본 시작 위치가 0, 1, 2 세 곳뿐인 것을 세어 비교 횟수도 3이라고 적었다. 그러나 위치마다 견주는 글자 수가 달라 3은 위치의 수일 뿐 비교 횟수가 아니라고 정정했다.
甲은 시작 위치 2에서 001과 견주는 세 번의 비교를 두 번까지만 세고 마지막 글자 비교를 빠뜨려 합을 5로 냈다. 셋째 글자 1과 1이 같은지 견주는 줄이 빠진 것을 찾아 넣었다.
甲은 위치 0에서 2번, 위치 1에서 1번, 위치 2에서 3번 비교한 표를 만들었다. 2, 1, 3을 더해 6번이라 적고 위치 2에서 패턴이 다 맞아 검색을 멈춘 줄에 표시했다.

시작 위치 0에서 2번, 위치 1에서 1번, 위치 2에서 3번 비교해 모두 6번이다.

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

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

ㄴ. 병합 정렬 알고리즘

ㄷ. 다익스트라 알고리즘

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

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

정답 1번

🔍 보기별 해설

다익스트라는 확정되지 않은 정점 중 최단 거리인 것을 매번 골라 확정하는 그리디다. 나머지 셋은 각각 해시, 분할정복, 동적 계획법이라 ㄷ 하나만 남는 이 묶음이 맞다.
ㄱ 라빈-카프는 해시값으로 문자열을 찾는 방법이고 ㄴ 병합 정렬은 분할정복이다. 둘 다 그리디가 아닌데 그리디인 ㄷ은 빠졌으므로 옳지 않다.
ㄷ은 그리디가 맞지만 ㄱ 라빈-카프가 함께 묶였다. 라빈-카프는 매 단계 최선을 고르는 방식이 아니라 해시 비교로 문자열을 찾는 알고리즘이므로 옳지 않다.
ㄷ은 그리디가 맞지만 ㄱ은 해시 문자열 매칭이고 ㄹ 플로이드-워셜은 동적 계획법이다. 그리디가 아닌 둘이 섞였으므로 옳지 않다.

🧮 풀이

甲은 네 알고리즘 이름 옆에 설계 기법을 적는 표를 만들었다. 다익스트라 칸에만 매번 가장 가까운 정점을 확정한다고 적어 그리디로 분류하고 나머지 세 칸은 다른 기법으로 채웠다.
甲은 라빈-카프가 해시로 패턴을 견주는 그림과 병합 정렬이 절반으로 나누고 합치는 그림을 나란히 그렸다. 둘 다 매 단계 최선을 고르는 방식이 아니어서 그리디 후보에서 지웠다.
甲은 라빈-카프와 다익스트라를 함께 묶은 답을 하나 검토했다. 다익스트라는 그리디이지만 라빈-카프는 해시값을 견주어 문자열을 찾는 방법이라 한 묶음이 될 수 없다고 노트 옆에 적었다.
甲은 플로이드-워셜의 삼중 반복문에서 중간 정점을 늘려 가며 표를 갱신하는 과정을 손으로 계산했다. 앞 단계 표를 다시 쓰는 동적 계획법이라 그리디 묶음에서 빼고 답 표에 지운 자국을 남겼다.

그리디는 다익스트라뿐이다. 라빈-카프는 해시 문자열 매칭, 병합 정렬은 분할정복, 플로이드-워셜은 동적 계획법이다. 정답은 1번.

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

1. 피벗(pivot)을 최대값으로 정한다.
2. 피벗을 랜덤(random)하게 정한다.
3. 피벗을 중간값(median)으로 정한다.
4. 피벗을 파티션(partition)의 중간에 위치한 값으로 정한다.

정답 1번

🔍 보기별 해설

피벗을 최댓값으로 정하면 나머지 n-1개가 한쪽에만 몰려 분할이 매번 치우친다. 재귀 깊이가 n이 되어 O(n^2)이 되는 최악의 경우이므로 옳다(정답).
피벗을 무작위로 정하면 평균적으로 균형 잡힌 분할이 나오고 극단적으로 치우친 분할이 계속될 확률은 매우 낮다. 최악을 만드는 방법으로는 적절하지 않으므로 옳지 않다.
피벗을 중앙값으로 정하면 양쪽에 거의 같은 개수가 나뉘어 재귀 깊이가 log n에 그친다. O(n log n)이 나오는 좋은 경우이므로 옳지 않다.
분할 구간의 가운데 위치에 있는 값을 피벗으로 삼으면 정렬된 입력에서도 양쪽이 반반에 가깝게 나뉜다. 최악을 일으키는 방법으로는 적절하지 않으므로 옳지 않다.

🧮 풀이

甲은 이미 오름차순인 1부터 8까지에서 항상 마지막 값을 피벗으로 잡아 분할하는 과정을 그렸다. 매번 한쪽에만 원소가 다 몰려 재귀가 여덟 단계 이어지는 것을 보고 최악이라고 적었다.
甲은 피벗을 난수로 고르는 프로그램을 여러 번 돌려 분할이 그때그때 다른 위치에서 일어나는 것을 기록했다. 극단적으로 치우친 분할이 계속 이어질 확률은 아주 작다는 점을 표로 남겼다.
甲은 값이 1부터 8까지인 배열에서 피벗을 중앙값 4나 5로 잡아 양쪽에 비슷한 개수가 나뉘는 트리를 그렸다. 트리의 깊이가 log n에 그쳐 최악이 아님을 그림 옆에 적었다.
甲은 분할 구간 가운데 자리에 놓인 값을 피벗으로 삼는 코드를 돌려 양쪽 개수를 세어 보았다. 정렬된 입력에서도 반반에 가깝게 나뉘어 최악을 일으키는 사례로는 부족하다고 적었다.

피벗이 늘 최댓값이나 최솟값이면 분할이 n-1개와 0개로 치우쳐 재귀 깊이가 n이 되고 O(n^2)이 된다.

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

1. 61
2. 62
3. 63
4. 64

정답 3번

🔍 보기별 해설

61은 라운드별 경기 수 32, 16, 8, 4, 1을 더한 값이다. 준결승 2경기를 빠뜨렸으므로 실제 경기 수 63과 맞지 않아 옳지 않다.
62는 라운드별 경기 수 32, 16, 8, 4, 2를 더한 값이다. 결승 1경기를 빠뜨렸으므로 63보다 하나 모자라 옳지 않다.
64팀이 32, 16, 8, 4, 2, 1경기의 여섯 라운드를 거치므로 합이 63번이다. 경기마다 한 팀이 탈락해 우승 팀을 뺀 63팀이 떨어지는 셈과도 같아 옳다(정답).
64는 팀 수와 같은 값이다. 우승 팀은 탈락하지 않으므로 경기 수는 팀 수보다 하나 적어야 하고 64가 될 수 없어 옳지 않다.

🧮 풀이

甲은 라운드별 경기 수를 32, 16, 8, 4, 1로 적어 더하다가 61이 나오자 이상하게 여겼다. 준결승 2경기를 적은 줄이 빠진 것을 찾아 넣어 합을 다시 더해 보았다.
甲은 32, 16, 8, 4, 2까지만 더해 62를 얻고 결승 1경기를 빠뜨린 것을 나중에 알았다. 결승 경기 수를 적은 줄을 표 끝에 하나 더해 넣고 합계를 다시 확인해 두었다.
甲은 경기마다 한 팀이 탈락하므로 우승 팀 하나만 남으려면 63팀이 떨어져야 한다는 논리를 세웠다. 라운드별 경기 수를 더한 표의 합 63과 맞아떨어지는 것을 보고 답 칸에 적어 넣었다.
甲은 팀 수 64를 그대로 경기 수로 적었다가 각 경기에서 한 팀만 탈락하는 점을 다시 읽었다. 우승팀은 탈락하지 않으니 경기 수가 64가 아니라 하나 적어야 한다고 고쳐 적었다.

경기마다 한 팀이 탈락하므로 64팀 중 1등을 가리려면 63팀이 떨어져야 하고 경기는 63번이다.

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

어떤 문제 A가 다음을 모두 만족하면 (가) 이다.

○ 문제 A는 NP에 속한다.

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

1. P 문제
2. NP 문제
3. NP－하드(NP-hard) 문제
4. NP－완전(NP-complete) 문제

정답 4번

🔍 보기별 해설

P는 다항 시간에 풀 수 있는 문제의 모임이다. P≠NP라면 모든 NP 문제를 P 문제로 옮길 수 없으므로 두 번째 조건이 성립하지 않아 옳지 않다.
NP는 해가 주어졌을 때 다항 시간에 검증할 수 있는 문제의 모임이다. 문제 A가 NP에 속한다는 첫 조건일 뿐이라 두 조건을 모두 담지 못하므로 옳지 않다.
NP-하드는 모든 NP 문제를 다항 시간에 옮겨 올 수 있다는 둘째 조건만 만족해도 된다. NP에 속한다는 첫 조건까지 함께 만족하는 문제는 그보다 좁은 NP-완전이므로 옳지 않다.
NP에 속하고 모든 NP 문제가 다항 시간에 이 문제로 변환되는 두 조건을 모두 만족하면 NP-완전 문제이다. 정의와 정확히 맞으므로 옳다(정답).

🧮 풀이

甲은 정렬처럼 빠르게 풀리는 문제를 P 칸에 묶었다. 이런 문제로 NP 전체를 바꿔 풀 수 있다면 P와 NP가 같아지는 셈이라, 전제와 어긋나 둘째 조건은 채워지지 않는다고 메모해 두었다.
甲은 해가 주어졌을 때 다항 시간에 맞는지 확인만 하면 되는 문제들을 NP로 묶었다. 그 안에는 첫 조건만 만족하는 쉬운 문제도 들어 있어 두 조건을 모두 만족하는 것과 같지 않다고 표시했다.
甲은 NP에 속하지 않는 정지 문제를 예로 떠올렸다. 모든 NP 문제를 옮겨 올 수 있으나 NP 소속이 아니므로 둘째 조건만 만족한다고 적어 NP-하드와 NP-완전을 구분했다.
甲은 3-SAT을 예로 들어 해를 넣고 다항 시간에 검증할 수 있음과 다른 NP 문제를 이 문제로 옮길 수 있음을 확인했다. 두 조건에 모두 표시하고 NP-완전 칸에 넣어 두었다.

NP에 속하면서 모든 NP 문제를 다항 시간에 이 문제로 변환할 수 있으면 NP-완전이다.

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

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

1. T (n) = T ({n / 2}) + c , Θ (n)
2. T (n) = T ({n / 2}) + c , Θ (log_2 n)
3. T (n) = 2T ({n / 2}) + c , Θ (n)
4. T (n) = 2T ({n / 2}) + n , Θ (n log_2 n)

정답 2번

🔍 보기별 해설

식 T(n)=T(n/2)+c는 맞지만 결과가 Θ(n)은 아니다. n을 절반씩 줄이면 log2 n번 만에 1이 되고 호출마다 c가 들어 Θ(log2 n)이므로 옳지 않다.
algo(n)은 algo(n/2)를 한 번만 부르고 상수 c의 일을 하므로 T(n)=T(n/2)+c다. n을 절반씩 줄여 log2 n번 만에 끝나므로 Θ(log2 n)이라서 옳다(정답).
식에 2T(n/2)가 들어 있어 재귀 호출이 두 번이라고 말하는데, 이 코드의 호출은 한 번뿐이다. 호출 수와 식의 계수가 맞지 않으므로 옳지 않다.
2T(n/2)+n은 절반씩 나눈 두 문제를 풀고 합치는 데 n이 드는 병합 정렬형 점화식이다. 이 코드에는 두 번째 호출도 합치는 비용도 없으므로 옳지 않다.

🧮 풀이

甲은 algo(16)을 따라가 algo(8), algo(4), algo(2), algo(1)로 다섯 번 호출됨을 세었다. 호출당 상수 c이고 n이 절반씩 줄어 다섯 번뿐이라 n에 비례하지 않는다고 적었다.
甲은 n을 2로 계속 나누면 몇 번 만에 1이 되는지를 n=1024에서 세어 10번임을 얻었다. 호출마다 c씩 드니 c·log2 n이라 식으로 정리해 Θ(log2 n)이라고 적었다.
甲은 함수 본문에 재귀 호출이 한 번뿐인데 식에 2T가 적힌 보기를 훑어보았다. 호출 수와 식의 계수가 서로 맞지 않는다는 점을 짚어 그 보기를 후보 목록에서 지워 두었다.
甲은 병합 정렬이 두 절반을 각각 정렬하고 합치는 데 n이 드는 2T(n/2)+n의 형태임을 떠올렸다. 이 코드에는 합치는 비용도 두 번째 호출도 없어 그 식은 병합 정렬에 해당한다고 옆에 적었다.

호출이 하나이고 n을 절반으로 줄이므로 T(n)=T(n/2)+c이며 c가 log2 n번 더해져 Θ(log2 n)이다.

9급 데이터 기출 80문항 · 자동복습과 예상점수까지 무료로 →

다음 정수 열에서 연속 부분합의 최댓값은?

1, －3, 2, 4, －1, 5, －3, 2, 1, －2

1. 5
2. 8
3. 10
4. 15

정답 3번

🔍 보기별 해설

여섯째 항 5 하나만 고른 값이다. 바로 앞의 4와 -1을 이어 셋째 항 2부터 5까지 합치면 10이 되어 훨씬 크므로 옳지 않다.
첫 항부터 아홉째 항까지 이으면 8이 나온다. 하지만 앞의 1과 -3을 빼고 셋째 항부터 이으면 더 큰 값이 나와 최댓값이 못 되므로 옳지 않다.
셋째 항 2부터 여섯째 항 5까지 2, 4, -1, 5를 잇는 합이 10이다. 뒤의 -3, 2, 1을 더해도 0이라 그대로 10이 유지되며 이보다 큰 연속 구간은 없으므로 옳다(정답).
15는 음수를 빼고 양수 1, 2, 4, 5, 2, 1을 모두 더한 값이다. 사이에 낀 -3과 -1을 건너뛰면 연속 부분이 될 수 없으므로 옳지 않다.

🧮 풀이

甲은 열흘치 손익표에서 가장 큰 하루 값인 5만 최고 구간이라 적었다. 앞의 2, 4, -1을 붙여 합쳐 보니 10이 되어 처음에 적어 둔 답을 두 줄로 그어 지우고 새 값을 옆에 적었다.
甲은 첫날부터 아흐레째까지 모두 더해 8을 얻고 이것을 최댓값으로 삼으려 했다. 첫 이틀을 빼고 셋째 날부터 잡아 다시 더하자 값이 더 커지는 것을 표 옆에 적어 두었다.
甲은 손익표에 셋째 날부터 여섯째 날까지 괄호를 치고 2, 4, -1, 5를 차례로 더해 10을 적었다. 구간 끝을 한 칸씩 늘려 보아도 더 커지지 않아 그 괄호를 굵게 덧그렸다.
甲은 양수 칸만 형광펜으로 칠해 모두 더하고 15라는 값을 얻었다. 사이의 -3과 -1을 건너뛴 합이라 연속 구간이 못 됨을 알고 형광펜 자국 위에 큼직한 가위표를 쳤다.

연속 부분합의 최댓값은 2, 4, -1, 5를 잇는 10이다. 양수만 모은 15는 연속이 아니라서 답이 될 수 없다.

이진 탐색(binary search) 알고리즘에 대한 설명으로 옳지 않은 것은?

1. 탐색 범위가 절반씩 줄어든다.
2. 탐색할 데이터는 순서 없이 저장되어 있다.
3. 시간 복잡도는 O (logn) 이다.
4. 1,000개의 데이터가 존재하는 경우, 최대 10회의 탐색으로 완료된다.

정답 2번

🔍 보기별 해설

비교할 때마다 가운데 값을 기준으로 한쪽을 통째로 버리므로 남은 범위가 절반으로 줄어든다. 이진 탐색의 핵심 동작을 바르게 말한 설명이라 맞다.
이진 탐색은 가운데 값과 비교해 어느 쪽에 있는지 판단하므로 데이터가 미리 정렬되어 있어야 한다. 순서 없이 저장된 배열에서는 한쪽을 버릴 근거가 없으므로 옳지 않다(정답).
범위를 절반씩 줄이므로 비교 횟수가 n을 2로 몇 번 나누어야 1이 되느냐로 정해져 로그 n에 비례한다. 이진 탐색의 복잡도를 바르게 말한 설명이라 맞다.
1,000개는 2의 9제곱인 512보다 크고 2의 10제곱인 1,024보다 작아서 범위를 최대 열 번 줄이면 끝난다. 최악의 비교 횟수 계산과 맞는 설명이라 맞다.

🧮 풀이

甲은 사전에서 단어를 찾으며 책을 가운데쯤에서 펼쳤다. 찾는 단어가 앞쪽이면 뒤쪽 반을 통째로 넘기고 남은 반에서 다시 가운데를 펼치는 방식으로 쪽수를 차근차근 좁혀 갔다.
甲은 번호표가 뒤섞여 쌓인 서류함에서 가운데 서류를 꺼내 번호를 살폈다. 그 번호가 크든 작든 어느 쪽에 있는지 알 수 없어 번호순 정리부터 하기로 하고 번호를 매겨 두었다.
甲은 명단이 1,000명에서 2,000명으로 두 배가 될 때 확인 횟수가 한 번만 늘어난다는 표를 만들었다. 학생 수가 열 배가 되어도 비교가 서너 번밖에 늘지 않는 곡선을 그래프로 그려 두었다.
甲은 1,000을 계속 절반으로 나누는 계산을 종이에 적었다. 500, 250, 125로 줄어 열 번 나누면 1 아래로 내려가는 것을 세어 보고 옆에 최대 열 번이라고 적었다.

이진 탐색은 정렬된 데이터에서 범위를 절반씩 줄이며 O(log n)에 찾는다. 순서 없는 데이터에는 쓸 수 없다.

동적 계획법(dynamic programming)으로 설계된 알고리즘의 동작 방식에 대한 설명으로 옳지 않은 것은?

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복해서 사용되며, 이 작은 문제들의 결괏값을 저장해 두고 활용한다.
3. 상향식(bottom-up) 접근 방식 또는 하향식(top-down) 접근 방식으로 구현할 수 있다.
4. 메모하기(memoization) 방법을 활용하여 연산과 탐색이 증가하고 실행속도가 저하된다.

정답 4번

🔍 보기별 해설

큰 문제를 겹치는 작은 부분 문제로 쪼갤 수 있어야 동적 계획법을 적용할 수 있다. 문제 분해 조건을 바르게 말한 설명이라 맞다.
같은 부분 문제가 여러 번 나오기 때문에 한 번 푼 결과를 표에 저장해 두고 다시 꺼내 쓴다. 중복 계산을 피하는 동적 계획법의 핵심을 바르게 말한 설명이라 맞다.
작은 문제부터 표를 채워 올라가는 상향식과 큰 문제에서 시작해 재귀로 내려가는 하향식 두 방식 모두로 구현할 수 있다. 구현 방식을 바르게 말한 설명이라 맞다.
메모하기는 한 번 구한 값을 저장해 두고 다시 계산하지 않는 기법이라 반복 연산을 오히려 줄여 실행 속도를 높여 준다. 증가하고 저하된다는 서술은 정반대이므로 옳지 않다(정답).

🧮 풀이

甲은 계단 오르기 경우의 수 문제를 풀며 10칸 문제를 9칸과 8칸 문제로 나눠 적었다. 그 두 문제가 다시 더 작은 문제로 갈라지는 나무를 그리다가 나눌 수 있다는 점을 짚어 보았다.
甲은 피보나치 f(5)를 재귀로 전개하다 f(3)이 두 번 나오는 것을 발견했다. 두 번째부터는 계산하지 않고 이미 구한 값을 표에서 가져오도록 f(3)의 결과를 표 안에 적어 두었다.
甲은 같은 문제를 두 가지로 짰다. 하나는 f(1)부터 표를 채워 올라가는 반복문이고 다른 하나는 f(n)에서 재귀로 내려가는 방식인데 두 코드가 같은 값을 내는 것을 실행해 견주었다.
甲은 메모를 붙인 피보나치 함수와 붙이지 않은 함수를 n이 40일 때 각각 실행해 보았다. 메모를 붙인 쪽이 눈 깜짝할 새에 끝나고 붙이지 않은 쪽은 한참 걸려 소요 시간을 표에 나란히 적었다.

동적 계획법은 겹치는 부분 문제의 결과를 저장해 재사용한다. 메모하기는 연산을 줄여 속도를 높인다.

다음 정렬 알고리즘 중에서 동일한 최악 시간 복잡도를 가진 것만을 모두 고르면?

ㄱ. 선택 정렬(selection sort)

ㄴ. 삽입 정렬(insertion sort)

ㄷ. 힙 정렬(heap sort)

ㄹ. 퀵 정렬(quick sort)

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

정답 2번

🔍 보기별 해설

선택 정렬과 삽입 정렬은 최악에 n제곱이지만 힙 정렬은 어떤 입력에서도 n log n으로 끝난다. 힙 정렬을 함께 묶으면 복잡도가 갈라지므로 옳지 않다.
선택 정렬은 항상 n제곱, 삽입 정렬은 역순 입력에서 n제곱, 퀵 정렬은 기준이 한쪽으로만 쏠릴 때 n제곱이라 최악이 모두 같다. 세 가지를 묶은 이 묶음이 맞다.
힙 정렬은 최악에도 n log n인데 선택과 퀵은 n제곱이라 힙 정렬이 낀 이 묶음은 최악 복잡도가 셋으로 갈라진다. 세 정렬이 같은 값을 갖지 않으므로 옳지 않다.
삽입과 퀵은 최악이 n제곱이나 힙은 n log n이라 서로 차이가 난다. 힙 정렬을 넣은 이 묶음도 세 알고리즘의 최악 복잡도가 한 줄로 이어지지 않으므로 옳지 않다.

🧮 풀이

甲은 선택, 삽입, 힙 정렬에 역순 배열을 넣어 비교 횟수를 세어 보았다. 앞의 둘은 입력 크기의 제곱꼴로 늘었지만 힙 정렬만 로그가 붙은 곡선을 그려 세 개를 한 묶음으로 잡을 수 없었다.
甲은 이미 오름차순인 배열을 퀵 정렬에 넣고 맨 앞 값을 기준으로 삼아 보았다. 기준이 언제나 가장 작아 한쪽으로 쏠리며 선택·삽입 정렬처럼 제곱 횟수가 나오자 세 알고리즘 옆에 같은 표시를 달았다.
甲은 선택, 힙, 퀵 정렬을 최악 입력에서 각각 돌려 걸린 시간을 쟀다. 힙 정렬만 눈에 띄게 빨라 다른 둘과 같은 자리에 묶을 수 없는 것을 그래프에서 확인하고 힙에 별표를 쳤다.
甲은 삽입, 힙, 퀵 정렬의 최악 복잡도를 교재 표에서 찾아 나란히 옮겨 적었다. 삽입과 퀵은 제곱, 힙은 로그가 붙은 꼴이라 한 줄로 이어지지 않아 힙 정렬 칸에만 색을 칠해 구분했다.

선택·삽입·퀵 정렬의 최악은 n제곱이고 힙 정렬만 n log n이다. 정답은 2번.

그림과 같은 과정을 포함하여 정렬을 실행하는 알고리즘은?

1. 퀵 정렬
2. 셸 정렬(shell sort)
3. 기수 정렬(radix sort)
4. 병합 정렬(merge sort)

정답 4번

🔍 보기별 해설

퀵 정렬은 기준값을 골라 작은 값과 큰 값으로 나누는 것이 핵심이다. 그림처럼 이미 정렬된 두 묶음을 앞에서부터 비교해 하나로 이어 붙이는 과정은 없으므로 옳지 않다.
셸 정렬은 일정한 간격만큼 떨어진 원소끼리 삽입 정렬을 하고 간격을 줄여 가는 방식이다. 묶음을 둘씩 합쳐 올라가는 그림의 모양과 다르므로 옳지 않다.
기수 정렬은 값을 비교하지 않고 자릿수별로 나눠 담았다 꺼내며 정렬한다. 그림처럼 정렬된 두 묶음을 합치는 단계가 없으므로 옳지 않다.
낱개로 쪼갠 뒤 두 묶음씩 정렬하며 합쳐 마지막에 하나의 정렬된 배열을 만드는 과정이 그림과 같다. 병합 정렬의 합치기 단계가 그대로 나타나므로 옳다(정답).

🧮 풀이

甲은 퀵 정렬을 손으로 따라가며 맨 앞 값을 기준으로 잡았다. 기준보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 갈라 세우고 기준을 가운데에 세워 두는 그림을 세 번 그렸다.
甲은 열 개짜리 배열에 간격을 5, 2, 1로 줄여 가며 셸 정렬을 적용했다. 간격이 5일 때 멀리 떨어진 두 원소끼리 짝지어 순서를 바꾸는 단계를 색연필로 이어 표시했다.
甲은 세 자리 수 카드를 일의 자리부터 0에서 9까지 통에 나눠 담았다. 통에서 차례로 꺼낸 카드를 십의 자리, 백의 자리로 다시 나눠 담으며 한 번도 두 수를 견주지 않았다.
甲은 카드 여덟 장을 한 장씩 낱개로 흩어 놓고 두 장씩 짝지어 순서를 맞춰 붙였다. 두 장 묶음을 다시 네 장 묶음으로, 마지막에 한 줄로 합쳐 가는 과정을 그림으로 그려 두었다.

그림처럼 정렬된 두 묶음을 하나로 합쳐 올라가는 과정이 병합 정렬의 핵심이다.

다음과 같은 배열 A에서 A[0]부터 삽입 연산을 차례대로 적용하여 이진 탐색 트리 T를 생성한 후, T를 전위(preorder) 순회 방법으로 방문한 값들을 배열 B에 B[0]부터 순차적으로 저장한 결과는?

A[] ＝ 40, 20, 30, 10

1. B[] ＝ 10, 20, 30, 40
2. B[] ＝ 10, 30, 20, 40
3. B[] ＝ 40, 20, 10, 30
4. B[] ＝ 40, 30, 20, 10

정답 3번

🔍 보기별 해설

10, 20, 30, 40은 오름차순, 곧 중위 순회의 결과이다. 전위 순회는 루트를 먼저 방문해야 하는데 이 배열은 가장 큰 40이 맨 뒤에 놓여 있어 옳지 않다.
10, 30, 20, 40은 자식을 먼저 방문하고 부모를 나중에 방문하는 후위 순회의 결과이다. 루트 40이 마지막에 온 순서라 전위와 다르므로 옳지 않다.
40이 루트, 20은 40의 왼쪽, 30은 20의 오른쪽, 10은 20의 왼쪽에 놓인다. 루트 40, 왼쪽 서브트리의 20, 그 왼쪽 10, 오른쪽 30 순으로 방문하므로 옳다(정답).
40 다음에 30이 오려면 30이 40의 바로 아래 자식이어야 하지만 30은 20보다 크므로 20의 오른쪽 자식에 놓인다. 삽입한 트리 모양과 순서가 어긋나므로 옳지 않다.

🧮 풀이

甲은 완성된 트리를 왼쪽에서 오른쪽으로 훑으며 값을 적어 내려갔다. 작은 값부터 큰 값까지 줄지어 나오는 이 순서가 중위 순회의 특징이라는 점을 공책 옆에 메모해 두었다.
甲은 왼쪽 서브트리 안에서 10과 30을 먼저 적고 그 부모 20을 적은 뒤 40을 맨 끝에 붙였다. 자식을 다 방문한 다음에야 부모를 적는 후위 순서의 예로 삼아 노트에 옮겼다.
甲은 40, 20, 30, 10을 차례로 넣어 트리를 그렸다. 루트에서 시작해 왼쪽 갈래를 끝까지 내려갔다가 오른쪽으로 돌아 나오는 순서를 화살표로 이어 40, 20, 10, 30이라 적었다.
甲은 40 바로 아래에 30을 붙여 그린 트리를 들여다보다가 손을 멈췄다. 30을 넣을 때 40보다 작아 왼쪽으로 갔다가 20보다 커서 오른쪽에 붙는 순서를 다시 따라가며 그림을 고쳤다.

이진 탐색 트리는 40 아래 20이 왼쪽이고 20 아래 10은 왼쪽, 30은 오른쪽이라 전위 순회는 40, 20, 10, 30이다.

30억 개의 정수를 갖는 배열에서 20개의 정수를 제외한 나머지가 모두 정렬되어 있다면, 이 배열을 가장 빠르게 정렬할 수 있는 알고리즘은?

1. 퀵 정렬
2. 선택 정렬
3. 병합 정렬
4. 삽입 정렬

정답 4번

🔍 보기별 해설

퀵 정렬은 기준을 맨 앞 값으로 잡으면 이미 정렬된 부분에서 나뉨이 한쪽으로 기울어 제곱 시간까지 갈 수 있다. 정렬된 부분을 살리지 못하므로 옳지 않다.
선택 정렬은 배열이 정렬되어 있든 아니든 매번 남은 구간 전체에서 최솟값을 찾는다. 항상 n제곱에 가까운 비교를 하므로 거의 정렬된 배열의 이점을 못 살려 옳지 않다.
병합 정렬은 입력 상태와 상관없이 늘 절반으로 나누고 합치므로 어떤 배열이든 n log n 작업을 한다. 거의 정렬된 배열이라도 더 빨라지지 않으므로 옳지 않다.
삽입 정렬은 이미 자리가 맞는 원소는 한 번 비교하고 넘어가고 어긋난 원소만 뒤로 옮긴다. 20개만 제자리를 벗어난 배열에서 나머지에는 한 번씩만 비교하므로 가장 빨라 옳다(정답).

🧮 풀이

甲은 맨 앞 값을 기준으로 삼는 퀵 정렬에 이미 오름차순인 열 개짜리 배열을 넣어 보았다. 기준이 계속 가장 작은 값이라 한 번에 한 개씩만 떨어져 나가는 나뭇가지를 그리고 단계를 세었다.
甲은 거의 정렬된 배열에 선택 정렬을 돌리며 비교 횟수를 표시했다. 이미 제자리인 값이 많아도 매번 남은 구간 전체를 훑어 최솟값을 찾는 탓에 횟수가 줄지 않는 것을 표로 정리했다.
甲은 정렬된 배열과 뒤섞인 배열을 병합 정렬에 각각 넣고 단계 수를 셌다. 두 경우 모두 반으로 나눴다 합치는 층 수가 똑같이 나오는 것을 보고 두 그림을 겹쳐 그려 견주었다.
甲은 오름차순 명단에 늦게 도착한 세 사람의 이름만 잘못된 자리에 끼워 넣은 목록을 받았다. 삽입 정렬을 적용해 어긋난 이름만 제자리로 옮기고 나머지는 한 번씩만 훑어 끝내는 과정을 지켜보았다.

거의 정렬된 배열에는 어긋난 원소만 옮기면 되는 삽입 정렬이 가장 빠르다.

알고리즘의 시간 복잡도에 대한 설명으로 옳은 것은?

1. 널리 사용되는 것은 최악 시간 복잡도이다.
2. 모든 알고리즘은 최악 시간 복잡도와 평균 시간 복잡도가 다르다.
3. 최악의 경우 실행 시간은 모든 입력에 대한 실행 시간의 하한을 제공한다.
4. 최선의 경우 실행 시간은 모든 입력에 대한 실행 시간의 상한을 제공한다.

정답 1번

🔍 보기별 해설

알고리즘 분석에서는 입력이 얼마나 나빠도 이 시간 안에는 끝난다는 상한을 보장하는 최악 시간 복잡도를 가장 널리 쓴다. 실제로 가장 많이 쓰이는 척도이므로 옳다(정답).
병합 정렬은 최악과 평균이 모두 n log n이듯 두 복잡도가 같은 알고리즘도 얼마든지 있다. 모든 알고리즘이 서로 다르다고 일반화한 것은 반례가 있어 옳지 않다.
최악 입력에서 걸리는 시간은 다른 모든 입력의 시간보다 작지 않은 값이라 실행 시간의 상한이 된다. 하한이라고 말한 것은 방향이 거꾸로이므로 옳지 않다.
최선의 경우는 가장 유리한 입력에서 걸리는 시간이라 어떤 입력도 이보다 빨리 끝날 수 없다는 하한을 준다. 상한이라고 말한 것은 거꾸로이므로 옳지 않다.

🧮 풀이

甲은 택배 배송 앱의 예상 도착 시각이 가장 막히는 날을 기준으로 표시되는 것을 보았다. 이 날짜까지는 반드시 도착한다는 보장이 되어 이용자가 계획을 세울 수 있다는 설명을 메모했다.
甲은 병합 정렬을 정렬된 배열, 역순 배열, 무작위 배열에 각각 돌려 보았다. 세 경우 모두 거의 같은 층 수와 비교 횟수가 나오는 것을 표로 만들고 최악과 평균이 같음을 적어 두었다.
甲은 순차 탐색으로 100개 중 하나를 찾는 실험을 했다. 찾는 값이 맨 끝에 있을 때 백 번 비교가 나오고 다른 위치의 값은 그보다 적어 최악이 위쪽 경계임을 그래프에 선으로 그었다.
甲은 찾는 값이 맨 앞에 있는 가장 운 좋은 경우의 비교 횟수 한 번을 적었다. 어떤 값을 찾든 최소한 이 한 번은 필요하다는 아래쪽 경계임을 그래프에 점선으로 표시했다.

최악 시간 복잡도는 실행 시간의 상한이라 가장 널리 쓰이고, 최선은 하한이다.

다항적 시간 복잡도를 갖는 탐욕(greedy) 알고리즘으로 최적의 해를 구할 수 없는 것은?

1. 부분 배낭(fractional knapsack) 문제
2. 한 정점에서 다른 정점으로의 최단 경로 탐색 문제
3. 이진 트리의 최대합 경로 찾기 문제
4. 최소 신장 트리(MST, Minimum Spanning Tree) 생성 문제

정답 3번

🔍 보기별 해설

물건을 쪼갤 수 있으면 무게당 가치가 큰 것부터 담는 탐욕 전략이 최적해를 보장한다. 정렬 뒤 한 번 훑는 다항 시간에 풀리므로 탐욕으로 풀 수 있는 문제라 맞다.
간선 가중치가 음수가 아닌 그래프에서는 다익스트라 알고리즘이 가장 가까운 정점부터 확정해 가는 탐욕 방식으로 최단 경로를 구한다. 다항 시간에 최적해가 나오므로 맞다.
매 단계에서 더 큰 자식만 따라 내려가면 그 아래에 큰 값이 숨은 다른 가지를 놓친다. 탐욕으로는 최적해가 보장되지 않고 모든 경로를 살피거나 재귀로 풀어야 하므로 옳지 않다(정답).
크루스칼과 프림은 가장 가벼운 간선을 사이클이 생기지 않게 골라 붙이는 탐욕 방식이며 최적의 신장 트리를 보장한다. 다항 시간에 최적해가 나오므로 맞다.

🧮 풀이

甲은 무게 30인 가방에 쌀, 소금, 설탕을 무게당 값이 높은 순서로 담았다. 마지막 자루는 남은 공간만큼만 덜어 담자 가방이 빈틈없이 차고 값이 최대가 되는 것을 표로 계산했다.
甲은 지하철 노선도에서 출발역과 가장 가까운 역부터 하나씩 확정하는 방식으로 소요 시간을 구했다. 확정한 역의 시간이 나중에 바뀌지 않는다는 점을 표 옆에 한 줄로 적어 두었다.
甲은 이진 트리에서 루트부터 매번 더 큰 자식만 골라 내려가 합을 구했다. 다른 쪽 가지 끝에 더 큰 값이 있는 것을 나중에 발견하고 두 경로의 합을 나란히 적어 견주었다.
甲은 마을 여섯 곳을 도로로 잇는 공사비 표에서 가장 싼 도로부터 골랐다. 이미 이어진 마을끼리는 잇지 않고 다섯 개의 도로만 남겨 총비용을 계산한 값을 표 밑에 적었다.

이진 트리의 최대합 경로는 큰 자식만 따라가는 탐욕으로 놓치는 경로가 있어 최적해가 보장되지 않는다.

해시(hash) 함수가 h(k) = k mod 8 이고 키값 (k) 이 15, 11, 5, 13, 22, 21 순서로 저장된 해시 테이블의 결과가 다음과 같은 경우에 사용된 충돌 해결 기법은?

인덱스 0 1 2 3 4 5 6 7 키값 22 21 11 5 13 15

1. 체이닝(chaining)
2. 선형 조사법(linear probing)
3. 분기 한정법(branch and bound)
4. 이차 조사법(quadratic probing)

정답 2번

🔍 보기별 해설

체이닝은 같은 인덱스에 든 키를 연결 리스트로 이어 붙이므로 한 칸에 여러 키가 매달린다. 표에는 한 칸에 키가 하나씩만 있고 13이 인덱스 6에 들어가 있어 옳지 않다.
13은 5번이 찼으므로 6번, 22는 6번과 7번이 차서 0번, 21은 5, 6, 7, 0번이 차서 1번에 들어간다. 한 칸씩 뒤로 가며 빈 곳을 찾은 결과가 표와 정확히 일치하므로 옳다(정답).
분기 한정법은 탐색 공간을 나눠 가며 가망 없는 가지를 잘라 최적해를 찾는 알고리즘 설계 기법이다. 해시 충돌을 해결하는 방법이 아니므로 옳지 않다.
이차 조사법은 충돌 때 1, 4, 9칸처럼 제곱만큼 떨어진 칸을 살핀다. 이 방식이면 22는 6번과 7번이 차 있어 2번으로 가야 하는데 표에서는 0번에 있어 옳지 않다.

🧮 풀이

甲은 같은 인덱스 5에 5와 13과 21이 모두 걸리는 것을 알고 그 자리에 연결 리스트를 그려 세 값을 꼬리처럼 이어 붙였다. 한 칸에 여러 값이 매달린 그림을 배열 칸 하나씩만 쓰는 표와 견주었다.
甲은 21을 넣으며 5번이 찼으니 6번, 7번, 0번을 차례로 살피고 1번의 빈칸에 넣었다. 한 칸씩 뒤로 미루며 빈칸을 찾는 화살표를 표 위에 그려 그 순서를 확인했다.
甲은 여행 경로를 가지 치며 최적안을 찾는 문제에서 비용 상한을 넘는 가지를 잘라 냈다. 이것이 해시 표의 충돌과 무관한 탐색 기법임을 알고 이름 옆에 최적화라고 적어 두었다.
甲은 22를 넣을 때 6번과 7번이 차 있으면 이차 조사법이 몇 번 칸으로 가는지 규칙대로 적어 보았다. 이 규칙이면 2번에 들어가 표의 0번과 달라지는 것을 확인하고 값을 옮겨 그렸다.

표에서 충돌한 키가 한 칸씩 뒤로 밀려 들어갔으므로 선형 조사법이다.

9급 데이터 기출 80문항 · 자동복습과 예상점수까지 무료로 →

함수 f(n) 에 대한 점근 표기법으로 옳지 않은 것은?

f(n) = 7n logn + logn - 20n + 6

1. f(n) = Ω (n^2)
2. f(n) = O (n^2)
3. f(n) = Θ (n logn)
4. f(n) + n^2 = O (n^2)

정답 1번

🔍 보기별 해설

f(n)은 n log n 꼴로 자라므로 n제곱보다 느리게 커진다. 아래 경계로 n제곱을 잡으면 충분히 큰 n에서 f(n)이 그 값을 따라가지 못하므로 옳지 않다(정답).
n log n은 n제곱 이하로 자라므로 n제곱을 위쪽 경계로 잡아도 틀리지 않는다. 느슨하지만 참인 상한을 말한 설명이라 맞다.
가장 빨리 자라는 7n log n이 위와 아래를 함께 결정하고 -20n과 로그 항은 충분히 큰 n에서 영향이 사라진다. 상한과 하한이 모두 n log n이므로 맞다.
n log n에 n제곱을 더하면 지배적인 항이 n제곱이 되어 전체가 n제곱 이하로 자란다. 위쪽 경계가 알맞게 잡혔으므로 맞다.

🧮 풀이

甲은 f(n)과 n제곱의 비를 n이 커질 때 계산해 보았다. 값이 점점 0에 가까워져 n제곱의 상수배 이상으로 커질 수 없음을 알고 아래 경계 표기에 붙어 있던 물음표를 지웠다.
甲은 n이 1000일 때 f(n)이 약 5만이고 n제곱이 100만인 것을 표에 적었다. 언제나 n제곱 아래에 머무는 이 관계를 확인하고 상한 표기 옆에 참이라고 표시했다.
甲은 f(n)에서 항을 하나씩 지워 보았다. -20n과 log n은 n이 커질수록 7n log n에 견줘 미미해져 남은 항의 꼴로 정리했고 그 꼴을 Θ 표기 옆에 적었다.
甲은 n log n에 n제곱을 더한 식을 두 항의 크기로 견주어 보았다. n이 커질수록 n제곱이 대부분을 차지하는 것을 그래프로 그려 확인하고 합의 위쪽 경계에 밑줄을 그었다.

f(n)은 n log n 꼴이라 Ω(n²) 아래 경계는 성립하지 않는다.

다음 문자열에 대하여 허프만 코딩(Huffman coding) 알고리즘으로 생성한 허프만 트리에서 루트(root) 노드부터 가장 깊은 단말(leaf) 노드까지 도달하기 위한 단순 경로상의 간선(edge) 개수는?

AAAEEBCCDDDDCCEEEAADDEEEBB

1. 3
2. 4
3. 5
4. 6

정답 1번

🔍 보기별 해설

빈도가 가장 낮은 B(3)와 C(4)를 합쳐 7, 이어 A(5)와 D(6)를 합쳐 11, 다음 7과 E(8)를 합쳐 15, 마지막에 11과 15를 합친다. B와 C가 루트에서 세 칸 아래 가장 깊은 곳에 놓이므로 옳다(정답).
4가 되려면 가장 깊은 잎이 루트에서 네 칸 아래여야 한다. 빈도가 8, 6, 5, 4, 3인 다섯 글자를 병합하면 가장 깊은 잎이 세 칸에서 멈추므로 옳지 않다.
다섯 글자라면 한쪽으로만 계속 치우친 나무일 때 깊이가 최대 네 칸이다. 5는 그 한계를 넘고 이 빈도에서는 균형 있게 합쳐지므로 옳지 않다.
글자 종류가 다섯 가지이므로 잎이 다섯 개인 트리에서 간선이 여섯 개 이어진 경로는 나올 수 없다. 이 문자열에서는 세 칸이 가장 깊으므로 옳지 않다.

🧮 풀이

甲은 A가 5회, B가 3회, C가 4회, D가 6회, E가 8회 나오는 것을 세어 표에 적었다. 작은 둘씩 합치며 나무를 그리자 B와 C 잎이 루트에서 간선 세 개 아래에 놓여 그 길에 색연필로 3이라 표시했다.
甲은 잎 다섯 개짜리 나무를 한쪽으로 기울여 그려 깊이를 세어 보았다. 가장 깊은 잎이 간선 네 개 아래라 4가 되려면 이 정도 기울기가 필요함을 알고 이 문자열의 빈도로는 어렵다고 적었다.
甲은 잎이 다섯 개인 나무에서 가장 길게 뻗을 수 있는 경로를 세어 보았다. 아무리 치우쳐도 간선이 네 개를 넘지 못하는 것을 그림으로 그려 보고 5라는 선택지 옆에 가위표를 쳤다.
甲은 간선이 여섯 개인 경로가 나오려면 잎이 최소 일곱 개는 있어야 한다는 것을 그림으로 그려 보았다. 이 문제는 글자가 다섯 종류뿐이라는 점에 동그라미를 치고 선택지를 지웠다.

빈도 3, 4, 5, 6, 8을 작은 것부터 합치면 가장 깊은 잎 B, C가 루트에서 간선 3개 떨어진다.

그래프(graph) 구조로 데이터를 저장하고 그래프 알고리즘을 이용하여 문제를 해결하는 대표적인 예만을 모두 고르면?

ㄱ. 소셜 네트워크에서 친구 추천하기

ㄴ. 가장 적은 수의 동전으로 거스름돈 돌려받기

ㄷ. 최소 비용의 여행 경로 탐색하기

ㄹ. 정렬된 1차원 배열 구조에서 특정값 빠르게 찾기

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

정답 1번

🔍 보기별 해설

친구 관계는 사람을 점, 친구 사이를 선으로 잇는 그래프이고, 여행 경로의 최소 비용은 도시와 도로의 그래프에서 최단 경로를 구하는 문제이다. 두 가지를 묶은 이 묶음이 맞다.
정렬된 배열에서 값을 빠르게 찾는 것은 이진 탐색으로 풀며 배열 구조를 쓴다. 그래프 문제가 아닌 ㄹ이 섞여 있으므로 옳지 않다.
동전 거스름돈은 큰 동전부터 고르는 탐욕이나 동적 계획법으로 풀며 점과 선의 구조가 필요하지 않다. 그래프 문제가 아닌 ㄴ이 섞여 있으므로 옳지 않다.
동전 거스름돈과 정렬 배열의 탐색은 모두 그래프 구조 없이 탐욕이나 이진 탐색으로 푼다. 그래프 문제인 것이 하나도 들어 있지 않은 묶음이므로 옳지 않다.

🧮 풀이

甲은 친구 추천 앱이 내 친구의 친구를 찾는 방식을 살폈다. 사람을 점으로 친구 관계를 선으로 이은 그림에서 두 칸 떨어진 점을 추천 후보로 뽑고, 여행 경로도 도시를 점으로 이어 같은 방식으로 다뤄 보았다.
甲은 정렬된 학생 번호표 배열에서 가운데를 열어 보며 원하는 번호를 찾았다. 도시나 관계 같은 연결이 필요 없고 배열 위치만 쓰는 방식이라 친구 추천과는 다른 구조임을 옆에 적었다.
甲은 거스름돈 1,260원을 500원, 100원, 50원, 10원 순서로 큰 동전부터 골라 냈다. 동전 개수를 줄이는 이 방식이 지도의 도로망과는 상관없이 계산으로만 풀림을 확인해 계산식 밑에 줄을 쳤다.
甲은 동전 거스름돈과 정렬된 배열의 탐색을 한 표에 나란히 놓았다. 두 문제에서 점과 선으로 이은 그림이 한 번도 나오지 않는 것을 확인하고 그래프 칸을 통째로 비워 두었다.

친구 추천과 최소 비용 경로는 그래프 문제이고 동전 거스름돈과 정렬 배열 탐색은 그렇지 않다. 정답은 1번.

다음 C 프로그램의 실행 결과는?

#include <stdio.h> int count = 0; int A[] = {1, 3, 5, 8, 12, 15, 20, 24, 30, 44, 52, 61, 64, 70, 81, 90}; int bin(int low, int high, int key) { int mid; count++; if (low > high) return 0; else { mid = (low + high) / 2; if (key == A[mid]) return 1; else if (key < A[mid]) return bin(low, mid - 1, key); else return bin(mid + 1, high, key); } } int main() { bin(0, 15, 22); printf("count: %d, ", count); bin(0, 15, 52); printf("count: %d\n", count); return 0; }

1. count: 4, count: 8
2. count: 4, count: 9
3. count: 5, count: 9
4. count: 5, count: 10

정답 3번

🔍 보기별 해설

22를 찾는 첫 호출에서 mid가 7, 3, 5, 6 순으로 바뀐 뒤 low가 high를 넘는 다섯 번째 호출까지 count가 오른다. 4로 끝난다고 본 셈이므로 옳지 않다.
count는 전역 변수라 첫 호출의 5가 이어져 두 번째 호출 뒤 9가 되는 것은 맞다. 하지만 첫 출력이 4가 아니라 5여서 앞자리가 어긋나므로 옳지 않다.
22는 배열에 없어 mid 7, 3, 5, 6을 거쳐 low가 high를 넘는 다섯 번째 호출에서 끝나 5가 출력된다. 이어 52는 mid 7, 11, 9, 10에서 찾아 5에 4가 더해진 9가 되므로 옳다(정답).
첫 출력 5는 맞지만 52를 찾는 호출은 네 번으로 끝나 count가 5에서 9로만 늘어난다. 10까지 세는 것은 한 번 더 세는 오류이므로 옳지 않다.

🧮 풀이

甲은 22를 찾는 재귀 호출을 종이에 한 줄씩 적어 내려갔다. mid가 7, 3, 5, 6인 네 번의 호출까지만 세고 멈춘 표를 보고 low가 high를 넘는 마지막 호출이 빠진 것을 찾아 한 줄을 보태 적었다.
甲은 첫 출력을 4로 적어 두고 두 번째는 전역 변수라 이어서 센다며 9로 적었다. 첫 호출을 다시 따라가 보니 마지막 low>high 호출이 한 번 더 있어 첫 값을 고치는 과정을 표에 표시했다.
甲은 두 검색 호출의 횟수를 나눠 5회와 4회로 적고 합쳐 9라는 값을 얻었다. 화면 출력은 합계가 아니라 누적값이라는 점을 코드에서 확인하고 두 값을 나란히 적어 두었다.
甲은 52를 찾는 호출에서 mid가 7, 11, 9, 10으로 이동하는 것을 그렸다. 네 번째 호출인 mid 10에서 값이 일치해 재귀가 끝나 다섯 번째 호출이 없다는 점에 표시하고 10 대신 9를 적었다.

22는 다섯 번, 52는 네 번 호출하고 count는 누적되므로 출력은 count: 5, count: 9이다.

다음 그래프에서 크루스칼(Kruskal) 알고리즘으로 최소 신장 트리(MST)를 생성할 때 다섯 번째로 추가되는 간선은? (단, 초기 MST는 공집합이다)

1. (b, f)
2. (c, d)
3. (d, e)
4. (d, g)

정답 1번

🔍 보기별 해설

가중치 순으로 (a,b) 2, (a,c) 3, (c,e) 5, (d,e) 6을 잇고 (b,c) 3과 (c,d) 8은 사이클이 생겨 건너뛴다. 그다음 가벼운 (b,f) 9가 다섯 번째로 추가되므로 옳다(정답).
(c,d)는 가중치 8인데 그 앞에 c와 e, e와 d가 이미 이어져 있어 c와 d가 한 덩어리다. 넣으면 사이클이 생기므로 아예 추가되지 않아 옳지 않다.
(d,e)는 가중치 6으로 네 번째로 추가되는 간선이다. 다섯 번째 자리가 아니라 그 바로 앞 순서에 들어가는 간선이므로 옳지 않다.
(d,g)는 가중치 10으로 (b,f) 9보다 나중에 검토된다. 다섯 번째가 아니라 여섯 번째로 추가되므로 옳지 않다.

🧮 풀이

甲은 간선을 무게 순으로 나열해 하나씩 지워 가며 표에 O, X를 적었다. (b,c)와 (c,d)에 X가 붙은 뒤 (b,f)에 다섯 번째 O가 붙는 과정을 색을 달리해 표시했다.
甲은 c와 d를 잇는 간선을 검토하다 이미 c-e-d로 이어진 길이 있음을 발견했다. 새 간선을 넣으면 순환이 생기는 것을 그림으로 그려 보고 후보 표에서 이 간선을 지웠다.
甲은 (d,e)가 가중치 6으로 (c,e) 다음에 들어가는 것을 순서표에 적었다. 표의 네 번째 칸에 이 간선을 채워 넣고 다섯 번째 칸은 비워 둔 채 다음 후보를 찾았다.
甲은 가중치 10인 (d,g)와 (f,g)가 같은 무게로 겹쳐 있는 것을 표에서 보았다. 둘 다 (b,f) 9보다 무거워 다섯 번째 뒤에 온다는 점을 확인하고 표 오른쪽 끝으로 옮겨 적었다.

가중치 순 검토에서 사이클을 만드는 (b,c)와 (c,d)는 건너뛰고 (b,f)가 다섯 번째로 붙는다.

다음 최대 힙(max heap)에 노드 25가 추가될 경우, 최대 힙 성질을 만족하도록 삽입 연산이 완료된 후의 구조로 옳은 것은?

정답 1번

🔍 보기별 해설

25는 마지막 자리인 2의 아래 왼쪽에 붙은 뒤 부모 2보다 커서 자리를 바꾸고, 다시 부모 20보다 커서 루트까지 올라간다. 결과가 25, 15, 20, 14, 10, 2 꼴이라 옳다(정답).
25가 20의 오른쪽 자식이 되어 루트 20보다 큰 값이 아래에 놓인다. 부모가 자식보다 커야 하는 최대 힙 성질이 깨졌으므로 옳지 않다.
25를 삽입한 자리 그대로 두어 부모 2와 루트 20보다 큰 값이 맨 아래에 있다. 위로 올리는 과정을 하지 않은 그림이라 옳지 않다.
루트는 25가 되었지만 오른쪽 가지에서 부모 2 아래에 그보다 큰 20이 놓여 있다. 최대 힙 성질을 어긴 구조이므로 옳지 않다.

🧮 풀이

甲은 새 노드 25를 마지막 자리에 붙인 뒤 부모와 값을 견주며 위로 옮겼다. 2와 20을 차례로 넘겨 루트에 앉히고 완성한 트리를 층별로 읽어 25, 15, 20, 14, 10, 2로 적었다.
甲은 25를 20의 오른쪽에 그리고 20을 루트에 남겨 둔 그림을 보았다. 루트보다 큰 값이 자식이라 힙의 규칙에서 벗어난다는 점에 빨간 펜으로 굵은 화살표를 그어 두었다.
甲은 새 값 25를 맨 아래 빈자리에 넣고 부모와 비교하지 않은 채 그림을 그렸다. 부모 2보다 큰 값이 아래에 남은 것을 보고 비교와 교환 단계를 빠뜨린 자리를 짚어 표시했다.
甲은 25가 부모 2를 건너뛰고 루트 20과 곧바로 자리를 바꾸는 경우를 그려 보았다. 오른쪽 가지에서 2 밑에 20이 놓여 부모가 자식보다 작아지는 것을 보고 그림 옆에 별표를 달았다.

25를 마지막 자리에 붙인 뒤 부모 2, 루트 20과 차례로 교환해 25가 루트가 된다.

백트래킹(backtracking)에 대한 설명으로 옳지 않은 것은?

1. 스택(stack)을 이용하여 구현할 수 있다.
2. 재귀적(recursive)으로 구현할 수 있다.
3. 제약 충족(constraint satisfaction) 문제에 유용하다.
4. 균형 탐색 트리(balanced search tree) 구조를 유지한다.

정답 4번

🔍 보기별 해설

되돌아갈 위치를 스택에 쌓아 두었다가 막다른 길에서 꺼내 쓰면 백트래킹을 반복문으로 구현할 수 있다. 구현 방법을 바르게 말한 설명이라 맞다.
함수가 자기 자신을 호출해 한 단계씩 들어가고 막히면 호출이 끝나 이전 단계로 돌아오므로 재귀가 자연스럽다. 구현 방법을 바르게 말한 설명이라 맞다.
N-Queen이나 스도쿠처럼 조건을 만족하는 해를 찾는 문제는 조건을 어기는 순간 그 가지를 버리고 되돌아가는 백트래킹이 잘 맞는다. 적용 분야를 바르게 말한 설명이라 맞다.
백트래킹은 해 후보를 나열한 상태 공간 트리를 깊이 우선으로 탐색하다 가망 없는 가지를 자르는 방법이다. 균형을 유지하도록 트리를 스스로 재구성하는 성질이 없으므로 옳지 않다(정답).

🧮 풀이

甲은 미로에서 갈림길마다 지나온 칸을 상자에 차례로 쌓아 두었다. 막다른 길에 닿자 맨 위 칸을 꺼내 그 갈림길로 돌아가서 아직 안 가 본 다른 길을 찾는 방식으로 출구까지 나아갔다.
甲은 순열을 만드는 함수가 다음 자리를 채우려고 자기 자신을 다시 부르는 코드를 짰다. 자리를 채울 수 없으면 호출이 끝나 앞 단계로 돌아오는 흐름을 출력 로그로 확인했다.
甲은 8-퀸 문제에서 다음 행에 퀸을 놓을 칸이 없으면 앞 행으로 돌아가 위치를 옮겼다. 조건을 어기는 자리를 만나는 즉시 그 가지를 잘라 낸 횟수를 세어 표의 마지막 칸에 적었다.
甲은 후보 해를 나열한 나무를 그리며 자라나는 모양을 살폈다. 노드를 넣을 때마다 나무를 다시 균형 잡는 회전은 하나도 나오지 않아 백트래킹이 균형 트리를 만드는 방법이 아님을 적었다.

백트래킹은 스택이나 재귀로 구현하고 제약 문제에 쓰며 균형 트리를 유지하지 않는다.

문자열 매칭을 위한 알고리즘으로 옳지 않은 것은?

1. 라빈－카프(Rabin-Karp)
2. 벨만－포드(Bellman-Ford)
3. 보이어－무어(Boyer-Moore)
4. KMP(Knuth-Morris-Pratt)

정답 2번

🔍 보기별 해설

라빈-카프는 패턴의 해시값을 계산해 텍스트의 같은 길이 부분 문자열의 해시값과 비교한다. 문자열 매칭 알고리즘의 하나이므로 맞다.
벨만-포드는 간선 가중치가 음수여도 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 그래프 알고리즘이다. 문자열을 찾는 용도가 아니므로 옳지 않다(정답).
보이어-무어는 패턴의 뒤쪽부터 비교하고 불일치 문자 표와 일치 접미부 표로 건너뛰며 텍스트를 훑는다. 문자열 매칭 알고리즘의 하나이므로 맞다.
KMP는 패턴 안에서 접두사와 접미사가 겹치는 길이를 미리 구해 두고 불일치 때 텍스트 위치를 되돌리지 않는다. 문자열 매칭 알고리즘의 하나이므로 맞다.

🧮 풀이

甲은 긴 글에서 짧은 단어를 찾기 위해 글의 각 부분마다 해시값을 계산해 단어의 해시값과 비교했다. 값이 같은 곳만 글자를 하나씩 대조하는 방식으로 후보를 크게 줄여 나갔다.
甲은 환승 할인으로 일부 구간 값이 음수가 된 노선도를 받았다. 출발 도시에서 각 도시까지 거리를 간선 전체를 여러 번 훑으며 갱신해 구하고 문자열은 한 번도 나오지 않음을 메모했다.
甲은 패턴 끝 글자부터 텍스트와 맞춰 보다가 어긋난 글자가 패턴에 없으면 패턴을 통째로 뒤로 옮겼다. 텍스트를 건너뛰는 폭이 큰 예를 이동 표로 만들어 옆에 붙여 두었다.
甲은 패턴 abab의 접두사와 접미사가 겹치는 길이를 표로 만들어 두었다. 어긋났을 때 텍스트 위치는 그대로 두고 패턴만 표의 값만큼 옮기는 방식으로 비교 횟수를 줄여 나갔다.

벨만-포드는 최단 경로 알고리즘이지 문자열 매칭 알고리즘이 아니다.

다음 그래프에서 A부터 깊이 우선 탐색(depth first search)을 수행하는 경우, 가능한 정점의 방문 순서로 옳지 않은 것은?

1. A → B → D → E → C → F → G → H
2. A → C → F → H → G → E → D → B
3. A → C → G → H → F → D → E → B
4. A → D → B → E → C → G → H → F

정답 2번

🔍 보기별 해설

A에서 B, D를 거쳐 E까지 갔다가 막히면 D로 돌아와 C, F, G, H로 이어지는 경로이다. 각 이동이 간선을 따르고 되돌아오는 위치도 알맞아 가능한 순서이므로 맞다.
G까지 간 뒤에는 이웃이 모두 방문된 상태라 되돌아가야 한다. G는 E와 간선이 없고 F에 아직 방문하지 않은 D가 남아 있어 E로 곧바로 갈 수 없으므로 옳지 않다(정답).
A에서 C, G, H, F까지 내려간 뒤 F에서 D로 가고 D의 이웃인 E를 방문한 다음 되돌아와 B에 도착한다. 매 단계가 간선으로 이어져 있어 가능한 순서이므로 맞다.
A, D, B까지 내려간 뒤 D에서 E를 방문하고 다시 D로 돌아와 C, G, H, F를 잇는다. D가 아직 방문하지 않은 이웃을 차례로 가는 순서라 가능한 방문이므로 맞다.

🧮 풀이

甲은 A에서 B, D, E까지 따라간 뒤 E가 막다른 정점이라 D로 돌아왔다. D에 남은 이웃 C와 그 뒤의 F, G, H를 이어 가며 되돌아오는 자리를 화살표 표로 기록했다.
甲은 G에 닿은 뒤 다음 정점으로 E를 적으려다 G와 E 사이에 선이 없음을 발견했다. F에 아직 D가 남아 있어 그 순서대로 가야 한다는 것을 알고 경로표에서 E를 지웠다.
甲은 C에서 G, H를 지나 F에 온 다음 D를 방문하는 순서를 그림 위에 손가락으로 따라가 보았다. D의 이웃 E를 본 뒤 B로 돌아오는 갈림길까지 순서를 정리해 답안에 적었다.
甲은 D를 먼저 골라 B를 방문한 경로를 그렸다. D로 되돌아와 E를 거쳐 C, G, H, F로 이어지는 순서가 각 단계마다 이웃이라는 점을 확인해 정점 옆에 번호를 달았다.

DFS는 막히면 방문하지 않은 이웃이 남은 가장 가까운 정점으로 돌아가야 하므로 G 다음에 E는 올 수 없다.

다음 함수는 0보다 큰 자연수 n이 입력될 때, 1 2 3 4 … n 순서로 출력하는 재귀 함수이다. (가) ～ (다)에 들어갈 내용을 바르게 연결한 것은?

void fun(int n) if ( (가) ) (나) (다) (가) (나) (다)

1. n > 0 printf("%d ", n); fun(n-1);
2. n > 0 fun(n-1); printf("%d ", n);
3. n > 1 printf("%d ", n); fun(n-1);
4. n > 1 fun(n-1); printf("%d ", n);

정답 4번

🔍 보기별 해설

조건이 n>0이고 출력만 조건 안에 두면 재귀 호출이 조건 밖에서 매번 실행된다. n이 0 이하가 되어도 호출이 계속되어 끝나지 않으므로 옳지 않다.
n>0이면 fun(n-1)만 조건 안에서 부르고 출력은 조건 밖에 있어 n이 0일 때도 0을 찍는다. 결과가 0 1 2로 시작해 1부터 출력하는 요구와 어긋나므로 옳지 않다.
출력이 조건 안에, 재귀 호출이 조건 밖에 있어 n이 1일 때도 호출이 이어진다. 종료 조건이 재귀 호출을 막지 못하므로 옳지 않다.
n이 1보다 클 때만 fun(n-1)을 부르고 그 아래 출력은 언제나 실행한다. 가장 깊은 호출인 fun(1)이 1을 먼저 찍고 돌아오며 2, 3, 그리고 n까지 찍으므로 옳다(정답).

🧮 풀이

甲은 조건 밖에 재귀 호출이 있는 함수를 종이로 따라가 보았다. fun(1) 다음에 fun(0), fun(-1)로 끝없이 이어지는 것을 보고 호출 사슬 끝에 무한이라고 적었다.
甲은 n이 3일 때 손코딩을 해 출력을 차례로 적었다. fun(1)이 fun(0)을 부른 뒤 0을 찍어 결과 맨 앞에 0이 붙는 것을 보고 조건에 든 숫자에 밑줄을 그었다.
甲은 n이 1인 경우만 골라 코드를 손으로 돌렸다. 조건이 거짓이어도 아래 재귀 호출이 그대로 실행되어 fun(0)으로 넘어가는 것을 발견하고 호출 순서를 번호로 매겨 두었다.
甲은 fun(3)이 fun(2)를, fun(2)가 fun(1)을 부르는 나무를 그렸다. 가장 깊은 곳부터 1, 2, 3이 거슬러 올라오며 출력되는 순서를 화살표로 표시했다.

if는 (나) 한 문장만 다스리고 (다)는 조건 밖이다. n>1일 때 fun(n-1)을 먼저 부르고 출력해야 1부터 n까지 나온다.

9급 데이터 기출 80문항 · 자동복습과 예상점수까지 무료로 →

다음은 1 이상인 x에 대해 1부터 x까지의 합을 계산하는 C 함수이다. (가)에 들어갈 코드는?

int sum(int x) {

if (x <= 1) return 1;

return x + (가) ;

}

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

정답 4번

🔍 보기별 해설

x+1은 재귀 호출이 아니라 수 하나를 더하는 식이라 1부터 x까지의 합을 이어 붙이지 못한다. 반환값이 x+x+1 꼴로 끝나 합의 정의와 어긋나므로 옳지 않다.
x-1은 함수 호출 없이 x 바로 아래 수를 더할 뿐이라 그 아래의 합이 이어지지 않는다. x가 커질수록 2x-1만 반환해 합계가 나오지 않으므로 옳지 않다.
sum(x+1)은 인자가 점점 커져서 x가 1 이하인 종료 조건에 영원히 닿지 못한다. 재귀가 끝나지 않고 스택이 넘치게 되므로 옳지 않다.
x에 x-1까지의 합을 더하는 재귀 식이다. 인자가 1씩 줄어 x가 1 이하가 되는 종료 조건에서 1을 돌려주고 차례로 더해 올라오므로 옳다(정답).

🧮 풀이

甲은 x가 4일 때 x + (x+1)을 계산해 보았다. 차근차근 4에 5를 더해 9가 나올 뿐 1부터 4까지의 합 10과 다르다는 점을 확인하고 식 옆에 다른 값이라고 적어 두었다.
甲은 x가 4일 때 x + (x-1)의 값을 손으로 계산해 7을 얻었다. 호출이 없어서 3 이하는 더해지지 않는다는 것을 알고 1부터 합 10과 나란히 적어 차이를 표시했다.
甲은 sum(x+1)로 바꾼 코드를 x가 3일 때 실행하는 상황을 그렸다. 호출 인자가 4, 5, 6으로 계속 커지고 종료 조건이 한 번도 참이 되지 않는 흐름을 화살표로 이어 그렸다.
甲은 sum(4)가 4+sum(3), sum(3)이 3+sum(2)로 이어지는 호출 나무를 그렸다. 맨 아래 sum(1)이 1을 돌려주고 위로 거슬러 올라오며 2, 3, 4가 더해지는 순서를 표시했다.

sum(x)는 x에 sum(x-1)을 더하고 x가 1 이하이면 1을 돌려주어야 1부터 x까지의 합이 된다.

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

○ 문자열 매칭 알고리즘이다.

○ 주어진 패턴과 텍스트에서 사용된 알파벳을 이용해 불일치 문자(bad character) 이동표를 만든다.

○ 패턴을 이용해서 일치 접미부(good suffix) 이동표를 만든다.

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

정답 3번

🔍 보기별 해설

다익스트라는 가중치가 있는 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. 문자열 매칭도 아니고 이동표도 쓰지 않으므로 옳지 않다.
라빈-카프는 패턴의 해시값과 텍스트 부분 문자열의 해시값을 견주는 문자열 매칭이다. 불일치 문자표와 일치 접미부표가 아니라 해시를 쓰므로 옳지 않다.
패턴의 뒤에서부터 비교해 어긋나면 불일치 문자 표와 일치 접미부 표로 얼마나 옮길지 정한다. 두 이동표를 모두 만드는 문자열 매칭이므로 옳다(정답).
플로이드-워셜은 모든 정점 쌍 사이의 최단 거리를 동적 계획법으로 구하는 그래프 알고리즘이다. 문자열을 다루지 않으므로 옳지 않다.

🧮 풀이

甲은 도시 사이의 도로망에서 출발 도시로부터 가장 가까운 도시를 차례로 확정해 갔다. 문자열이 나오지 않고 도로 길이만 쓰는 이 표를 보며 문자열 검색과는 다른 문제임을 옆에 적어 두었다.
甲은 패턴 문자열 하나와 텍스트의 각 구간에 같은 계산식을 적용해 나온 숫자를 비교했다. 숫자가 같을 때만 글자를 맞춰 보는 방식이 이동표 없이 해시만 쓰는 것을 알고 메모했다.
甲은 패턴 끝 글자부터 텍스트와 맞춰 보다가 어긋나는 글자가 패턴에 없으면 패턴을 크게 옮겼다. 그때 참고한 두 가지 이동표를 종이 한 장에 나란히 만들어 책상 앞에 붙여 두었다.
甲은 정점 다섯 개의 모든 쌍 사이 거리를 3중 반복문으로 갱신하는 표를 만들었다. 우선 문자열 대신 인접 행렬만 쓰는 이 표를 보고 글자 비교 문제가 아님을 옆에 적어 넣었다.

불일치 문자 이동표와 일치 접미부 이동표를 모두 쓰는 문자열 매칭은 보이어-무어다.

분할 정복(divide and conquer) 방식의 정렬 알고리즘만을 모두 고르면?

ㄱ. 버블 정렬(bubble sort)

ㄴ. 병합 정렬(merge sort)

ㄷ. 퀵 정렬(quick sort)

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

정답 4번

🔍 보기별 해설

병합 정렬은 분할 정복이지만 퀵 정렬도 배열을 기준값으로 나누어 각각 정렬하는 분할 정복 방식이다. 퀵 정렬이 빠져 있어 모두 고른 것에 못 미치므로 옳지 않다.
버블 정렬은 이웃한 두 값을 견주어 바꿔 가는 방식이라 문제를 나누어 푸는 구조가 아니다. 분할 정복이 아닌 ㄱ이 섞여 있으므로 옳지 않다.
버블 정렬은 이웃한 값끼리 바꾸며 전체를 반복해 훑는 방식이다. 이 묶음은 그것을 넣고 병합 정렬을 빼서 분할 정복 정렬 모음과 어긋나므로 옳지 않다.
병합 정렬은 반으로 나눠 각각 정렬한 뒤 합치고 퀵 정렬은 기준값으로 둘로 나눠 각각 정렬한다. 둘 다 분할 정복이고 버블 정렬은 제외되므로 이 묶음이 맞다.

🧮 풀이

甲은 병합 정렬만 분할 정복이라고 외웠다가 퀵 정렬도 배열을 둘로 갈라 각각 정렬하는 것을 그림으로 확인했다. 갈라진 두 조각에 다시 같은 방법을 적용하는 화살표를 그려 넣었다.
甲은 버블 정렬을 손으로 돌리며 이웃한 두 값을 비교해 바꾸는 단계를 하나하나 세어 보았다. 배열이 반으로 갈라지는 단계가 한 번도 없어 분할 정복 목록에서 그 이름을 지워 냈다.
甲은 정렬 세 가지를 분할 정복인지 아닌지 표에 표시했다. 버블 정렬 칸에 X, 퀵 정렬 칸에 O를 넣고 병합 정렬이 빠진 조합이 어색해 보여 그 옆에 물음표를 하나 그려 넣었다.
甲은 병합 정렬은 반으로 갈라 합치고 퀵 정렬은 기준값으로 나눈다는 차이를 적었다. 둘 다 나눈 조각에 같은 정렬을 되풀이하는 점을 표에 함께 적고 버블 정렬은 표 밖에 두었다.

병합 정렬과 퀵 정렬은 분할 정복이고 버블 정렬은 그렇지 않다. 정답은 4번.

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

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

정답 3번

🔍 보기별 해설

상수는 n에 상관없이 일정해 n log n의 상수배 아래에 든다. 위쪽 경계 안에 포함되는 함수를 말한 설명이라 맞다.
3n log n + 2n + 1에서 가장 빠르게 자라는 항이 n log n이라 이 식은 n log n의 상수배 이하이다. 빅오 집합에 포함되는 함수를 말한 설명이라 맞다.
3n + log n + 2는 n에 비례해 자라므로 n log n보다 느리다. 빅오는 위쪽 경계라 느리게 자라는 함수도 포함하는데 제외한다고 한 서술은 옳지 않다(정답).
n제곱은 n log n보다 훨씬 빨리 자라 어떤 상수배로도 n log n에 묶이지 않는다. 그러므로 이 식은 집합에 포함되지 않는다는 서술이 맞다.

🧮 풀이

甲은 실행 시간이 입력과 상관없이 항상 5ms인 함수를 n log n 곡선 아래에 그려 보았다. 차근차근 언제나 곡선 밑에 머무는 것을 확인하고 표기 집합 안쪽에 점을 찍어 두었다.
甲은 3n log n에 2n과 1이 붙은 식이 n이 백만일 때 실제로 얼마나 커지는지 계산해 보았다. 값의 대부분이 첫 항에서 나오는 것을 보고 나머지 두 항 옆에 취소선을 그었다.
甲은 n에 비례하는 함수와 n log n 곡선을 한 그래프에 겹쳐 그렸다. 직선이 곡선 아래에 있어 상한 기준에 들어가는 것을 보고 이 함수를 집합에서 뺀 서술에 가위표를 쳤다.
甲은 n제곱 함수와 n log n 곡선에 계수를 바꿔 가며 한 그래프에 겹쳐 그렸다. 우선 어떤 상수를 곱해도 n제곱이 위로 벗어나는 것을 보고 이 식을 집합에서 제외해 두었다.

빅오는 위쪽 경계라서 n log n보다 느리게 자라는 3n+log n+2도 O(n log n)에 포함된다.

다음 그래프에서 크루스칼(Kruskal) 알고리즘을 사용하여 만든 최소 비용 신장 트리(minimum cost spanning tree)는?

정답 1번

🔍 보기별 해설

간선을 가중치 순으로 2(E,G), 3(A,B), 4(E,F), 5(B,D)를 넣고 6(A,D)은 사이클이라 건너뛴다. 이어 8(C,F)과 9(D,E)를 넣어 여섯 간선, 합계 31의 트리가 되므로 옳다(정답).
이 그림은 5짜리 (B,D) 대신 6짜리 (A,D)를 넣고 C도 8짜리 (C,F) 대신 10짜리 (C,E)로 잇는다. 더 가벼운 간선이 먼저 선택되는 크루스칼의 결과와 다르므로 옳지 않다.
그림에서는 A와 C를 17짜리 간선으로 잇고 5짜리 (B,D)와 4짜리 (E,F)를 쓰지 않았다. 더 가벼운 간선이 있는데 무거운 간선을 고른 셈이라 옳지 않다.
17짜리와 12짜리 같은 무거운 간선이 들어 있고 가장 가벼운 (E,G) 2와 (E,F) 4가 빠져 있다. 가중치 순으로 고르는 크루스칼 결과가 될 수 없으므로 옳지 않다.

🧮 풀이

甲은 간선 열두 개를 가중치 순으로 늘어놓고 작은 것부터 하나씩 골랐다. 6인 (A,D)는 이미 A, B, D가 이어져 있어 건너뛰고 여섯 개가 되었을 때 멈춘 뒤 합계 31을 적었다.
甲은 (B,D) 5 대신 (A,D) 6이 들어간 트리를 보고 총합을 계산했다. 결과가 31이 아니라 34가 나오는 것을 보고 가장 가벼운 간선을 놓친 선택이라 표 옆에 표시했다.
甲은 A와 C를 이은 17짜리 간선이 들어 있는 트리를 발견했다. 그 간선 없이도 C를 8짜리 (C,F)로 이을 수 있음을 알고 총합이 크게 늘어난 계산을 그림 옆에 적었다.
甲은 12짜리 (B,G)가 들어간 트리를 가중치 순 목록과 대조했다. 우선 그보다 가벼운 2와 4짜리 간선이 하나도 쓰이지 않은 것을 알고 크루스칼 결과가 못 된다고 메모했다.

가중치 2, 3, 4, 5, 8, 9 간선을 차례로 고르고 사이클이 되는 6은 건너뛴다.

충분히 큰 n에 대해서 수행 시간이 가장 많이 걸리는 시간 복잡도는?

1. Θ (2^n)
2. Θ (n^3)
3. Θ (n!)
4. Θ (n logn)

정답 3번

🔍 보기별 해설

2^n은 지수 함수라 n이 커지면 매우 빨리 늘어난다. 그러나 n!은 n이 커질수록 2^n보다도 훨씬 빨리 커지므로 가장 오래 걸리는 것이 될 수 없어 옳지 않다.
n^3은 다항 함수라 n이 커져도 지수나 팩토리얼보다 완만하게 늘어난다. 충분히 큰 n에서는 가장 작은 축에 들어 가장 오래 걸리지 않으므로 옳지 않다.
n!은 n을 곱해 가며 커지므로 충분히 큰 n에서 2^n이나 n^3보다 빨리 자란다. 네 함수 가운데 실행 시간이 가장 길어지므로 옳다(정답).
n log n은 정렬 알고리즘의 효율적인 복잡도로 n^3보다도 느리게 자란다. 네 함수 중 가장 빨리 끝나는 쪽이라 가장 오래 걸리는 것과 거리가 멀어 옳지 않다.

🧮 풀이

甲은 n이 20일 때 2^n이 약 백만이라는 계산을 표에 적었다. 곧이어 같은 n에서 n!이 이보다 수조 배 크다는 것을 나란히 두고 2^n 줄에는 두 번째라고 적어 넣었다.
甲은 n이 100일 때 n^3이 백만 남짓이라는 값을 계산기로 두드려 보았다. 지수와 팩토리얼 곡선에 견주면 바닥에 붙은 선이라 그래프 아래쪽에 이 함수의 이름을 따로 적었다.
甲은 n이 10, 15, 20으로 늘 때 n!이 약 363만, 약 1.3조, 약 240경으로 뛰는 것을 표로 만들었다. 나머지 세 함수의 열이 그 값에 못 미치는 것을 보고 가장 오른쪽 열에 별표를 쳤다.
甲은 데이터 백만 개를 n log n 정렬에 넣으면 약 2천만 번 연산이면 끝난다는 것을 계산했다. 다른 세 함수와 견주면 가장 작은 값이라는 것이 한눈에 보이게 막대그래프를 그렸다.

n!은 지수 함수보다도 빨리 자라므로 충분히 큰 n에서 가장 오래 걸린다.

다음 의사코드에 해당하는 알고리즘 설계기법은?

f[ ]: 모든 값이 0으로 초기화된 정수 배열

fib(n)

{

if (f[n] == 0) {

if (n == 1 or n == 2) f[n] = 1;

else f[n] = fib(n - 1) + fib(n - 2);

}

return f[n];

}

1. 그리디(greedy) 알고리즘
2. 유전자(genetic) 알고리즘
3. 분기 한정(branch and bound) 기법
4. 동적 프로그래밍(dynamic programming)

정답 4번

🔍 보기별 해설

그리디는 매 단계에서 지금 가장 좋아 보이는 선택을 하고 되돌리지 않는다. 제시된 코드는 배열 f에 저장한 값을 다시 쓰는 방식이라 옳지 않다.
유전자 알고리즘은 해 후보 집단을 교차와 변이로 진화시켜 좋은 해를 찾는 기법이다. 배열에 계산 결과를 기록하는 이 코드와는 방식이 다르므로 옳지 않다.
분기 한정은 탐색 트리에서 한계값을 계산해 가망 없는 가지를 잘라 낸다. 이 코드에는 한계값 판단이 없고 저장한 값을 재사용하므로 옳지 않다.
f[n]이 0이 아니면 이미 계산한 값을 그대로 돌려주고 0일 때만 fib(n-1)과 fib(n-2)를 계산해 저장한다. 부분 문제의 결과를 저장해 재사용하는 동적 프로그래밍이므로 옳다(정답).

🧮 풀이

甲은 거스름돈을 줄 때마다 지금 가장 큰 동전을 바로 고르고 다시 바꾸지 않았다. 이 방식에는 이전 계산을 저장해 두는 배열이 없다는 것을 알고 f 배열이 있는 코드와 구분해 적었다.
甲은 후보 해 여러 개를 섞고 일부를 바꿔 가며 다음 세대를 만드는 프로그램을 보았다. 배열에 값을 기록해 다시 쓰는 재귀 코드와는 진행 방식이 다르다는 것을 표에 정리했다.
甲은 상한값을 계산해 가능성이 낮은 가지를 버리는 탐색 트리를 그렸다. 다음으로 코드에 상한을 재는 부분이 없고 배열 값만 확인하는 것을 보고 기법 이름 옆에 가위표를 크게 쳤다.
甲은 fib(5)를 처음 호출하면서 f 배열에 값이 채워지는 순서를 표에 적었다. 두 번째로 fib(3)을 부를 때 계산 없이 저장된 2를 곧바로 돌려주는 줄에 동그라미를 쳤다.

f 배열에 결과를 저장해 다시 쓰는 재귀는 메모이제이션을 쓰는 동적 프로그래밍이다.

다음 그래프의 A 정점부터 너비 우선 탐색(BFS, breadth first search)을 할 때, 가능한 정점의 방문 순서가 아닌 것은?

1. A ⟶ B ⟶ C ⟶ D ⟶ F ⟶ G ⟶ E ⟶ H
2. A ⟶ B ⟶ D ⟶ C ⟶ E ⟶ F ⟶ G ⟶ H
3. A ⟶ C ⟶ B ⟶ D ⟶ F ⟶ G ⟶ E ⟶ H
4. A ⟶ C ⟶ D ⟶ E ⟶ B ⟶ F ⟶ H ⟶ G

정답 4번

🔍 보기별 해설

A에서 B, C, D 순으로 한 칸 이웃을 모두 방문한 뒤 C의 이웃 F, G와 D의 이웃 E 순으로 두 칸 이웃을 방문하고 H로 끝난다. 층을 순서대로 지키는 방문이라 맞다.
A의 이웃을 B, D, C 순으로 방문한 뒤 D가 발견한 E와 F, C가 발견한 G를 이어서 방문하고 H로 마친다. 앞 층을 마치고 다음 층으로 가는 순서라 맞다.
이웃을 C, B, D 순으로 방문하면 C가 먼저 발견한 F, G가 앞서고 D가 발견한 E가 뒤따른다. 마지막 H까지 층 순서가 유지되므로 맞다.
B는 A에서 한 칸 떨어진 정점이라 같은 층의 C, D와 함께 먼저 방문해야 한다. E는 D를 거쳐야 하는 두 칸 거리인데 B보다 앞서 방문되어 층 순서가 깨지므로 옳지 않다(정답).

🧮 풀이

甲은 A에서 시작해 이웃 B, C, D를 차례로 큐에 넣고 꺼냈다. 펜을 다시 집어 들고 큐에서 C를 꺼낼 때 F와 G를, D를 꺼낼 때 E를 새로 큐에 넣는 순서를 칸마다 옮겨 적었다.
甲은 큐에 B, D, C를 넣는 순서를 바꿔 가며 실험했다. 곧이어 D를 먼저 꺼내는 경우 E와 F가 앞에 서고 그 뒤로 C가 데려온 G가 붙는 큐 상태를 그림으로 남겨 두었다.
甲은 A의 이웃을 C, B, D 순으로 큐에 넣어 보았다. 책상 앞에 앉아 C에서 F, G가 먼저 큐에 들어가고 D에서 E가 그 뒤에 붙는 흐름을 손으로 따라가며 칸마다 적어 넣었다.
甲은 D를 꺼낸 직후에 E를 방문하는 순서를 적어 보았다. 펜을 다시 집어 들고 방문 순서에서 B가 E 뒤로 밀려 층 순서가 깨지는 자리를 확인하고 그 부분에 형광펜으로 굵은 줄을 그었다.

BFS는 A에서 가까운 층부터 방문하므로 두 칸 거리의 E가 한 칸 거리의 B보다 먼저 나올 수 없다.

다음 방향 그래프에 벨만－포드(Bellman-Ford) 알고리즘을 적용한 후, 각 정점과의 최단 거리 값을 바르게 연결한 것은? (단, 시작 정점은 A 정점이다)

A B C D E F G

1. 0 1 1 5 －1 －1 3
2. 0 1 3 5 0 4 3
3. 0 3 2 2 3 2 6
4. 0 3 5 5 6 4 7

정답 2번

🔍 보기별 해설

C를 1, E를 -1, F를 -1로 잡았지만 C는 D를 거쳐 5-2인 3, F는 D에서 -1을 더한 4가 최단 거리이다. C와 E와 F의 값이 실제보다 작게 적혀 옳지 않다.
D는 5, C는 D의 -2를 거쳐 3, B는 C의 -2를 거쳐 1, E는 B의 -1을 거쳐 0, F는 D의 -1을 거쳐 4, G는 E 경유 3이다. 간선을 반복해 완화하면 모든 값이 이와 같으므로 옳다(정답).
B를 3, C를 2, D를 2로 적었지만 A에서 D로 가는 간선은 5뿐이라 D가 2가 될 수 없다. 여러 정점이 실제 간선 값과 맞지 않아 옳지 않다.
C를 A에서 곧장 오는 5로만 잡고 D를 거쳐 음의 간선 -2를 타는 길을 놓쳤다. 이 때문에 B, E, G까지 모두 실제 최단 거리보다 크게 나와 옳지 않다.

🧮 풀이

甲은 E를 -1, F를 -1이라고 표에 적었다. 곧이어 그러나 D를 거친 F는 4, B를 거친 E는 0이 나오는 것을 다시 계산해 보고 그 두 칸의 값을 지우고 고쳐 적었다.
甲은 벨만-포드를 여섯 라운드에 걸쳐 모든 간선을 훑으며 표를 채워 갔다. 마지막 라운드에서 바뀌는 값이 없는 것을 보고 0, 1, 3, 5, 0, 4, 3을 답으로 적었다.
甲은 D의 거리를 2로 적고 A에서 D까지의 간선이 몇인지 그림에서 다시 보았다. 다음으로 5짜리 간선 하나뿐인 것을 알고 D의 값을 고치기 위해 그 칸의 숫자를 지우개로 지웠다.
甲은 C를 A에서 곧바로 가는 5로만 두었다가 D에서 C로 오는 간선이 -2인 것을 발견했다. 우선 그 길이 5-2인 3으로 더 짧은 것을 확인하고 화살표를 색연필로 덧그렸다.

벨만-포드로 구한 A로부터의 최단 거리는 B 1, C 3, D 5, E 0, F 4, G 3이다.

다음 방향 그래프에서 2개 이상의 정점이 포함되어 있는 강한 연결 요소(strongly connected component)의 개수는?

1. 1
2. 2
3. 3
4. 4

정답 2번

🔍 보기별 해설

A, E, B가 도는 고리와 D, G, H가 도는 고리는 서로 되돌아올 길이 없어 다른 요소이다. 요소가 하나라고 할 수는 없으므로 옳지 않다.
A에서 E, E에서 B, B에서 A로 돌아오는 고리와 D에서 G, G에서 H, H에서 D로 돌아오는 고리가 각각 하나의 강한 연결 요소이다. C와 F는 혼자라 세지 않으므로 옳다(정답).
정점 하나짜리 C와 F를 요소로 세면 네 개가 되지만 문제는 두 정점 이상만 묻는다. 세 개가 되는 경우는 없으므로 옳지 않다.
네 개는 A, E, B와 D, G, H 두 묶음에 정점 하나짜리 C와 F를 더한 전체 요소의 수이다. 두 정점 이상만 세면 그중 둘뿐이므로 옳지 않다.

🧮 풀이

甲은 방향 그래프 전체를 한 덩어리로 묶으려 했다. 다음으로 E에서 F를 거쳐 C, D로 가는 길은 있어도 돌아오는 길이 없어 두 덩어리로 나눠 다시 그리고 색을 달리 칠했다.
甲은 A에서 출발해 E, B를 거쳐 다시 A로 돌아오는 길을 색연필로 이었다. 다음으로 D, G, H도 같은 방식으로 이어 두 개의 닫힌 고리를 각각 다른 색으로 칠해 표시했다.
甲은 C 하나만 요소로 더 세어 세 개로 적었다가 C와 F가 서로 돌아올 길이 없어 홀로 남는다는 것을 발견했다. 우선 문제 조건인 두 정점 이상에 밑줄을 긋고 값을 바로잡았다.
甲은 정점 여덟 개의 요소를 모두 세어 네 개로 적었다. 메모지를 펼쳐 놓고 이 중 정점이 하나뿐인 C와 F를 빼야 한다는 조건에 밑줄을 긋고 답을 둘로 고쳐 다시 적어 넣었다.

강한 연결 요소 중 정점이 둘 이상인 것은 {A, E, B}와 {D, G, H} 두 개다.

9급 데이터 기출 80문항 · 자동복습과 예상점수까지 무료로 →

다음 배열에서 버블 정렬 알고리즘을 사용하여 오름차순 정렬했을 때, 자리바꿈의 총횟수는?

배열 65 40 80 15 오름차순 방향 →

1. 3
2. 4
3. 5
4. 6

정답 2번

🔍 보기별 해설

첫 회전에서 65와 40, 80과 15 두 번, 둘째 회전에서 65와 15 한 번, 셋째 회전에서 40과 15 한 번으로 모두 네 번 바뀐다. 세 번은 하나가 모자라므로 옳지 않다.
65와 40, 80과 15, 65와 15, 40과 15 순으로 네 번 자리를 바꾼다. 역순으로 놓인 짝의 개수가 4라서 바꿈 횟수와 같으므로 옳다(정답).
5는 역순 짝이 다섯 개일 때의 횟수이다. 이 배열에서 크기가 뒤바뀐 짝은 65와 40, 65와 15, 40과 15, 80과 15 네 쌍이라 옳지 않다.
6은 네 개 원소가 완전 역순일 때 나오는 최대 횟수이다. 이 배열은 65와 80, 40과 80의 순서가 이미 맞아 있어 그만큼 줄어드므로 옳지 않다.

🧮 풀이

甲은 버블 정렬의 첫 회전만 세고 두 번, 둘째 회전 한 번으로 세 번이라 적었다. 메모지를 펼쳐 놓고 셋째 회전에서 40과 15가 아직 뒤바뀐 채임을 발견해 한 번을 더 적어 넣었다.
甲은 네 개의 숫자를 종이 위에 늘어놓고 이웃한 두 개씩 차례로 비교했다. 다음으로 자리를 바꾼 짝마다 줄을 그어 표시하자 줄이 모두 네 개가 되어 그 수를 답 칸에 적어 두었다.
甲은 뒤바뀐 쌍의 개수가 바꿈 횟수와 같다는 성질을 이용했다. 펜을 다시 집어 들고 네 쌍뿐인데 다섯 쌍으로 셌다가 65와 80의 순서가 이미 맞는 것을 보고 한 쌍을 지워 냈다.
甲은 네 개가 완전히 거꾸로 놓인 배열에서 바꿈이 여섯 번임을 확인했다. 메모지를 펼쳐 놓고 이번 배열은 두 쌍이 이미 제 순서라 그만큼 줄어든다는 것을 계산식과 함께 표에 적었다.

버블 정렬의 자리바꿈 횟수는 뒤바뀐 짝의 수와 같아 65 40 80 15에서는 4번이다.

다음 표와 같이 분말이 있을 때, 40 kg 무게까지 허용가능한 배낭에 최대 이익을 얻을 수 있도록 분말을 넣는 알고리즘의 C 프로그램이 아래와 같다. (가), (나)에 들어갈 코드와 출력값을 바르게 연결한 것은? (단, 배낭에 각 분말 일부만 넣을 수도 있다)

분말 종류 보유량(kg) 이익

A 10 60

B 18 90

C 25 100

D 15 120

#include

int main() {

double wgt[] = {10, 18, 25, 15};

double val[] = {60, 90, 100, 120};

double ratio[4] = {}, W = 40, max_r,

totalVal = 0.0;

int i, max_i;

for (i = 0; i < 4; i++)

ratio[i] = (가) ;

while (W > 0) {

max_r = -1.0;

max_i = -1;

for (i = 0; i < 4; i++) {

if (wgt[i] > 0 && ratio[i] > max_r) {

max_r = ratio[i];

max_i = i;

}

if (max_i == -1) break;

if (W >= wgt[max_i]) {

W -= wgt[max_i];

totalVal += val[max_i];

}

else {

totalVal += val[max_i] * (나) ;

break;

}

wgt[max_i] = 0;

}

printf("%.1f\n", totalVal);

return 0;

}

(가) (나) 출력값

1. val[i] / wgt[i] W / wgt[max_i] 255.0
2. val[i] / wgt[i] wgt[max_i] / W 255.0
3. val[i] / wgt[i] W / wgt[max_i] 220.0
4. wgt[i] / val[i] W / wgt[max_i] 220.0

정답 1번

🔍 보기별 해설

이익을 무게로 나눈 값이 큰 분말부터 담아야 최적이고, 마지막 분말은 남은 무게 W를 그 분말 무게로 나눈 비율만큼 담는다. D 120, A 60, B의 남은 15/18인 75로 255.0이 나오므로 옳다(정답).
부분만 담을 때 곱하는 비율은 남은 무게 W를 분말 무게로 나눈 값이라야 한다. 분자와 분모를 바꾸면 1보다 큰 값이 곱해져 이익이 부풀려지므로 옳지 않다.
(가)와 (나)는 바르지만 출력값 220.0이 실제 계산과 다르다. D 120과 A 60에 B의 15/18인 75를 더하면 255.0이 나오므로 옳지 않다.
(가)를 무게/이익으로 잡으면 비율이 거꾸로라 값이 낮은 분말이 앞서 선택된다. 가치가 낮은 순으로 담게 되어 최대 이익을 얻는 배낭이 못 되므로 옳지 않다.

🧮 풀이

甲은 분말마다 이익을 무게로 나눈 값을 표에 적었다. D는 8, A는 6, B는 5, C는 4가 나왔고 큰 순서로 담으면서 마지막 B는 15만 담아 총 255가 되는 것을 확인했다.
甲은 마지막 분말을 담는 비율을 무게 나누기 남은 무게로 적어 계산했다. 18/15가 1.2로 1보다 커져 이익이 90에서 108로 부풀려진 것을 보고 분자와 분모를 바꿨다.
甲은 (가)와 (나)를 옳게 넣고 계산을 마쳤는데 출력값을 220으로 적었다. 우선 D 120, A 60, B 75를 다시 더해 보니 255여서 답 칸의 숫자를 고쳐 두었다.
甲은 (가)에 무게를 이익으로 나눈 값을 넣고 손으로 돌려 보았다. 책상 앞에 앉아 가장 먼저 고른 분말이 이익이 낮은 C가 되어 총액이 크게 줄자 이 식을 지우고 처음 식으로 돌아갔다.

무게당 이익 val/wgt 큰 순으로 담고 마지막은 W/wgt만큼 담아 D, A와 B의 15/18로 255.0이다.

다음 C 프로그램의 실행 결과에 포함되지 않는 것은?

#include

int count = 0;

void f(int n, char from, char tmp, char to){

count++;

if (n == 1)

printf("%d: 원판 %d를(을) %c에서 %c로 이동\n", count, n, from, to);

else {

f(n - 1, from, to, tmp);

printf("%d: 원판 %d를(을) %c에서 %c로 이동\n", count, n, from, to);

f(n - 1, tmp, from, to);

}

int main() {

f(3, 'a', 'b', 'c');

return 0;

}

1. 4: 원판 1를(을) c에서 b로 이동
2. 4: 원판 3를(을) a에서 c로 이동
3. 5: 원판 1를(을) b에서 a로 이동
4. 7: 원판 1를(을) a에서 c로 이동

정답 3번

🔍 보기별 해설

f(2)가 만든 두 번째 하위 호출 f(1, c, a, b)가 count를 4로 올린 뒤 원판 1을 c에서 b로 옮긴다고 출력한다. 실제 출력 줄이라 해당한다.
가장 큰 원판 3을 a에서 c로 옮기는 출력은 왼쪽 재귀 호출이 끝난 뒤이며 그때 count는 4이다. 실제 출력 줄이므로 해당한다.
원판 1이 b에서 a로 옮겨지는 출력은 count가 6일 때 나온다. count 5는 f(2)가 호출된 순간의 값일 뿐 그때는 출력이 없어 결과에 해당하지 않는다(정답).
마지막 f(1, a, b, c)가 count를 7로 올려 원판 1을 a에서 c로 옮긴다고 출력한다. 전체 일곱 번의 호출 끝에 나오는 실제 출력 줄이라 해당한다.

🧮 풀이

甲은 f(3, a, b, c)의 호출 순서를 나무로 그리며 호출마다 번호를 붙였다. f(1, c, a, b)가 4번째로 불리고 c에서 b로 옮기는 줄이 찍히는 것을 짚어 표에 옮겼다.
甲은 원판 3장 하노이를 손으로 옮기며 가장 큰 원판이 움직이는 순간을 살폈다. 작은 두 장을 b로 치운 직후인 4번째 호출 시점에서 a에서 c로 이동함을 표에 적어 두었다.
甲은 count가 5가 되는 호출을 찾았다. f(2, b, a, c)를 부르는 순간이지만 그 함수는 먼저 하위 호출을 부르고 출력은 6에서 나온다는 것을 확인해 5번 줄에 가위표를 쳤다.
甲은 마지막 줄의 count 7을 찾아 f(1, a, b, c)가 호출되는 경로를 따라갔다. 원판 하나가 a에서 c로 가는 마지막 이동이 그 호출에서 나오는 것을 확인하고 표 끝에 옮겼다.

count는 호출 때 오르고 출력은 하위 호출 뒤라 원판 1이 b에서 a로 가는 줄의 번호는 5가 아니라 6이다.

비어있는 이진 탐색 트리(binary search tree)에 다음 키값이 순서대로 입력되면, 15를 찾기 위해 방문해야 하는 노드의 개수는?

50, 40, 30, 35, 20, 15, 25, 10

1. 3
2. 4
3. 5
4. 6

정답 3번

🔍 보기별 해설

50, 40, 30까지만 방문하면 3이지만 30 아래 왼쪽에 20이 있고 20의 왼쪽에 15가 있다. 15에 닿으려면 두 노드를 더 거쳐야 하므로 옳지 않다.
50, 40, 30, 20을 지나 15에 닿는 경우를 세면 15 자신을 빼먹은 값이다. 찾는 노드도 방문 횟수에 넣어야 하므로 옳지 않다.
50, 40, 30, 20, 15 순으로 내려가며 15에 도착해 다섯 노드를 방문한다. 삽입한 트리에서 15는 20의 왼쪽 자식에 놓여 있으므로 옳다(정답).
50, 40, 30, 35, 20을 다 밟은 것처럼 센 값이다. 35는 30의 오른쪽 자식이라 15를 찾는 길에서 가지 않으므로 옳지 않다.

🧮 풀이

甲은 트리에서 15를 찾으며 50, 40, 30까지만 방문해 세 개라고 적었다. 30의 왼쪽 자식 20과 그 왼쪽의 15가 남아 있음을 발견해 화살표를 두 개 더 이어 그렸다.
甲은 방문한 노드 이름을 모두 적어 세었는데 15는 도착점이라 빼고 4개로 적었다. 책상 앞에 앉아 찾는 값의 노드도 방문 횟수에 든다는 점을 알고 15를 목록 맨 끝에 더해 넣었다.
甲은 50에서 15보다 작으니 왼쪽, 40에서 왼쪽, 30에서 왼쪽, 20에서 왼쪽으로 내려가며 15를 찾았다. 우선 방문한 다섯 노드에 번호를 매겨 답 칸에 5를 적어 넣었다.
甲은 30 아래의 35까지 방문 목록에 넣어 여섯 개로 세었다. 표를 한 번 더 훑고 15보다 큰 35 쪽은 오른쪽 가지라 지나갈 이유가 없음을 알고 35를 목록에서 지워 냈다.

15까지 50, 40, 30, 20, 15의 다섯 노드를 방문한다.

다음 배열에서 보간 탐색(interpolation search)으로 58을 찾고자 할 때, 첫 번째 탐색 위치는? (단, 배열에서 위치의 차이는 값의 차이에 비례한다는 가정하에 탐색 위치를 계산하며 소수점 이하는 반올림한다)

위치 0 1 2 3 4 5 6 7 8 9 배열 3 7 12 22 32 58 67 80 87 89

1. 2
2. 4
3. 6
4. 8

정답 3번

🔍 보기별 해설

위치 2는 값 12가 있는 자리다. 3에서 89 사이에서 58은 뒤쪽 3분의 2 가까이에 있어 계산 결과가 훨씬 뒤에 나오므로 옳지 않다.
위치 4는 값 32가 있는 자리다. 비례식이 가리키는 5.76이 아닌 이보다 앞의 위치라서 첫 탐색 위치로 삼을 수 없으므로 옳지 않다.
첫 위치는 0 + (58-3)/(89-3) × 9로 약 5.76이고 반올림하면 6이다. 위치 6에는 67이 있어 다음 탐색이 왼쪽으로 이어지므로 옳다(정답).
위치 8은 값 87이 있는 자리다. 58이 89에 가까운 것이 아니라 중간 뒤쪽이어서 계산 결과가 이만큼 커지지 않으므로 옳지 않다.

🧮 풀이

甲은 값이 3에서 89까지인 배열에서 58이 전체 폭의 몇 퍼센트에 있는지 계산했다. 곧이어 결과가 약 64퍼센트로 나와 위치 2의 12는 너무 앞이라고 표 옆에 적어 두었다.
甲은 위치 4의 값 32를 확인하고 58과의 차이를 계산했다. 다음으로 비례식이 이 자리를 가리키려면 58이 훨씬 작아야 한다는 것을 알고 계산식을 처음부터 다시 적어 내려갔다.
甲은 위치를 0 + 55/86 × 9로 계산해 5.76이 나온 것을 소수점 아래 반올림해 6으로 적었다. 우선 위치 6의 값 67을 보고 다음 범위를 왼쪽으로 좁힐 준비를 했다.
甲은 위치 8의 값 87이 58보다 훨씬 커서 그 자리를 첫 탐색 위치로 고르면 뒤로 너무 치우친다고 보았다. 식에 넣은 값이 89에 가깝지 않다는 것을 계산해 보이고 답에서 지웠다.

보간 탐색의 첫 위치는 0+(58-3)/(89-3)×9≈5.76이므로 반올림해 6이다.

다음과 같이 전체 버킷 개수가 13개이고 버킷당 1개의 슬롯을 가지는 비어있는 해시 테이블에 값 를 순서대로 해시 함수를 사용하여 저장하였을 때, 버킷 번호 4에 저장되는 값은? (단, 해시 함수로 h(x) = x mod 13 을 사용하며, 충돌 해결은 개방 주소 방법의 선형 조사법(linear probing)을 적용한다)

버킷 번호 슬롯 0 1 2 3 4 5 6 7 8 9 10 11 12

1. 4
2. 46
3. 67
4. 81

정답 3번

🔍 보기별 해설

값 4는 4 mod 13이라 해시 결과는 버킷 4이다. 하지만 그보다 먼저 저장된 67이 선형 조사로 4번을 차지해 4는 5번으로 밀리므로 옳지 않다.
46은 13으로 나눈 나머지가 7이라 처음엔 7번을 노리지만 7번이 7로, 8번이 20으로 차 있어 9번에 저장된다. 4번에 들어가지 않으므로 옳지 않다.
67은 13으로 나눈 나머지가 2라 2번을 노리지만 28이 2번, 81이 3번에 있어 한 칸씩 뒤로 가 4번에 들어간다. 4번에 저장되는 값이므로 옳다(정답).
81은 13으로 나눈 나머지가 3이라 그 자리가 비어 있어 충돌 없이 곧바로 3번에 저장된다. 4번까지 밀리지 않으므로 옳지 않다.

🧮 풀이

甲은 값 4를 넣으며 4 mod 13이 4라 4번에 넣으려다 이미 67이 차 있음을 발견했다. 곧이어 선형 조사로 5번의 빈칸으로 옮겨 넣고 저장 순서표를 처음부터 다시 확인했다.
甲은 46을 넣을 때 7번과 8번이 각각 7과 20으로 차 있어 9번까지 한 칸씩 내려갔다. 다음으로 그 과정을 표 오른쪽에 화살표로 적고 4번 칸에는 이 값이 없음을 표시했다.
甲은 67의 나머지가 2라서 2번과 3번이 이미 28, 81로 차 있음을 확인했다. 펜을 다시 집어 들고 한 칸씩 뒤로 가서 4번의 빈칸에 넣은 뒤 그 칸에 67이라고 진하게 적었다.
甲은 81이 13으로 나누어 나머지 3이라 3번에 바로 들어가는 것을 보았다. 책상 앞에 앉아 충돌이 없으므로 4번까지 갈 일이 없다는 것을 알고 화살표 없이 그 칸에 곧바로 저장했다.

선형 조사로 67은 2, 3번이 차 있어 4번에 저장된다.

다음 두 문자열 A와 B의 편집 거리(edit distance)는? (단, 허용하는 문자열 연산은 삽입, 삭제, 교체 연산이다)

○ 문자열 A: algorithm

○ 문자열 B: anthem

1. 5
2. 6
3. 7
4. 9

정답 2번

🔍 보기별 해설

a, t, h, m 네 글자를 맞추고도 l g o r i를 n으로 바꾸는 데 다섯 번, e를 끼워 넣는 데 한 번이 더 든다. 5로는 이 두 몫을 다 셀 수 없으므로 옳지 않다.
a, t, h, m을 그대로 두고 lgori를 n으로 바꾸는 데 교체 한 번과 삭제 네 번, e를 끼워 넣는 데 삽입 한 번이 든다. 합이 6이 되어 동적 계획법 표의 마지막 칸과 같으므로 옳다(정답).
7은 삭제나 삽입을 한 번 더 세었을 때의 값이다. 교체 한 번이 삭제나 삽입 두 번 몫을 대신하므로 그만큼 줄어들어 옳지 않다.
9는 algorithm의 글자 수와 같아 글자를 살릴 방법을 전혀 쓰지 않은 값이다. a, t, h, m을 남기고 나머지만 고치면 훨씬 적게 들어 옳지 않다.

🧮 풀이

甲은 두 단어를 위아래로 쓰고 겹치는 a, t, h, m을 밑줄로 이었다. 남은 글자를 바꾸고 지우고 넣는 데 든 횟수를 세어 5로 적었다가 e를 빠뜨린 것이 보여 한 줄을 더 적었다.
甲은 두 단어로 표를 만들어 첫 행과 첫 열에 0부터 숫자를 채웠다. 다음으로 왼쪽, 위, 대각선 값 중 작은 것에 1을 더해 채워 가다가 오른쪽 아래 칸에 6이 나온 것을 적었다.
甲은 교체 하나가 삭제와 삽입 두 번보다 싸다는 규칙을 적어 두었다. 7이라 적었던 계산에서 삭제와 삽입으로 처리한 자리를 교체로 바꾸자 한 번이 줄어들어 값을 고쳐 적었다.
甲은 글자를 모두 지우고 새로 쓰는 방식이 아니라 남길 글자를 찾는 방식을 시험했다. algorithm의 길이 9에 미치지 못하는 값이 나오는 것을 보고 9라는 답을 지웠다.

algorithm에서 anthem으로 가는 편집 거리는 교체 1, 삭제 4, 삽입 1로 6이다.

다음 배열에 대해 아래 알고리즘을 적용하여 정렬하고자 한다. 3번째 for 루프를 수행할 때, 배열 내에서 교환되는 두 값은?

위치 0 1 2 3 4 5 6 7 8 9 배열 9 21 54 32 77 45 19 83 12 3 Sort(A[], n): // n은 입력배열 A의 크기이다. for last ← (n – 1) downto 1 A[0 ... last] 중 가장 큰 수 A[k]를 찾는다. A[k]와 A[last]의 값을 교환한다.

1. 3, 54
2. 21, 45
3. 21, 54
4. 32, 77

정답 1번

🔍 보기별 해설

세 번째 반복은 last가 7이라 A[0..7]에서 가장 큰 54를 골라 A[7]에 있는 3과 바꾼다. 앞선 두 번에서 83과 77이 자리를 잡은 뒤이므로 옳다(정답).
21과 45를 바꾸려면 그 둘이 구간의 가장 큰 값과 마지막 자리여야 하지만 세 번째 반복의 최댓값은 54이고 끝자리는 3이다. 이 쌍은 나오지 않으므로 옳지 않다.
54는 최댓값으로 맞지만 마지막 자리인 A[7]에 있는 값은 21이 아니라 3이다. 21은 A[1]에 그대로 남아 있으므로 옳지 않다.
77은 두 번째 반복에서 이미 A[8] 자리로 옮겨 가 정렬이 끝난 값이다. 세 번째 반복의 구간 A[0..7]에는 77이 없으므로 옳지 않다.

🧮 풀이

甲은 배열을 종이에 세 번 베껴 쓰며 선택 정렬을 손으로 진행했다. 첫 반복에서 83과 3, 둘째에서 77과 12, 셋째에서 54와 3이 바뀌는 것을 색연필로 이어 표시했다.
甲은 21과 45가 배열에서 이웃한 값이라 바뀐다고 착각했다. 책상 앞에 앉아 세 번째 반복의 구간 끝이 A[7]이고 그 값이 3임을 다시 읽고 답 칸에 적었던 값을 지워 고쳤다.
甲은 세 번째 반복의 최댓값 54는 옳게 찾았지만 교환 상대를 21로 적었다. 펜을 다시 집어 들고 A[7]을 배열에서 직접 짚어 보니 3이 놓여 있어 상대를 바꿔 적고 표에 표시했다.
甲은 77을 세 번째 반복의 최댓값으로 고르려다 이미 A[8]로 자리를 옮긴 것을 알았다. 표를 한 번 더 훑고 구간을 A[0]부터 A[7]까지로 좁혀 다시 훑고 77을 후보에서 지웠다.

선택 정렬의 세 번째 반복은 last가 7이라 A[0..7]의 최댓값 54와 A[7]의 3을 바꾼다.

다음과 같이 오름차순 정렬을 수행하는 알고리즘은?

초기 상태 5 20 17 6 2 13 10 1단계 5 20 17 6 2 13 10 2단계 5 17 20 6 2 13 10 3단계 5 6 17 20 2 13 10 4단계 2 5 6 17 20 13 10 5단계 2 5 6 13 17 20 10 6단계 2 5 6 10 13 17 20

1. 병합 정렬
2. 삽입 정렬
3. 선택 정렬
4. 퀵 정렬

정답 2번

🔍 보기별 해설

병합 정렬은 배열을 절반씩 나눈 뒤 정렬된 조각을 합친다. 제시된 단계는 앞부분 정렬된 구간에 한 원소씩 끼워 넣어 늘려 가는 모양이라 옳지 않다.
앞쪽 정렬된 구간이 1단계에 5 20, 2단계에 5 17 20, 3단계에 5 6 17 20으로 한 칸씩 늘어난다. 새 원소를 그 구간의 알맞은 자리에 끼워 넣는 모양이므로 옳다(정답).
선택 정렬은 남은 구간에서 최솟값을 골라 맨 앞과 바꾼다. 여기서는 2단계에 17이 20과 자리를 바꾸는 모양이라 최솟값을 앞으로 보내는 과정과 다르므로 옳지 않다.
퀵 정렬은 기준값을 골라 그보다 작은 값과 큰 값으로 나눈다. 제시된 단계에는 기준값을 가운데에 두고 양쪽으로 가르는 모습이 없으므로 옳지 않다.

🧮 풀이

甲은 카드 일곱 장을 반으로 갈라 두 묶음을 각각 정렬한 뒤 합치는 방식을 해 보았다. 다음으로 제시된 표에서는 한 장씩 늘어나는 구간만 있어 이 방식과 다르다고 적어 두었다.
甲은 손에 든 카드 앞쪽 정렬된 묶음에 새 카드를 뽑아 알맞은 자리에 끼웠다. 책상 앞에 앉아 카드가 5, 6, 17, 20 다음에 2가 들어오자 앞쪽으로 계속 밀어 맨 앞에 놓았다.
甲은 남은 카드 가운데 가장 작은 카드를 골라 맨 앞 카드와 바꾸는 방식을 적어 보았다. 우선 표의 첫 단계에서 2가 맨 앞으로 오지 않는 것을 보고 이 방식이 아님을 확인했다.
甲은 첫 카드 5를 기준으로 삼아 작은 값과 큰 값을 양쪽으로 갈라 세웠다. 메모지를 펼쳐 놓고 표의 단계마다 기준 카드가 가운데 자리를 잡는 흔적이 보이지 않아 이 선택지를 지웠다.

왼쪽 정렬 구간에 새 원소를 끼워 넣으며 늘려 가므로 삽입 정렬이다.

문자에 대한 빈도수가 다음과 같을 때, exam을 허프만(Huffman) 코드로 작성하면 비트 수는?

문자 a b c e m x 빈도수 8 5 3 10 6 1

1. 10
2. 11
3. 12
4. 14

정답 1번

🔍 보기별 해설

빈도가 낮은 x(1)와 c(3), 이어 그 합 4와 b(5), m(6)과 a(8), 9와 e(10) 순으로 합쳐 e, a, m은 2비트, x, c는 4비트가 된다. exam은 2+4+2+2로 10비트이므로 옳다(정답).
11은 한 글자를 필요보다 한 비트 길게 셌을 때의 합이다. e, x, a, m이 각각 2, 4, 2, 2비트라 합은 10이므로 옳지 않다.
12는 m이나 a를 3비트로 잘못 잡아 늘린 값이다. m(6)과 a(8)는 바로 합쳐져 2비트라 exam의 합은 10이므로 옳지 않다.
14는 exam의 각 글자에 실제보다 긴 부호를 붙인 값이다. 빈도 10인 e는 2비트, 6과 8인 m과 a도 2비트여서 짧게 배정되므로 합이 10이라 옳지 않다.

🧮 풀이

甲은 빈도가 가장 낮은 x와 c를 먼저 묶고 그 합 4를 b와 묶어 나갔다. 나무를 완성하고 e, a, m에 2비트, x에 4비트를 매겨 exam을 읽어 내려가며 10이라고 적었다.
甲은 exam의 네 글자에 붙은 비트를 2, 4, 2, 2로 적었다가 e를 3비트로 잘못 넣어 11을 얻었다. 빈도 10의 e가 가장 짧은 2비트를 받는다는 것을 알고 값을 고쳤다.
甲은 m과 a가 바로 합쳐지는 것을 놓치고 한 층 더 내려가 3비트로 적었다. 펜을 다시 집어 들고 두 글자의 빈도 합 14가 마지막 합병에 바로 참여하는 것을 확인해 12를 지웠다.
甲은 빈도가 높은 글자일수록 부호가 짧다는 원리에 따라 부호 길이를 다시 셌다. 표를 한 번 더 훑고 각 글자에 긴 부호를 준 14를 정답으로 적었던 계산을 지우고 e에 2비트를 주었다.

허프만 트리에서 e, a, m은 2비트, x는 4비트이므로 exam은 2+4+2+2로 10비트다.