2018 카카오 블라인드 필기시험 정답 및 해설

2018 카카오 블라인드 필기시험 정답 및 해설

지필평가..

지필 평가는 카카오를 포함하여 NHN, (매일경제. NHN엔터 "코딩 잘 못해도 기초 탄탄하면 채용"), SSG.COM S/W Basic & L/M Test 그리고 은행권 등등 흔한 단계 중 하나입니다. 방대한 CS 지식을 다시 공부하는 것은 여간 어려운 일이 아닙니다. 공개 문제 중 하나인 카카오 2018 블라인드 문제 및 해설을 첨부하였습니다. 문제 원본에서 전체 문제를 확인할 수 있습니다.

1~10번 안내

Q1에서 Q10 까지는 컴퓨팅 및 컴퓨터 과학, 인터넷 등의 기본적인 개념에 대한 영어 위키백과의 설명이다. 각 빈칸을 채워 넣으시오. (문항당 정답은 한 개이며, 단복 수형의 구분 무관 및 영문이 아닌 한국어로 번역된 명칭을 적어도 무방함.)

1번

In computer science, a ( ) of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. The implementation of ( ) and processes differs between operating systems, but in most cases a ( ) is a component of a process. Multiple ( ) can exist within one process, executing concurrently and sharing resources such as memory, while different processes do not share these resources. [3 점]

답. 쓰레드(Thread)
해설. Multiple ( ) can exist within one process. 에서 쓰레드라고 확실하게 생각할 수 있습니다.

2번

In multitasking computer operating systems, a ( ) is a computer program that runs as a background process, rather than being under the direct control of an interactive user. Traditionally, the process names of a ( ) end with the letter d, for clarification that the process is, in fact, a ( ), and for differentiation between a ( ) and a normal computer program. For example, syslogd is the ( ) that implements the system logging facility, and sshd is a ( ) that serves incoming SSH connections. [5 점]

답. 데몬(Daemon)
해설. the process names of a ( ) end with the letter d. 라는 표현을 보고 D로 시작한다는 힌트를 얻을 수 있습니다. 첫 문장 a ( ) is a computer program that runs as a background process을 보면 데몬이라고 확신할 수 있습니다.

3번

In computer science, a ( ) is a type of resource leak that occurs when a computer program incorrectly manages memory allocations in such a way that memory which is no longer needed is not released. [3 점]

답. Memory leak(메모리 누수)

해설. 문제에 답이 쓰여있습니다.. 포인터가 여전히 해제된 메모리 영역을 가리키고 있는 댕글링 포인터(Dangling Pointer)에 대해서도 추가적으로 알아두세요.

4번

In computing, ( ) is a computer program that takes one or more object files generated by a compiler and combines them into a single executable file, library file, or another 'object' file. A simpler version that writes its output directly to memory is called the loader, though loading is typically considered a separate process. [3 점]

답. 링커(Linker)

Source. https://jsommers.github.io/cbook/programstructure

해설. 컴파일러로부터 생성된 오브젝트 파일에 라이브러리 파일, 다른 오브젝트 파일을 합친다(combines) 표현에서 링커라고 알 수 있습니다.

5번

The ( ) is a hierarchical decentralized naming system for computers, services, or other resources connected to the Internet or a private network. It associates various information with domain names assigned to each of the participating entities. Most prominently, it translates more readily memorized domain names to the numerical IP addresses needed for locating and identifying computer services and devices with the underlying network protocols. By providing a worldwide, distributed directory service, the ( ) is an essential component of the functionality on the Internet, that has been in use since 1985. [3 점]

답. 도메인 네임 시스템(DNS, Domain Name System)
해설. 처음 읽으면 긴가민가 할 수 있는데 it translates more readily memorized domain names to the numerical IP addresses ~~ 부분을 보고 DNS라고 확신할 수 있습니다.

6번

( ) uses a simple connectionless communication model with a minimum of protocol mechanism. ( ) provides checksums for data integrity, and port numbers for addressing different functions at the source and destination of the datagram. It has no handshaking dialogues, and thus exposes the user's program to any unreliability of the underlying network; There is no g uarantee of delivery, ordering, or duplicate protection. If errorcorrection facilities are needed at the network interface level, an application may use the Transmission Control Protocol (TCP) or Stream Control Transmission Protocol (SCTP) which are designed for this purpose. [5 점]

답. UDP

해설. connectionless, no handshaking dialogues, unreliability, no guarantee of delivery 이러한 키워드가 UDP에 대한 설명입니다. 또한 마지막에 반대되는 성격의 TCP가 나오는 것으로 UDP라고 확신할 수 있습니다.

7번

( ) is a set of Web development techniques using many Web technologies on the client side to create asynchronous Web applications. With ( ), Web applications can send data to and retrieve from a server asynchronously (in the background) without interfering with the display and behavior of the existing page. By decoupling the data interchange layer from the presentation layer, ( ) allows for Web pages, and by extension Web applications, to change content dynamically without the need to reload the entire page. In practice, modern implementations commonly substitute JSON for XML due to the advantages of being native to JavaScript. [5 점]

답. AJAX

해설. 첫 줄에 클라이언트에서 비동기적 기술, 그리고 다시 불러오지 않고 동적으로 변화된 점을 보여준다는 점에서 Ajax라고 할 수 있습니다.

8번

A ( ) in the C programming language (and many derivatives) is a composite data type declaration that defines a physically grouped list of variables to be placed under one name in a block of memory, allowing the different variables to be accessed via a single pointer, or the ( ) declared name which returns the same address. In the C++ language, a ( ) is identical to a C++ class but a difference in the default visibility exists: class members are by default private, whereas ( ) members are by default public. [5 점]

답. 구조체(struct)

해설. 첫째 줄에 C 문법에서 변수들을 그룹으로 묶어서 하나의 메모리 블록에 저장되는 특징. C++의 class와 다르게 public으로 접근 가능한다는 특징은 struct입니다.

9번

In object-oriented programming, ( ) is when an object or class is based on another object (prototypal ( )) or class (class-based ( )), using the same implementation. ( ) in most classbased object oriented languages is a mechanism in which one object acquires all the properties and behaviors of parent object. [5 점]

답. 상속(Inheritance)

해설. 처음에 based on another object 표현. 마지막 줄, 부모 오브젝트의 모든 properties와 behavior를 얻을 수 있다는 점에서 답은 상속입니다.

10번

A ( ) symbolizes a unit of work performed within a database management system (or similar system) against a database, and treated in a coherent and reliable way independent of other ( ). A ( ) generally represents any change in a database. ( ) in a database environment have two main purposes: [5 점]

1. To provide reliable units of work that allow correct recovery from failures and keep a database consistent even in cases of system failure, when execution stops (completely or partially) and many
   operations upon a database remain uncompleted, with unclear status.
2. To provide isolation between programs accessing a database concurrently. If this isolation is not provided, the programs' outcomes are possibly erroneous.

답. Transaction(트렌잭션)

해설. A ( ) symbolizes a unit of work performed within a database management system.을 보고 트렌잭션이라고 알 수 있습니다. 다음에 나오는 긴 내용은 트랜젝션의 ACID(원자성, 일관성, 고립성, 지속성)에 대한 설명입니다. 해당 내용이 기억이 나지 않으시면 데이터베이스 트랜젝션 ACID란? 글을 확인해 주세요.

11번

아래는 TCP 의 커넥션 종료 과정을 도식화한 그림이다. 빈 칸의 상태에 알맞는 번호를 각각 기입하시오. [10 점]

1) CLOSE_WAIT
2) TIME_WAIT
3) FIN_WAIT_1
4) FIN_WAIT_2

The connection termination phase uses a four-way handshake, with each side of the connection terminating independently. When an endpoint wishes to stop its half of the connection, it transmits a FIN packet, which the other end acknowledges with an ACK. Therefore, a typical tear-down requires a pair of FIN and ACK segments from each TCP endpoint. After the side that sent the first FIN has responded with the final ACK, it waits for a timeout before finally closing the connection, during which time the local port is unavailable for new connections; this prevents confusion due to delayed packets being delivered during subsequent connections.

답. 위에서 아래로 순서대로

3) FIN_WAIT_1
1) CLOSE_WAIT
4) FIN_WAIT_2
2) TIME_WAIT

위의 영문 지문이 크게 도움 안 되는 문제입니다.. 관련 내용을 알고 있지 않으면 틀릴 수밖에 없습니다.

12번

다음은 Model–view–controller (MVC) 소프트웨어 디자인 패턴에 관한 설명 중 일부이다. 구성요소에 대한 설명 중 빈 칸에 알맞는 번호를 각각 기입하시오. [5 점]

1) Model
2) View
3) Controller

• The ( ) accepts input and converts it to commands.
• A ( ) can be any output representation of information, such as a chart or a diagram.
• The ( ) is the central component of the pattern. It expresses the application's behavior in terms of the problem domain, independent of the user interface. It directly manages the data, logic and rules of the application.

정답 및 해설

Source. openclassrooms

• Controller
  • Model과 view를 연결하는 역할을 합니다.
• View
  • 화면에 무엇인가를 보여주기 위한 역할입니다.
• Model
  • 어플리케이션이 무엇을 할지 결정합니다.
  • 처리되는 알고리즘, DB 데이터 등등이 해당됩니다.

13번

아래 코드의 시간 복잡도는 어떻게 되는가? [5 점]

int f(int n) {
 if (n <= 1) {
 return 1;
 }
 return f(n - 1) + f(n - 1);
}

1. Ο(1)
2. Ο(𝑛)
3. Ο(𝑛 log 𝑛)
4. Ο(𝑛^2)
5. Ο(2^𝑛)

답. 5. Ο(2^𝑛)

해설.

알고리즘 수업을 들으면 시간 복잡도를 계산하는 문제에서 가장 기본 문제로 나오는 코드입니다. 위와 같이 재귀 트리(Recursion Tree)를 풀면 Ο(2^𝑛)으로 증가하는 것을 알 수 있습니다.

14번

아래 코드의 시간 복잡도는 어떻게 되는가? [5 점]

int f(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
    for (int j = 0; j < n / 2; j++) {
    sum *= j;
    }
 }

 return sum;
}

1. Ο(1)
2. Ο(𝑛)
3. Ο(𝑛 log 𝑛)
4. Ο(𝑛^2)
5. Ο(2^𝑛)

답. 4. Ο(𝑛^2)

해설. n에 대해서 2중 for문이기 때문에 Ο(𝑛^2)입니다.

15번

아래는 Queue 로 구현한 Stack 클래스의 자바 코드이다.

public class Stack {
    private Queue Q = new Queue();

    public E pop() {
        int k = 1;
        while(k++ < Q.size())
            Q.enqueue(Q.dequeue());
            return Q.dequeue();
    }

    public void push(E o){
        Q.enqueue(o);
    }
}

Queue 의 enqueue(o)와 dequeue()의 시간복잡도가 Ο(1) 일때 Stack 클래스의 push(o)와 pop() 각각의 시간 복잡도를 기입하시오. [7 점]

• push(o): 𝚶( )
• pop(): 𝚶( )

답

• push(o): 𝚶(1)
  • push 안의 메서드인 enqueue는 𝚶(1)로 수행됩니다.
• pop(): 𝚶(n)
  • while이 Queue 크기만큼 dequeue, enqueue를 수행하기 때문입니다.

16번

중복된 원소가 없는 서로 길이가 다른 숫자 리스트 A, B 가 있다. 두 리스트 내에 공통으로 포함된 원소를 출력하고자 한다. 두 리스트 중 한 개를 정렬하고, 다른 리스트를 순회하면서 이진 검색 Binary Search 으로 포함 여부를 체크한다고 할때 어떤 리스트를 정렬하는게 더 빠를지 고르시오. 단, len(A) < len(B) 이며 정렬은 병합 정렬 Merge Sort 을 사용하여 Ο(𝑛 log 𝑛)의 시간 복잡도로 진행한다. [5 점]

1. 길이가 짧은 A
2. 길이가 긴 B
3. 상관 없음

답. (1) 길이가 짧은 A

해설.
len(A)=a, len(B)=b라고 정의한다면 다음과 같이 각각의 경우 시간 복잡도를 구할 수 있습니다.

[A를 정렬하는 경우]

a를 정렬하면 alog(a) 시간이 걸립니다. 각각의 b에 대해서 log(a) (∵ a에 대해서 이진검색을 하므로)의 탐색을 합니다. 따라서 alog(a) + blog(a) = (a+b)log(a)

[B를 정렬하는 경우]

b를 정렬하면 blog(b) 시간이 걸립니다. 각각의 a에 대해서 log(b) (∵ b에 대해서 이진검색을 하므로)의 시간이 걸립니다. 따라서 blog(b) + alog(b) = (a+b)log(b)

(a+b)loga < (a+b)logb 입니다. 여기서 a < b 이므로 답은 1번이 됩니다.

17번

웹 브라우저의 이전페이지로 돌아가기와 에디터의 되돌리기 Undo 기능을 구현하기에 적합한 자료구조는? [3 점]

1. Hash
2. Stack
3. Queue
4. Tree
5. Graph

답. 2(Stack)
해설. 웹 페이지의 이전페이지로 돌아가는 것, 에디터에서 되돌리는 기능의 공통점은 가장 최근에 실행한 것으로 되돌아가야 하는 것입니다. LIFO 자료구조인 스택을 사용해야 합니다.

18번

DB 의 인덱스 Index 는 원하는 레코드 Record 에 빠르게 접근 할 수 있게 해준다. 문자열과 숫자 컬럼에 대한 인덱스를 구현할 때 사용할 수 있는 자료구조를 모두 고르시오. [5 점]

1. Hash
2. Stack
3. Queue
4. Tree
5. Graph

답. 1(Hash), 4(Tree)

해설. DB는 특징이 하나의 테이블에 정렬되지 않은 자료가 선형으로 저장되어 있습니다. 선형 자료를 빠르게 탐색하기 위해서는 해시, 트리, 정렬되어 있다면 이분탐색이 가능합니다. 스택 은 중간의 자료를 탐색하는데 최악의 경우 시간복잡도는 O(n)이기에 부적합합니다. 그래프는 cycle 관계의 데이터를 관리하는데 유용합니다.

19번

새로 가입하는 사용자에게 메일을 보내야 하는데, 실제 가입까지 처리는 10 𝑚𝑠 밖에 걸리지 않지만, 메일을 보내는 시간은 1000 𝑚𝑠 가 소요된다. 이런 경우에 가입자에게 메일을 순차적으로 발송하는 시스템을 구현하기 위한 자료구조로 적합한 것은? [3 점]

1. Hash
2. Stack
3. Queue
4. Tree
5. Graph

답. 3(Queue)

해설. 가입한 사람 순으로 발송하는 메일 시스템을 구현해야 합니다. 문제는 가입 시간보다 발송하는데 오래 걸립니다. 그렇기 때문에 버퍼에 저장을 해야 하며, 먼저 들어온 데이터가 먼저 처리되는 FIFO 자료구조인 큐를 사용해야 합니다.

20번

트리의 순회 방법 Tree traversal 에는 현재 노드를 언제 순회하느냐에 따라 전위 순회 Pre-order, 중위 순회 In-order, 후위 순회 Post-order 가 있다.

• 전위 순회는 현재 노드를 방문 후 왼쪽 서브 트리, 오른쪽 서브 트리 순으로 전위 순회를 한다.
• 중위 순회는 왼쪽 서브 트리를 중위 순회한 후 현재 노드를 방문하고, 마지막으로 오른쪽 서브 트리를 중위 순회한다.
• 후위 순회는 왼쪽 서브 트리, 오른쪽 서브 트리 순으로 후위 순회한 후, 마지막으로 현재 노드를 방문한다.

예를 들어, 위와 같은 이진트리가 주어졌을 때 각각의 순회 결과는 다음과 같다.

전위 순회 : 1 2 4 5 3

• 중위 순회 : 4 2 5 1 3
• 후위 순회 : 4 5 2 3 1

이진 탐색 트리의 전위 순회, 중위 순회 결과가 다음과 같을 때,

• 전위 순회: F, B, A, D, C, E, G, I, H
• 중위 순회: A, B, C, D, E, F, G, H, I

후위 순회 결과를 나열하시오. [10 점]

정답: A, ( ), E, ( ), ( ), H, ( ), G, ( )

답

A, (C), E, (D), (B), H, (I), G, (F)

해설

친절하게 예시를 주었기 때문에 이에 맞추어 직접 해보면 됩니다.