알고리즘 단원 모의 문제 · 정보처리기사

21단원 '알고리즘'의 다섯 레슨에서 6문제, 앞 단원(20)에서 2문제를 섞었고, 끝에 실기 꼴 3문제가 있습니다. 앞 단원 문제가 어느 레슨인지는 정답을 펼치면 보입니다. 알고리즘은 시험에서는 1과목 문제로 나옵니다. 코드의 출력은 Python 3.15로 돌린 결과입니다. 실기 꼴은 종이에 답을 끝까지 쓴 뒤 펼치세요. 띄어쓰기만 다르면 같은 답입니다.

문제 1

다음 C 코드에서 cnt++가 실행되는 횟수를 시간 복잡도로 나타낸 것을 고르세요.

cnt = 0;
for (i = 1; i < n; i *= 2)
    for (j = 0; j < n; j++)
        cnt++;

① O(log n)
② O(n)
③ O(n log n)
④ O(n²)

정답

③ — 바깥 반복은 i가 1, 2, 4, 8, …로 두 배씩 커지다 n에 닿으면 멈춰 log₂ n번 남짓 돌고, 안쪽 반복은 바깥 반복 한 번마다 n번 돕니다. 모두 n × log₂ n번이라 O(n log n)입니다. n이 16이면 4 × 16 = 64번, 32면 5 × 32 = 160번입니다.

① 바깥 반복만 봤습니다. 바깥 반복이 한 번 돌 때마다 안쪽 반복이 n번씩 돌아 횟수가 곱해집니다.
② 두 반복의 횟수를 더했습니다. 안쪽 반복이 바깥 반복 안에 들어 있으면 더하지 않고 곱합니다.
④ 두 겹 반복이면 늘 O(n²)이라고 봤습니다. 바깥 반복은 n번이 아니라, i가 두 배씩 건너뛰어 log₂ n번 남짓입니다.

다시 볼 레슨: 알고리즘과 시간 복잡도

문제 2

값 1,000개를 담은 배열과, 같은 값을 차례대로 담은 연결 리스트가 있습니다. 연결 리스트는 첫 노드를 가리키는 head만 알고 있습니다. (가) 500번째 값을 읽는 일과 (나) 맨 앞에 새 값 하나를 넣는 일을 각각 더 빨리 끝내는 쪽으로 알맞은 것을 고르세요.

① (가) 배열 · (나) 배열
② (가) 배열 · (나) 연결 리스트
③ (가) 연결 리스트 · (나) 배열
④ (가) 연결 리스트 · (나) 연결 리스트

정답

② — 배열은 번호로 500번째 칸에 곧바로 가지만, 연결 리스트는 head에서 출발해 화살표를 499번 따라가야 닿습니다. 데이터가 늘어도 한 번이면 O(1), 늘어난 만큼 따라가면 O(n)입니다. 맨 앞에 넣을 때는 거꾸로입니다. 배열은 1,000개를 모두 한 칸씩 뒤로 옮겨야 하고, 연결 리스트는 새 노드가 첫 노드를 가리키게 한 뒤 head가 새 노드를 가리키게 하면 끝납니다.

① 배열은 칸이 이어져 있어 넣기도 빠르다고 봤습니다. 맨 앞에 넣으려면 뒤의 값을 모두 한 칸씩 옮겨야 합니다.
③ 두 자리를 거꾸로 봤습니다. 번호로 곧바로 가는 것은 배열, 화살표만 바꿔 끼우는 것은 연결 리스트의 강점입니다.
④ 연결 리스트는 포인터로 어느 노드에나 곧바로 간다고 봤습니다. 노드의 포인터는 다음 노드 하나만 가리켜, 500번째 노드는 head부터 따라가야 닿습니다.

다시 볼 레슨: 연결 리스트 · 알고리즘과 시간 복잡도

문제 3

줄 4, 6, 8, 1, 3, 2를 선택 정렬로 작은 값부터 정렬합니다. 3회전 뒤의 모습을 고르세요.

① 1, 2, 3, 4, 8, 6
② 1, 2, 8, 4, 3, 6
③ 1, 3, 2, 4, 6, 8
④ 1, 4, 6, 8, 3, 2

정답

① — 선택 정렬은 회전마다 아직 정해지지 않은 칸 가운데 가장 작은 값을 찾아 그 구간의 맨 앞과 바꿉니다. 1회전에 1과 4를 바꿔 1, 6, 8, 4, 3, 2, 2회전에 2와 6을 바꿔 1, 2, 8, 4, 3, 6, 3회전에 3과 8을 바꿔 1, 2, 3, 4, 8, 6이 됩니다. 앞에서부터 세 칸이 정해졌습니다.

② 회전을 하나 덜 셌습니다. 2회전 뒤의 모습이라 셋째 칸이 아직 8입니다.
③ 버블 정렬로 돌렸습니다. 이웃끼리 바꿔 큰 값 8·6·4가 뒤에서부터 자리를 잡은 버블 정렬의 3회전 뒤입니다.
④ 삽입 정렬로 돌렸습니다. 앞쪽 네 칸은 정렬됐지만 제자리가 아니고, 3과 2는 아직 꺼내지 않은 삽입 정렬의 3회전 뒤입니다.

다시 볼 레슨: 선택·버블·삽입 정렬

문제 4

줄을 칸 번호 차례로 완전 이진 트리에 놓습니다. i번 칸의 자식은 2i번과 2i + 1번 칸입니다. 최대 힙이 아닌 것을 고르세요.

① 9, 4, 7, 5, 1, 6, 3
② 9, 6, 8, 2, 5, 7, 4
③ 9, 7, 3, 6, 5, 2, 1
④ 9, 8, 7, 6, 5, 4, 3

정답

① — 최대 힙은 모든 부모가 자식보다 크거나 같아야 합니다. 2번 칸의 4는 자식인 4번 칸의 5보다 작아 최대 힙이 아닙니다. 루트의 9가 가장 커서 루트만 보면 지나치기 쉽습니다.

② 맞습니다. 왼쪽 자식이 오른쪽 자식보다 커야 한다고 보면 고르게 됩니다. 2번 칸의 6과 3번 칸의 8은 형제라 서로 견주지 않고, 부모와 자식 사이만 봅니다.
③ 맞습니다. 위 층의 값이 아래 층의 값보다 모두 커야 한다고 보면 고르게 됩니다. 3번 칸의 3은 다른 갈래의 6·5보다 작지만, 제 자식인 2·1보다 크면 됩니다.
④ 맞습니다. 힙은 정렬된 줄이 아니라고 외워 두면 고르게 됩니다. 정렬까지 되어 있을 필요가 없을 뿐, 큰 값부터 늘어선 줄도 부모가 자식보다 늘 커서 최대 힙입니다.

다시 볼 레슨: 퀵·병합·힙 정렬

문제 5

이진 트리의 노드 자리에 위 층부터, 같은 층에서는 왼쪽부터 1, 2, 3, … 번호를 붙였습니다. i번 자리의 왼쪽 자식은 2i번, 오른쪽 자식은 2i + 1번 자리입니다. 노드가 있는 자리가 다음과 같을 때, 완전 이진 트리인 것을 고르세요.

① 1, 2, 4, 5번
② 1, 2, 3, 4, 5번
③ 1, 2, 3, 6, 7번
④ 1, 2, 3, 4, 5, 6, 7, 9번

정답

② — 완전 이진 트리는 위 층부터, 같은 층에서는 왼쪽부터 빈틈없이 채운 트리라, 자리 번호가 1부터 빠짐없이 이어집니다. 1~5번은 레벨 1·2가 꽉 차고 레벨 3은 왼쪽 두 자리인 4·5번만 찼습니다. 3번 노드에 자식이 없어도 됩니다.

① 층마다 왼쪽부터 채우기만 하면 된다고 봤습니다. 레벨 2의 3번 자리가 빈 채로 레벨 3에 노드가 있어, 위 층부터 채우지 않았습니다.
③ 같은 층의 노드가 한쪽에 몰려 있기만 하면 된다고 봤습니다. 6·7번은 레벨 3의 오른쪽 끝이라, 왼쪽의 4·5번을 비워 둔 채 채웠습니다.
④ 마지막 층은 덜 차도 되니 어느 자리에 있어도 된다고 봤습니다. 덜 찬 마지막 층도 왼쪽부터 채워야 하는데, 8번이 빈 채로 9번에 노드가 있습니다.

다시 볼 레슨: 트리 · 퀵·병합·힙 정렬

문제 6

정렬된 줄 3, 8, 11, 15, 19, 24, 27, 31, 36, 40, 45, 52(위치 1~12)에서 40을 찾습니다. (가) 이진 탐색으로 찾을 때 견주는 횟수와 (나) 앞에서부터 하나씩 견주는 순차 탐색으로 찾을 때 견주는 횟수로 알맞은 것을 고르세요. 이진 탐색의 가운데는 (처음 + 끝) ÷ 2의 몫입니다.

① (가) 2 · (나) 10
② (가) 2 · (나) 12
③ (가) 4 · (나) 10
④ (가) 4 · (나) 12

정답

③ — 1~12번의 가운데 6번(24)은 40보다 작아 7~12번이 남고, 9번(36)도 작아 10~12번이 남습니다. 11번(45)은 커서 10번만 남고, 10번에서 네 번째에 찾습니다. 순차 탐색은 1번부터 견주어 40이 있는 10번에서 열 번째에 찾습니다.

① 가운데를 몫이 아니라 올림으로 잡았습니다. 6.5를 올려 7번(27)부터 보면 두 번 만에 닿지만, 문제는 몫을 쓰라고 했습니다.
② 두 오해가 겹쳤습니다. 가운데를 올림으로 잡았고, 순차 탐색은 늘 끝까지 본다고 봤습니다.
④ 순차 탐색은 늘 n번 견준다고 봤습니다. 찾는 값에 닿으면 멈추므로 10번입니다. n번은 찾는 값이 맨 끝에 있거나 없을 때입니다.

다시 볼 레슨: 이진 탐색과 해싱 · 알고리즘과 시간 복잡도

문제 7

0~12번 칸의 해시 테이블에 키를 13으로 나눈 나머지 칸에 넣습니다. 키 27, 40, 14, 53, 16을 이 차례로 넣을 때, (가) 충돌을 선형 조사로 풀면 16이 들어가는 칸과 (나) 충돌을 체이닝으로 풀면 1번 칸에 매달리는 키의 수로 알맞은 것을 고르세요.

① (가) 3 · (나) 1
② (가) 3 · (나) 4
③ (가) 5 · (나) 1
④ (가) 5 · (나) 4

정답

④ — 27, 40, 14, 53은 모두 13으로 나눈 나머지가 1입니다. 선형 조사로는 1·2·3·4번 칸에 차례로 들어가고, 나머지가 3인 16은 3번 칸(14)과 4번 칸(53)이 차 있어 5번 칸에 들어갑니다. 체이닝은 다른 칸을 차지하지 않고 같은 칸에 이어 매달아, 1번 칸에 27, 40, 14, 53 네 개가 달립니다.

① 두 오해가 겹쳤습니다. 16의 칸인 3번이 비어 있다고 봤고, 체이닝도 빈칸을 찾아 옮긴다고 봤습니다.
② 3번 칸이 비어 있다고 봤습니다. 14는 계산된 칸이 1번이지만 1·2번이 차 있어 3번에 먼저 들어갔습니다. 부딪힌 키가 이웃 칸을 차지해 한곳에 몰리는 것이 선형 조사의 약점입니다.
③ 체이닝도 선형 조사처럼 빈칸을 찾아 옮긴다고 봤습니다. 체이닝은 같은 칸으로 계산된 키를 그 칸에 연결 리스트로 이어 매답니다.

다시 볼 레슨: 이진 탐색과 해싱

문제 8

배낭에 무게 합이 10을 넘지 않게 물건을 골라, 값의 합을 가장 크게 하려고 합니다. 무게 0부터 10까지 칸을 두고, 칸마다 '그 무게 안에서 얻는 가장 큰 값'을 적어 둡니다. 물건을 하나씩 살필 때마다 앞서 적어 둔 칸의 값을 꺼내 와 칸을 새로 채웁니다. 이 풀이에 쓰인 알고리즘 설계 기법을 고르세요.

① 백트래킹
② 분할 정복
③ 탐욕 알고리즘
④ 동적 계획법

정답

④ — 작은 무게의 답을 칸에 적어 두고, 큰 무게의 답을 셀 때 그 칸을 꺼내 다시 씁니다. 겹치는 작은 문제를 다시 계산하지 않는 풀이가 동적 계획법입니다.

① 물건을 넣었다 뺐다 하며 되돌아간다고 봤습니다. 백트래킹은 길을 따라가다 조건에 어긋나면 앞 갈림길로 돌아가는데, 이 풀이는 칸을 차례로 채울 뿐 되돌아가지 않습니다.
② 무게를 작게 나눠 푸는 것으로 봤습니다. 분할 정복은 나눈 문제끼리 겹치지 않아 답을 적어 두지 않습니다. 여기서는 앞서 적은 칸을 여러 번 꺼내 씁니다.
③ 배낭에 물건을 고르는 문제라 탐욕으로 봤습니다. 탐욕은 그 순간 값이 큰 것부터 넣고 무르지 않으며, 적어 둔 답을 다시 꺼내 쓰지 않습니다.

다시 볼 레슨: 알고리즘 설계 기법

문제 9 (실기)

택배 보관함의 칸 번호를 송장 번호로 계산해 정합니다. 계산한 칸이 이미 차 있을 때 쓰는 (가)·(나) 방법의 이름을 영문으로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

(가) 계산한 칸의 바로 다음 칸부터 하나씩 차례로 살펴, 처음 만나는 빈칸에 넣습니다.
(나) 칸마다 고리를 달아 두고, 같은 칸으로 계산된 택배를 그 칸의 고리에 줄줄이 이어 매답니다.

정답

받는 답: (가) Linear Probing · (나) Chaining

(가)의 실마리는 '바로 다음 칸부터 차례로 살펴 빈칸에', (나)는 '같은 칸에 줄줄이 이어 매단다'입니다.

같은 이름의 다른 꼴: (가) 선형 조사 · (나) 체이닝 — 한글 이름입니다. 문제가 영문으로 물었습니다.
틀리는 꼴 Open Addressing — (가)에: 보관함 안의 다른 빈칸을 찾아 넣는 방법들을 통틀어 부르는 이름입니다. 바로 다음 칸부터 차례로 보는 방법 하나의 이름을 물었습니다.
틀리는 꼴 Collision — (나)에: 계산한 칸이 서로 겹친 일 자체의 이름입니다. 묻는 것은 겹쳤을 때 푸는 방법입니다.

다시 볼 레슨: 이진 탐색과 해싱

문제 10 (실기)

회사 조직도를 트리로 그렸습니다. 사장이 루트이고, 사람마다 바로 아래에 그 사람에게 딸린 직원이 이어집니다. (가)·(나)에 맞는 트리 용어를 한글로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

(가) 아래에 딸린 직원이 한 명도 없는 사원 한 사람의 자리
(나) 한 부장에게 바로 딸린 팀장이 셋이면 그 부장 자리에서 3이 되는 값. 팀장 아래의 사원은 세지 않습니다.

정답

받는 답: (가) 단말 노드 또는 잎 노드 · (나) 차수 또는 디그리

(가)의 실마리는 '아래에 딸린 사람이 없다', (나)는 '바로 아래 자식만 센 수'입니다. 잎 노드와 디그리는 자료에 따라 부르는 이름이라 함께 받습니다.

같은 이름의 다른 꼴: (가) Terminal Node · (나) Degree — 영문입니다. 문제가 한글로 물었습니다.
틀리는 꼴 루트 노드 — (가)에: 맨 위 사장의 자리입니다. 부모가 없는 노드이지, 자식이 없는 노드가 아닙니다.
틀리는 꼴 레벨 — (나)에: 루트를 1로 세어 내려가며 매긴 층 번호입니다. 부장이 있는 층의 번호이지, 부장에게 딸린 사람 수가 아닙니다.

다시 볼 레슨: 트리

문제 11 (실기)

다음 코드의 실행 결과를 그대로 쓰세요. [4, 1, 3, 2, 5]는 C의 배열처럼 0번부터 번호로 꺼내 쓰는 Python의 리스트입니다. 답을 끝까지 쓴 뒤 정답을 펼치세요.

def bubble(a):
    p = 0
    swap = 1
    while swap == 1:
        swap = 0
        p = p + 1
        j = 0
        while j < 4:
            if a[j] > a[j + 1]:
                t = a[j]
                a[j] = a[j + 1]
                a[j + 1] = t
                swap = 1
            j = j + 1
    return p

a = [4, 1, 3, 2, 5]
b = [1, 2, 3, 4, 5]
print(bubble(a))
print(bubble(b))

정답

받는 답:

실행 결과

3
1

bubble은 이웃끼리 견줘 앞이 크면 바꾸는 버블 정렬이고, 한 회전 동안 한 번도 바꾸지 않으면 멈춥니다. p는 돈 회전 수입니다. a는 1회전에 4가 1·3·2와 차례로 바뀌어 1, 3, 2, 4, 5, 2회전에 3과 2가 바뀌어 1, 2, 3, 4, 5가 됩니다. 2회전에도 바꾼 것이 있어 swap이 1이라, 바꿀 것이 없는 3회전을 돌고 나서야 멈춰 3입니다. b는 처음부터 정렬되어 있지만, 바꿀 것이 없다는 것을 알려면 한 회전은 돌아야 해서 1입니다.

틀리는 꼴 2와 1: a가 다 정렬된 2회전에서 바로 멈춘다고 봤습니다. 반복은 한 번도 바꾸지 않은 회전을 마친 뒤에야 멈춥니다.
틀리는 꼴 3과 0: 정렬된 b는 한 회전도 돌지 않는다고 봤습니다. while 조건을 처음 볼 때 swap이 1이라 한 번은 들어갑니다.
틀리는 꼴 4와 4: 늘 값의 수보다 하나 적은 4회전을 돈다고 봤습니다. swap이 0이면 바깥 while이 멈춥니다.

다시 볼 레슨: 선택·버블·삽입 정렬