[국회직 9급 컴퓨터일반] 20년 1회차 기출문제 정답·해설 페이지

Accumulator(누산기)는 병렬처리 기술이 아니라 연산 결과를 임시로 저장하는 CPU 레지스터다.
병렬처리 기술은 여러 명령이나 스레드를 동시에 또는 겹쳐서 실행해 처리량을 높이는 방식이다. 누산기는 저장 장소일 뿐 동시 실행과는 관계가 없다.
Pipelining: 명령어 처리를 여러 단계로 나누어 겹쳐 실행하는 병렬화 기법이다.
Superscalar: 여러 개의 실행 유닛으로 한 클록에 복수의 명령어를 동시에 내보내는 기법이다.
VLIW: 동시에 실행할 연산을 컴파일러가 하나의 긴 명령어로 묶어 실행하는 기법이다.
SMT: 한 코어에서 여러 스레드의 명령어를 동시에 실행하는 기법이다.

패킷의 실제 도착 순서를 바꾸지 않고 재조립한다는 설명이 틀렸다. TCP는 순서 번호(sequence number)로 패킷을 재정렬해 데이터를 재조립한다.
하위 IP 계층은 패킷의 도착 순서를 보장하지 않으므로, TCP가 수신 측에서 순서를 바로잡아 응용 계층에 순서대로 전달한다.
흐름제어: 수신 윈도우로 전송량을 조절하는 기능이 TCP에 있고 UDP에는 없다.
혼잡제어: 네트워크 상황에 맞춰 전송률을 낮추는 기능이 TCP에 있고 UDP에는 없다.
연결 지향성: TCP는 3-way handshake로 연결을 맺지만 UDP는 비연결형이다.
실시간 스트리밍: UDP는 재전송과 연결 절차가 없어 지연이 적으므로 더 적합하다.

옳은 설명은 ㄱ, ㄷ, ㄹ, ㅁ이고, ㄴ만 틀렸다.
전가상화에서는 게스트 OS를 수정하지 않고 그대로 실행할 수 있다. 수정이 필요한 것은 반가상화이므로 ㄴ이 든 조합은 모두 제외되고, 나머지 넷을 모두 담은 조합만 남는다.
ㄱ(O): 하드웨어를 직접 제어하는 Type-1과 운영체제 위에서 동작하는 Type-2가 모두 존재한다.
ㄴ(X): 게스트 OS 수정은 반가상화에서만 필요하며 전가상화에서는 필요 없다.
ㄷ(O): Type-2는 호스트 OS 위에서 응용 프로그램처럼 실행된다.
ㄹ(O): 전가상화와 반가상화는 게스트 OS 수정 여부가 다를 뿐 둘 다 하이퍼바이저를 쓴다.
ㅁ(O): KVM은 리눅스 커널 자체를 하이퍼바이저로 동작시키므로 Type-1로 분류될 수 있다.

깊이 우선 탐색의 방문 순서는 A-B-E-F-K-C-G-D-H-I-L-J이다.
깊이 우선 탐색은 한 자식 쪽으로 더 내려갈 수 없을 때까지 내려간 뒤 되돌아와 다음 자식으로 넘어간다. 왼쪽 자식부터 살피면 전위 순회와 같은 순서가 된다.
B 서브트리: A → B → E, 되돌아와 F → K
C 서브트리: C → G
D 서브트리: D → H → I → L, 되돌아와 J
A-B-C-D-E-F-G-H-I-J-K-L은 같은 깊이의 노드를 차례로 방문한 순서로, 너비 우선 탐색의 결과이다.
A-B-E-K-F-C-G-D-H-I-L-J는 E 다음에 K를 방문하지만, K는 F의 자식이므로 F보다 먼저 방문할 수 없다.
A-E-K-F-B-G-C-H-L-I-J-D는 A 다음에 바로 E로 가지만, E는 B의 자식이므로 B를 거치지 않고 도달할 수 없다.
A-K-L-E-F-G-H-I-J-B-C-D는 A 다음에 가장 깊은 노드부터 깊이별로 나열한 순서로, 간선을 따라 이동한 경로가 아니다.

실행 결과는 5 2 3 0 1 3이다. 앞의 다섯 값은 재귀 호출마다 찍힌 n이고, 마지막 3은 main에서 찍은 반환값이다.
덧셈의 왼쪽 호출부터 평가된다고 보고 추적한다.
fun(5): 5 출력 → fun(2) + fun(3)
fun(2): 2 출력 → n < 3 이므로 1 반환
fun(3): 3 출력 → fun(0) + fun(1)
fun(0): 0 출력 → 1 반환
fun(1): 1 출력 → 1 반환
fun(3)은 1 + 1 = 2, fun(5)는 1 + 2 = 3을 반환한다.
5 1 2 2 0: fun(5)의 첫 호출은 n - 3 인 fun(2)이므로 두 번째 출력이 1일 수 없다.
5 2 3 1 0: fun(3)에서는 fun(0)이 먼저 호출되므로 0이 1보다 앞선다.
5 2 3 0 1: 재귀 출력만 있고 main이 찍는 k 값이 빠져 있다.
5 2 3 0 3 1: k는 맨 마지막에 출력되므로 3이 fun(1)의 출력보다 앞설 수 없다.

DMA 전송을 CPU가 관리한다는 설명이 틀렸다. 전송 과정을 관리하는 주체는 DMA 제어기다.
CPU는 전송 시작을 지시하고 완료 인터럽트를 받을 뿐, 전송 중에는 관여하지 않고 다른 작업을 수행한다. 이렇게 CPU 부담을 줄이는 것이 DMA의 목적이다.
채널 입출력: 입출력 전용 프로세서인 채널이 CPU의 계속적인 간섭 없이 장치와 기억장치 사이의 전송을 맡는다.
인터럽트: I/O장치는 작업 완료 같은 이벤트를 주로 인터럽트로 CPU에 알린다.
인터페이스 역할: I/O장치는 사람이나 외부 세계와 컴퓨터를 연결한다.
Memory-mapped I/O: 장치 레지스터를 메모리 주소 공간에 배치하므로 일반 메모리 접근 명령어로 제어한다.

올바른 후위 표기는 7 6 2 / + 2 / 9 4 * 3 / +이다.
연산자 우선순위와 왼쪽 결합 순서대로 묶은 뒤 연산자를 뒤로 옮긴다.
6 / 2 → 6 2 /
7 + 6 / 2 → 7 6 2 / +
( 7 + 6 / 2 ) / 2 → 7 6 2 / + 2 /
9 * 4 / 3 → 9 4 * 3 /
두 식을 더해 맨 끝에 +를 붙인다.
후위식 6 / 2 + 7 …: 연산자가 피연산자 사이에 있어 후위 표기가 아니다.
후위식 6 2 / 7 + 2 / 9 4 3 * / +: 뒷부분이 9 / (4 * 3)이 되어 원래 식과 다르다.
후위식 7 6 / 2 + …: 앞부분이 7 / 6 + 2 가 되어 원래 식과 다르다.
후위식 … 9 4 3 / + *: 뒷부분이 9 + 4 / 3 이 되고 이를 앞의 결과에 곱하게 되어 원래 식과 다르다.

이 회로는 선택 신호로 두 입력 중 하나를 골라 출력하는 2×1 멀티플렉서이다.
위쪽 AND 게이트에는 입력 $I_0$와 NOT을 거친 선택 신호가, 아래쪽 AND 게이트에는 입력 $I_1$과 선택 신호가 들어가고, 두 결과를 OR 게이트가 합친다.
$\mathrm{out}=\overline{\mathrm{sel}_0}\cdot I_0+\mathrm{sel}_0\cdot I_1$
따라서 선택 신호가 0이면 출력은 $I_0$, 1이면 출력은 $I_1$이 된다.
플립플롭은 출력이 입력으로 되돌아가는 귀환 경로로 상태를 저장하지만, 이 회로에는 귀환 경로가 없다.
덧셈기는 XOR 연산으로 합을 만들고 올림수도 출력하지만, 이 회로의 출력은 선택된 입력 하나뿐이다.
곱셈기는 입력 비트들의 부분곱을 더해 여러 비트의 결과를 내므로, 출력이 입력 하나와 같아지는 이 회로와 다르다.
감산기는 차와 빌림수를 출력하지만, 이 회로는 입력값을 그대로 전달할 뿐 산술 연산을 하지 않는다.

CPU용으로 컴파일된 프로그램이 그대로 GPGPU에서 실행된다는 설명이 틀렸다.
CPU와 GPU는 명령어 집합과 실행 구조가 달라, GPU에서 돌리려면 CUDA나 OpenCL 같은 전용 환경으로 별도 작성·컴파일해야 한다.
GPGPU의 정의: 그래픽 처리장치를 그래픽 외의 일반 연산에 활용하는 기술을 가리킨다.
다수의 단순 ALU: 많은 연산 유닛이 동시에 동작해 병렬 프로그램의 처리 속도가 높아진다.
OpenCL: 제조사에 종속되지 않는 개방형 표준이라 여러 제조사의 기기에서 실행할 수 있다.
병렬처리가 불가능한 프로그램: 순차적으로만 실행되므로 많은 연산 유닛을 활용하지 못해 성능 향상을 기대하기 어렵다.

옳은 설명은 ㄱ, ㄴ, ㄷ이고, ㄹ만 틀렸다.
데이터베이스의 네 가지 특성은 실시간 접근성, 계속적인 변화, 동시 공유, 내용에 의한 참조다. 데이터는 주소가 아니라 값(내용)으로 찾으므로 ㄹ을 뺀 조합만 남는다.
ㄱ(O): 비정형적인 질의에도 즉시 응답하는 실시간 접근성을 설명한다.
ㄴ(O): 삽입·삭제·갱신으로 데이터가 계속 변하며 최신 상태를 유지하는 특성이다.
ㄷ(O): 여러 사용자가 같은 데이터를 동시에 이용하는 동시 공유를 설명한다.
ㄹ(X): 레코드는 주소가 아니라 내용 값으로 참조한다.

CPU 레지스터 내용을 스택에 저장할 수 없다는 설명이 틀렸다. 레지스터 값을 스택에 저장하는 것은 일상적인 동작이다.
함수 호출이나 인터럽트 처리 때 레지스터 값을 스택에 PUSH 해 두었다가 끝나면 POP 으로 복원한다.
스택포인터 레지스터: CPU에는 스택의 꼭대기 주소를 가리키는 레지스터가 있다.
LIFO: 나중에 넣은 데이터를 먼저 꺼내는 구조다.
버퍼 오버플로우 공격: 스택에 저장된 복귀 주소를 덮어써 실행 흐름을 바꾸는 데 이용된다.
문맥교환: 실행 상태를 저장하고 복원할 때 프로세스의 스택이 함께 쓰인다.

속성 값을 서브속성으로 세분화할 수 있다는 설명이 틀렸다. 릴레이션의 속성 값은 더 나눌 수 없는 값이어야 한다.
이 성질을 원자성이라 하며, 제1정규형의 조건이기도 하다.
스키마와 인스턴스: 스키마는 구조 정의라 잘 바뀌지 않고, 인스턴스는 데이터 변경에 따라 계속 달라진다.
튜플의 유일성: 릴레이션은 튜플의 집합이므로 똑같은 튜플이 중복될 수 없다.
속성의 무순서성: 속성은 이름으로 구분하므로 순서에 의미가 없다.
속성 이름과 값: 한 릴레이션 안에서 속성 이름은 유일해야 하지만 여러 튜플의 속성 값은 같을 수 있다.

서로 다른 서브넷으로 나누는 마스크는 255.255.255.192이다.
마지막 옥텟을 2진수로 쓰면 1은 00000001, 65는 01000001이고, 왼쪽에서 두 번째 비트가 다르다. 마스크가 이 비트까지 포함해야 네트워크 주소가 달라진다.
A: 1 AND 192 = 0 → 192.168.0.0
B: 65 AND 192 = 64 → 192.168.0.64
0.0.0.0: 네트워크 부분이 없어 모든 주소가 같은 네트워크 0.0.0.0이 된다.
255.255.255.0: 앞 세 옥텟이 같으므로 둘 다 192.168.0.0이다.
255.255.255.128: 마지막 옥텟의 첫 비트가 둘 다 0이므로 둘 다 192.168.0.0이다.
255.255.128.0: 더 짧은 마스크라서 둘 다 192.168.0.0이다.

스래싱은 페이지 부재가 너무 잦아 실행보다 페이지 교체에 더 많은 시간을 쓰는 현상이다.
다중 프로그래밍 정도가 지나치게 높아 프로세스별 프레임이 부족할 때 발생하며, 이때 CPU 이용률이 급격히 떨어진다.
서로 상대의 작업 종료를 기다려 아무것도 완료되지 못하는 현상: 교착상태(deadlock)다.
짧은 버스트 우선으로 긴 프로세스가 계속 지연되는 현상: 기아(starvation)다.
긴 프로세스가 CPU를 양보할 때까지 나머지가 모두 기다리는 현상: 호위 효과(convoy effect)다.
장치나 예외 상황을 CPU에 알려 처리하게 하는 것: 인터럽트(interrupt)다.

옳은 설명은 ㄱ, ㄴ, ㄹ이고, ㄷ과 ㅁ은 틀렸다.
쇼어(Shor) 알고리즘은 소인수분해와 이산로그를 다항시간에 풀지만, 이것이 모든 NP 문제를 다항시간에 푼다는 뜻은 아니다. ㄷ과 ㅁ을 빼면 조합은 하나만 남는다.
ㄱ(O): 양자컴퓨팅은 중첩과 얽힘 현상을 계산에 이용한다.
ㄴ(O): 큐비트는 0과 1의 중첩 상태를 가질 수 있는 기본 단위다.
ㄷ(X): 얽힘을 이용하는 방식의 QKD 프로토콜(E91 등)이 있으므로 이용하지 않는다고 단정할 수 없다.
ㄹ(O): 쇼어 알고리즘으로 이산로그 문제를 다항시간에 풀 수 있다.
ㅁ(X): 소인수분해가 다항시간에 풀린다고 해서 NP 문제 전체가 다항시간에 풀리는 것은 아니다.

OFDM을 IEEE 802.11b에 사용할 수 있다는 설명이 틀렸다.
802.11b는 DSSS 계열의 CCK 변조를 쓰며 11Mbps가 그 규격의 최고 속도다. OFDM은 802.11a/g 이후 규격에서 도입되었다.
MIMO: 안테나 수가 늘면 동시에 보내는 공간 스트림이 늘어 전송 속도가 높아진다.
LTE와의 비교: 802.11n/ac 같은 고속 규격은 LTE보다 빠른 전송 속도를 낼 수 있다.
채널 대역폭: 802.11n 이후에는 채널을 묶어 대역폭을 바꿔 쓸 수 있다.
다수의 채널: 서로 겹치지 않는 채널을 쓰면 인접한 두 쌍의 기기가 간섭 없이 동시에 통신할 수 있다.

옳지 않은 설명은 ㄱ, ㄴ이다.
C++은 Java와 달리 클래스의 다중 상속을 지원하고, 한 클래스 안에서 매개변수가 다른 같은 이름의 함수를 정의하는 오버로딩도 허용한다. 틀린 지문이 둘뿐이므로 조합도 하나로 정해진다.
ㄱ(X): C++은 다중 상속이 가능하다.
ㄴ(X): 오버로딩은 바로 한 클래스 내에서 같은 이름의 함수를 여럿 정의하는 기능이다.
ㄷ(O): 클래스는 데이터와 함수를 묶어 캡슐화와 추상화를 지원한다.
ㄹ(O): C++은 상속과 다형성을 지원한다.
ㅁ(O): 가상 함수(virtual)를 통해 동적 바인딩으로 다형성을 구현한다.

calc 함수의 실행 시간은 $O(n^2)$이다.
한 번의 호출에서 for 문이 n번 돌고, 이어서 calc(n - 1)을 호출한다.
$T(n)=T(n-1)+n$
$T(n)=n+(n-1)+\cdots+1=\dfrac{n(n+1)}{2}$
최고차항이 $n^2$이므로 점근 표기는 $O(n^2)$이다.
$O(\log_2 n)$: 호출마다 n이 절반이 아니라 1씩 줄어 호출 깊이만 해도 n이다.
$O(n\log_2 n)$: 호출 깊이가 $\log_2 n$일 때 나오는 형태로, 이 함수의 깊이는 n이다.
$O(n)$: 반복문 없이 재귀 호출만 있을 때의 값으로, 호출마다 도는 for 문의 비용이 빠져 있다.
$O(n^3)$: 삼중 구조일 때의 값으로, 이 함수는 재귀 하나와 단일 for 문뿐이다.

LRU를 적용하면 페이지 부재는 총 10회 발생한다.
가장 오래 쓰이지 않은 페이지를 교체한다. 괄호는 오래된 순의 프레임 상태다.
2 부재 (2)
3 부재 (2, 3)
4 부재 (2, 3, 4)
2 적중 (3, 4, 2)
1 부재 (4, 2, 1)
5 부재 (2, 1, 5)
6 부재 (1, 5, 6)
2 부재 (5, 6, 2)
1 부재 (6, 2, 1)
2 적중 (6, 1, 2)
3 부재 (1, 2, 3)
5 부재 (2, 3, 5)
3 적중 (2, 5, 3)
전체 참조 13회 중 적중이 3회이므로 부재는 13 - 3 = 10회다.
부재 8회: 아홉 번째 참조까지의 누계이고, 뒤의 참조 3과 5에서 부재가 더 발생한다.
부재 9회: 열한 번째 참조까지의 누계이고, 뒤의 참조 5에서 부재가 한 번 더 발생한다.
부재 11회: 적중이 2회여야 나오는 값인데 실제 적중은 3회다.
부재 12회: 적중이 1회여야 나오는 값인데 실제 적중은 3회다.

삭제 후의 최대힙은 루트가 16, 그 자식이 14와 7이고 7의 자식이 2와 3인 트리이다.
최대힙의 삭제는 최댓값인 루트에서 일어나며, 마지막 노드를 루트로 옮긴 뒤 자식 중 더 큰 값과 교환하며 내려보낸다.
루트 20을 삭제하고 마지막 노드 7을 루트로 옮긴다.
7의 자식 14, 16 중 더 큰 16과 교환한다.
7의 새 자식 2, 3은 모두 7보다 작으므로 멈춘다.
루트 20이 남고 10이 사라진 트리는 삭제가 루트가 아닌 말단에서 일어난 형태이다.
루트 20이 남고 7이 사라진 트리도 말단 노드를 지운 형태로, 최대힙의 삭제가 아니다.
루트가 14이고 오른쪽 자식이 16인 트리는 부모가 자식보다 작아 최대힙 조건을 어긴다.
루트 16의 자식이 14와 12인 트리는 힙 조건은 만족하지만, 7이 내려간 경로에 없는 12가 위치를 옮겼으므로 이 삭제 연산의 결과가 아니다.