# 카이스트 전산학부 대학원 입시 기출 문제 정리

2018.08.21 (미완성)

문제 출처 https://cs.kaist.ac.kr/userfiles/file/exam.pdf

목차

# Programming Language / Compiler

1. 자바에서 public, protected, private 키워드가 있는데 아무것도 안 쓸 경우 default로 적용되는 범위는?

package-private: 오로지 해당 패키지에서만 사용할 수 있다.

2. Static typing과 Dynamic typing의 차이점은? C++/JAVA는 어떤 typing을 사용하는 가?

Static typing: 변수의 타입을 컴파일 타임에 알 수 있다.
Dynamic typing: 타입이 런타임에서의 값과 결부(associated) 된다.
C++/JAVA는 컴파일 타임에 타입이 결정되어 기계어 혹은 바이트 코드로 컴파일 되기 때문에 static typed 언어이다.

3. C++에서 서로 다른 타입의 오브젝트를 가리키는 포인터를 사용할 수 있나?

c++를 많이 안해봐서 잘 모르겠다.

4. 전역 변수 사용의 장단점은?

시스템 프로그래밍 관점에서 지역변수(local variable)는 해당 함수를 벗어나게 되면 다른 함수 실행에 의해 overwrite되게 된다. 즉, 더 이상 값이나 주소를 사용할 수 없다는 얘기이다. 여기서 전역 변수를 이용하게 되면, 함수를 벗어나도 주소를 유지할 수 있기 때문에 여러 함수에서 사용하는 data structure를 전역변수로 구현하기 좋을 것이다.
그런데 동시에 여러 함수가 해당 주소를 접근 할 수 있기 때문에 side effect가 일어날 가능성이 있다.

5. 프로그램 실행 전 컴파일 시에 타입과 같은 프로그램의 정적 성질을 검사하는 프로그램밍 언어와 그렇지 않은 프로그래밍 언어를 비교하시오.

(컴파일 언어와 인터프리팅 언어를 비교하는 것인듯) 전자는 작성한 코드를 어셈블리어로 변환하기 위해 컴파일 타임에 문법과 타입을 체크하고 런타임에 프로그램을 실행(evaluate)한다.
후자는 작성한 코드를 컴파일 타임없이 일단 파싱해서 코드의 문법이 잘 맞는 지 확인한 뒤에 바로 실행해서 타입이 잘 맞지 않으면 에러를 뱉게 된다.
전자는 컴파일 타임에 syntax와 type을 체크하기 때문에 런타임에서 이를 걱정할 필요가 없고 짧은 런타임 시간을 갖는다. 대신 간단한 프로그램이라도 수정 시마다 컴파일이 필요하기 때문에 빠른 수정과 테스트가 이루어지는 상황에서는 후자가 효율적일 수 있다.

6. 파라미터 패싱 방식에는 eager evaluation 방식과 lazy evaluation 방식이 있다. 두 방식의 차이점을 비교 설명하세요. call-by-value와 call-by-name 파라미터 방식은 각각 어느 방식에 속하는 지 구분하세요.

eager/lazy evaluation들이 파라미터 패싱방식이었나요????

7. 언어를 분류하는 데 있어서는 해당 언어를 생성하는 Production 룰의 형태에 가해지는 제약 사항을 가지고 분류하는 것이 일반적이다. Context Sensitive Language, Context Free Language, Regular Language를 생성하는 데 사용되는 Production 룰의 형태에 대해서 그 차이점을 비교 설명하세요.

이산구조(discrete mathematics)에서 배웠던 것 같기도 한데, 잘 모르겠네요..

8. Let L be a regular language. Prove that R(L), strings in L reversed, is also a regular language.

마! 문제 왜캐 어렵냐!

# Architecture

1. 캐시가 필요한 이유는? Cache hit ratio에 대해 설명하시오.

캐시를 통해 평균적인 빠른 메모리 access가 가능하기 때문이다. 내가 access하는 메모리 주소가 SRAM에 존재한다면 hit이고 아니라면 miss라고 한다. 전체 access중 hit의 비율을 cache hit ratio라고 한다.

2. 메모리 접근하는 데 x 사이클이 걸리고 캐시에 접근하는 데 y 사이클이 걸리면 캐시 hit rate가 h%일 때 effective access time은?

miss의 경우도 일단 캐시에 접근을 하기 때문에 캐시와 메모리를 접근하는 시간 모두가 필요하다. 따라서 $0.01*h*y + (1 - 0.01*h)*(x+y)$ 사이클의 시간이 필요하다.

3. 페이지 폴트는 언제 발생하는 가? 페이지 폴트 비율과 cache miss 비율 중 큰 것은?

페이지 폴트는 프로세스가 접근한 페이지가 물리적 메모리(physical memory)에 존재하지 않을 때 발생한다. 보통 해당 페이지는 디스크에 존재하게 된다. 접근하려는 페이지가 물리적 메모리에 없다는 것은 캐싱도 되지 않았다는 이야기이기 때문에 cache miss 비율이 더 크다.
Memory access(when all miss): cache memory -> TLB -> page table -> physical memory -> disk

4. 캐시 메모리와 메인 메모리의 주소 지정 방식의 차이점이 무엇인가?

가물가물

5. 캐시를 구성하는 컴포넌트에 무엇이 있는가? 각 컴포넌트는 어떤 역할을 하는가?

valid bit, dirty bit, tag bits, offset bits

6. 캐시에서 태그 매칭이 무엇이고 왜 필요한가?

7. 캐시에서 블록(라인) 크기를 크게 했을 때와 작게 했을 때 어떤 장단점이 있을까?

block 단위로 캐싱을 하는 이유는 Spatial locality에 있다. 따라서 block을 키우면 spatial locality는 높아지겠지만, 캐시된 block의 갯수가 낮아지므로 temporal locality는 낮아질 수 있다. 반대로 block을 줄이면 spatial locality는 낮아지고 temporal locality는 높아지게 될 것이다.

8. Direct-mapped cache와 set-associative cache의 장단점은 무엇인가?

9. Write-through cache와 write-back cache에 대해서 설명해 보시오.

10. Write-through cache는 write buffer를 보통 사용하는 데 이의 역할은 무엇인가?

11. 코어가 10개 있는 cpu에서 프로세스 하나를 균등하게 처리하면 이상적인 경우, 시간이 얼마나 줄어드는가? 그런데 프로세스에서 분할되지 않는 20%의 작업이 이써다고 하면, 시간이 얼마나 줄어드는가? 이제 코어가 수백개, 혹은 무한개 있다고 하면 얼마나 줄어드는가?

12. cache에서 사용하는 replacement policy에는 어떤 것이 있는가?

LRU(Least Recently Used), FIFO(First In, First Out)

# OS

1. Kernel을 필요에 의해 어느 정도 수정했다고 하자. 이 kernel이 제대로 작동하는 지를 알기 위해서 어떤 test를 해야겠나?

나라면 기본적인 스케줄링, virtual memory, file system을 테스트하고 바로 부하테스트를 할 것 같다. 가령 쓰레드를 최대한 많이 생성한다거나 memory를 최대한 많이 사용한다던가 file를 최대한 많이 생성한다거나.

2. Sequential program과 multithread program에서 error detection에 대한 차이점에는 어떤 것이 있나?

multithread program에서는 deadlock, starvation이 있을 것이고, memory deallocation을 잘 했다고 생각해도 실행순서 문제로 memory deallocation이 제대로 되지 않는 상황이 생길 수 있다.

3. 어떤 C program으로 작성되어 수행중인 process가 있다고 가정하자. C언어에서는 직접적으로 주소를 변수에게 지정해 줄 수 있다. 만약 주소 1,2,3,4에 변수를 잡아서 어떤 일을 수행하는 process라고 하자. 이 process를 한 시스템에 동시에 두 번 수행시켰다. 그랬을 때 한 프로세스가 1,2,3,4 주소에 있는 변수를 바꿧을 때 다른 프로세스의 변수들에도 영향을 끼치는가?

4. Thread와 process의 차이는 무엇인가?

5. IPC가 무엇잇가?

# Database

1. Data inconsistency가 무엇인가?

데이터 integrity를 보장하지 못하는 요소들을 data inconsistency라고 한다. Normalization을 충분히 하지 않고 DB model을 설계할 경우 발생할 수 있다.

2. Data normalization이 무엇인가? 왜 필요한가?

Data inconsistency를 피하기 위해서 DB model를 설계할 때 필요한 조치이다. First normal form은 하나의 컬럼이 multi value를 가지면 이를 별도의 테이블로 분리한 경우이다. Second normal form은 First normal form을 만족하면서 모든 non-candidate key들이 모든 candidate key에 functional dependent할 때이다.

3. Inner Join과 Outer Join의 차이점은? Outer Join은 언제 사용하는가?

Inter Join은 join 조건에 만족하는 row들만 결과 table에 포함하지만 outer join은 join조건에 만족하지 않는 row들도 포함시킨다. 예를 들어 게시물 목록을 모두 가지고 오고 싶은 데 댓글이 달려있는 게시물이라면 댓글까지 가지고 오고 싶을 때 outer join을 사용할 수 있다.

4. DB와 file의 차이점은?

Traditional한 file system에서는 각 file의 data는 특정 application들에 dependent하지만 DB에서는 독립적으로 data들이 관리될 수 있다. file system에서는 data에 접근하기 위해 application에서 직접 system call을 통해 접근하게 되지만, DB에서는 DBMS를 통해서 쿼리를 통해 data에 접근할 수 있다.

5. Data independence란?

Data와 application 사이의 abstraction을 통해 application이 수정되어도 data에 영향을 미치지 않는 특성이다.

# Network

1. TCP와 같이 protocol을 reliable하게 설계하려면 무엇이 필요한가?

delivery에 실패했다면 user에게 알려야 한다.

2. Flow control이란 무엇인가? Congestion control과 flow control의 차이점은?

Flow control은 데이터 송신자와 수신자의 데이터 처리 속도 차이를 해결하기 위한 기법이다. 수신자의 데이터 처리 속도가 송신자보다 느리면 데이터의 손실이 발생할 수 있기 때문에 불필요한 데이터의 전송과 응답이 발생하게 된다. 따라서 수신자의 데이터 처리 속도에 따라 전송량을 조절해야 한다.

3. OSI 7계층에 대해 설명하시오.

Physical layer, data link layer, network layer, transport layer, session layer, presentation layer, application layer.

4. Transport, network, link 계층이 모두 연결에 관한 것인데, 무엇이 차이가 나나요?

5. Network에서 checksum을 위해 사용하는 hash function과 security에서 data integrity를 위해 사용하는 hash function이 서로 interchangable해요?

동일한 input에 대해서는 동일한 hash값을 뱉으면 되기 때문에 interchangable하다.

6. TCP와 UDP의 차이점은?

TCP는 reliable하고 패킷을 순서대로 전달하는 반면, UDP는 unreliable하고 패킹을 순서대로 전달하지 않는다.

7. Congestion이 발생했다는 것을 어떻게 할 수 있는가?

8. 3-way handshaking

end간에 연결이 잘 되었는 지 확인하는 과정이다. client가 SYN bit을 server에게 넘기면 서버는 SYN bit와 함께 ACK bit를 client에게 넘긴다. 이를 받은 client는 server가 연결 준비 되었음을 확인하고 server에게 ACK bit을 보냄으로써 client가 메세지를 보낼 것이라는 것을 알린다.

9. CSMA/CD란?

10. MAC address란? IP address가 MAC address에 비해 갖는 장점은?

# AI/ML

1. Show, using a proof or an example, that if $P(A|B,C) = P(A|C)$, then $P(A,B|C) = P(A|C)P(B|C)$.

$P(A,B|C) = \frac{P(A,B,C)}{P(C)} = \frac{P(A|B,C)P(B,C)}{P(C)} = P(A|C)P(B|C)$

2. An eigenvector of a square matrix A is a non-zero vector v that, when multiplied by A,, yields the original vector multiplied by the corresponding eigenvalue $\lambda$. What is the eigenvector of $\begin{bmatrix} 0 & 1 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}$ corresponding to the eigenvalue 3?

$3v = Av$

$\begin{bmatrix} 3 & -1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}v = 0$

$\begin{bmatrix} 3 & -1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} = 0$

$v = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}$ for eigenvalue 3.

# Algorithm

1. Sorting algorithm들에는 어떤 것들이 있는 가? Insertion sort, heap sort, selection sort, quick sort 중 optimal한 것과 optimal하지 않은 알고리즘은? 그 이유는?

2. 그래프의 정의는? 트리의 정의는? 트리와 그래프의 관계는?

그래프는 노드들과 노드들 간의 연결(엣지)로 정의되는 data structure이다. 트리는 cycle이 없는 그래프이다.

3. Topological Sorting을 설명하시오.

4. Partially ordered set이란?

5. NP complete의 정의는?

NP이면서 NP-hard인 문제이다. NP problem은 답이 yes가 존재할 때 이를 증명하는 데 다항시간이 걸리는 문제이다. NP-hard problem은 모든 NP problem이 다항시간 내에 환원될 수 있는 문제들이다.

6. Dynamic programming이란?

7. Priority queue란? Heap 이란?

priority queue는 array나 linked list로 구현할 수 있지만 보통 heap으로 구현한다. priority를 heap자료구조로 정렬하여 priority에 따라 queue에서 pop하는 element의 순서가 다른 queue이다.
Heap은 부모노드와 자식노드간의 일관된 대소관계를 가지는 complete binary tree이다.

8. 오일러 사이클이란?

모든 edge를 한 번씩 방문하는 사이클이다.

9. Tree traversal의 3가지 방식을 설명하시오.

Inorder, Preorder, Postorder

10. Quick sort에 대해 설명하시오.

처음에 pivot을 랜덤하게 뽑고 이 pivot을 기준으로 pivot의 왼쪽에는 pivot값보다 작은 값들을 놓고 오른쪽에는 pivot값보다 큰 값들을 놓는다. 이제 왼쪽과 오른쪽 리스트에 대하여 같은 과정(재귀함수)을 반복하면 전체 리스트가 정렬되게 된다.

11. Binary tree란? binary tree에서 각 node는 두 개의 children을 갖거나 혹은 leaf node이거나 둘 중에 하나라고 할 때, non-leaf node와 leaf node 개수의 관계식은 어떻게 되는가?

12. Minimum spanning tree를 구하는 알고리즘과, 그 알고리즘의 복잡도는?