2020년 2학기 컴퓨터과학 개론 기말시험 과제

코딩이 초등학교 필수과목이 되었다는 소식을 듣고 위기감을 느꼈다. 코딩을 모르고는 살 수 없는 세상이 올 것만 같은 기분이 들었기 때문이다. 학원을 다닐까, 인강을 들을까 고민하다가 공부와 함께 학위취득까지 할 수 있는 방송통신대학교에 편입을 하였고, 컴퓨터과학과 학생으로서 수업을 듣고 있다.

컴퓨터과학과 학생으로서 다양한 과제를 제출하며 느낀 것은, 방송통신대학교 학생들을 대상으로 과제를 장사하는 사람이 정말 많다는 것이었다. 유용한 자료를 검색했다 싶으면 언제나 해피캠퍼스로 연결되는 것을 보며 몇 번이나 좌절을 했는지 모른다. 

그렇기에 지난 학기 내가 제출했던 과제들을 공유하고자 한다.

이미 지난 학기의 자료가 되어버렸기에 큰 도움이 되지 않을 수도 있으나, 누군가에게는 이 정도의 정보도 도움이 될 수 있을 것이라 믿으며 본 글을 게시한다.

방송통신대학교의 2020학년도 제2학기 기말시험(온라인평가) 컴퓨터과학개론 과제이다.

---

 

2020학년도 2학기 기말시험(온라인평가)

컴퓨터과학 개론

목 차

Ⅰ. 문제 2.

[이진 트리, 완전 이진 트리, 포화 이진 트리를 설명하고 비교하시오.]

 

Ⅱ. 문제 4.

[가상기억장치의 페이징 기법과 세그먼테이션 기법을 설명하고 비교하시오.]

 

Ⅲ. 문제 5.

[조합회로와 순차회로의 개념과 종류를 나열하고 설명하시오.]

 

Ⅳ. 문제 6.

[함수의 매개변수 전달방식인 값호출 방식과 참조호출 방식을 설명하고 비교하시오.]

 

Ⅴ. 문제 8.

[OSI 참조 모델에 대해서 설명하시오.]

 

Ⅵ. 참고문헌

 

---

Ⅰ. 문제2. [이진 트리, 완전 이진 트리, 포화 이진 트리를 설명하고 비교하시오.]

 

1. 각각의 개념

 

‘트리’는 다수의 데이터 간 관계를 나타내는 여러 방법 중 대표적인 것으로서, 실제 현실에서는 한 눈에 각 데이터 간 관계를 파악하기가 용이하다는 장점 때문에 조직도나 가계도 등에서 자주 활용되고, 컴퓨터 자료구조에서는 검색의 속도가 빠르다는 장점 때문에 활용도가 매우 높은 방법이다.

 

이러한 트리 중 ‘이진 트리(binary tree)’는 각 노드의 차수가 2개 이하인 트리를 의미한다. 이진 트리의 특성상 각 노드는 2개, 1개, 0개의 자식 노드를 가질 수 있는데, 만약 존재하는 모든 노드가 각 차수의 레벨에서 모두 2개의 자식 노드를 갖는 상태라면 이러한 상태는 ‘포화 이진 트리(full binary tree)’라고 표현할 수 있고, 모든 노드가 각 2개의 자식 노드를 갖는 것은 포화 이진 트리와 동일하지만, 각 차수의 레벨 따라 2개의 자식 노드를 갖지 않는 노드가 있는 상태의 이진 트리를 ‘완전 이진 트리(complete binay tree)’라고 표현한다. 결국 구조상 포화 이진 트리라면 완전 이진 트리에 해당하기도 하나, 모든 완전 이진 트리가 포화 이진 트리인 것은 아니라고 할 것이다.

 

2. 각 트리의 비교

 

각 트리가 n개의 노드를 갖는다고 가정했을 때 이진 트리에 대해 상정할 수 있는 가장 높은 높이는 모든 노드가 하나의 노드를 갖는 경우의 높이인 n이며, 가장 낮은 높이는 각 노드가 최대 두 개씩의 자식 노드를 갖는 경우의 높이인 (log2n) + 1이다.

 

포화 이진 트리의 경우 모든 노드가 두 개씩의 자식 노드를 가져야만 하기에 노드의 개수가 1, 1+2, 1+2+4, 1+2+4+8, 1+2+4+8+16 ... 의 순서로 증가하게 된다. 결국 포화 이진 트리의 경우 높이 n에 따라 갖게되는 노드의 수가 항상 일정하고, 해당 노드의 수는 2n-1에 해당한다.

 

완전 이진 트리의 경우, 트리의 일정 레벨까지는 포화 이진 트리와 동일하게 노드의 수가 2n-1에 해당하지만, 일정 레벨에서부터는 꼭지 노드(루트)를 기준으로 좌측의 트리만이 자식 노드를 갖고, 우측의 노드들은 자식 노드를 갖지 않게 되기에, 그 최대 깊이를 안다고 하더라도, 일률적으로 노드의 개수를 특정할 수는 없고 다만 총 노드의 개수가 2n-1을 초과하지 않는다는 대략적인 측정만이 가능하다.

 

3. 각 트리의 비교 의의

 

이러한 트리의 형태에 대한 비교가 의의를 갖는 것은 트리의 순회 방법에 있어서이다. 이진트리에 대한 순회 방법으로는 전위 순회, 중위 순회, 후위 순회를 들 수 있는데 각 트리의 형태를 파악하고 있다면 각 순회의 순서에 따라 우선적으로 방문하게 될 곳에 대한 파악을 할 수 있기 때문이다.

---

Ⅱ.문제 4. [가상기억장치의 페이징 기법과 세그먼테이션 기법을 설명하고 비교하시오.]

 

1. 각 개념의 설명 및 비교

 

컴퓨터의 각 기억장치들을 계층화시켰을 때, 속도가 빠른 것일수록 그 처리 가능 용량은 적다는 한계를 갖는다. 처리 가능 용량이 적다는 한계를 극복하기 위해 적어도 가용 가능한 용량 중 여분이 남지 않도록 만들어 이른바 단편화(fragmentation)를 막기 위한 여러 노력이 있어왔다. 페이징 기법과 세그먼테이션 기법은 보조기억장치의 주소를 주기억장치의 주소로 변환하는 과정에서 이러한 단편화를 최소화시키기 위한 방법들이다.

 

페이징 기법은 ‘페이지’라는 일정 크기의 블록을 설정한 후 보조기억장치의 데이터 등을 해당 ‘페이지’에 분산하여 적재하는 방식을 의미하며, 프로세스의 크기에 따라 몇 개의 페이지를 할당할 것인지를 정한다면, 단편화를 크게 줄일 수 있다는 것을 원리로 한다. 가령 페이지의 크기가 10이라고 했을 때 60의 크기를 갖는 프로세스에 대해 처리해야 한다면 6개의 페이지를 할당하여 이를 처리할 수 있다는 것이다. 다만 이러한 페이징 기법은 가령 프로세스의 크기가 위와 달리 61이라고 가정한다면, 단 1의 크기만을 위해서라도 7개의 페이지를 할당하여야 하기 때문에 내부적인 단편화가 발생할 수 있다는 한계를 갖는다.

 

세그먼테이션 기법은 위 페이징에 관한 사례(프로세스의 크기가 61인 경우)와 같은 때에 효과적으로 작용할 수 있는 기법이다. 페이징 기법이 ‘페이지’라는 동일 크기의 블록을 설정하는 것과 달리, 세그먼테이션 기법은 ‘세그먼트’라는 각기 다른 크기로 분할한 블록을 기반으로 가상주소를 변환하기 때문이다.

 

2. 세그멘테이션의 세그먼트

 

결국 세그멘테이션 기법이 페이징 기법과 비교되는 점이자 가장 중요한 것은 세그먼트와 관련된 것인데, 세그먼트를 보조기억장치에서 주기억장치로 적재하는 방법은 페이지 반입 기법, 배치 기법, 교체 기법의 세 가지로 나뉜다.

 

1) 페이지 반입 기법

프로세스가 실제로 페이지를 요구했을 때에 주기억 장치로 페이지를 이동 시키는 ‘요구 페이지 반입 기법’과 페이지를 아직 요구하지는 않았으나 장차 요구할 것으로 예상되는 페이지를 미리 적재시키는 ‘예상 페이지 반입 기법’으로 나뉜다.

2) 배치 기법

페이지 기법과 달리 세그먼트와 주기억 장치 간 용량의 차이가 있기에, 어떠한 세그먼트를 적재할 것인지에 관한 결정이 필요하고 이에 대해서는 시간 순서의 최초적합 기법, 크기에 따르는 최적적합 기법 등이 있다.

3) 교체 기법

주기억장치에 세그먼트를 새로이 추가할 때에 이미 주기억장치에 적재되어 있는 세그먼트 중 보조기억장치로 보낼 것을 정하는 기법으로, 무작위 페이지 교체 기법, 가장 앞에 존재하는 세그먼트를 선택하는 FIFO 기법 등이 있다.

---

Ⅲ. 문제 5. [조합회로와 순차회로의 개념과 종류를 나열하고 설명하시오.]

1. 각 개념의 설명

 

컴퓨터는 다양한 구성요소들의 총합으로 기능하는바, 각 구성요소의 연결 기능을 수행하는 이른바 ‘시스템 버스’를 제외한 나머지 요소는 모두 ‘논리 게이트’라고 칭하는 한 종류의 소자로 구성된다. 컴퓨터 시스템은 기본적으로 0과 1의 2진수 개념을 사용하기에 이러한 논리게이트는 결국 조합을 통하여 단순한 2진수 개념에서 나아가 다양한 연산을 수행할 수 있도록 구성되는데, 이렇게 논리 게이트를 조합하여 회로를 구성하는 두 가지 방식이 바로 ‘조합회로’와 ‘순차회로’이다.

 

조합회로는 현재 입력값에 따라 출력값이 결정되는 형태의 회로이며, 순차회로는 입력값과 더불어 ‘플립플롭’이라고 칭해지는 곳 내에 존재하는 추가적인 변수의 영향을 받아 출력값이 결정되는 형태의 회로이다.

 

2. 조합회로 종류

 

조합회로는 다시 기본적인 연산을 수행하는 ‘산술연산회로’와 데이터 전송과 관련된 기타 회로들로 나눌 수 있다. 산술연산회로는 ‘가산기’로 대표되는데, 가산기란 2진수 두 개를 입력받은 후 이를 합산(산술)한 결과(연산)를 출력하는 회로를 의미하고 그밖에도 ‘감산기’, ‘비교기(Comparator)’등이 존재한다. 데이터 전송과 관련된 기타 회로는 ‘디코더’, ‘인코더’, ‘멀티플렉서’, ‘디멀티플렉서’, ‘코드 변환기’, ‘패리티 검사기’ 등을 대표적인 예로 들 수 있다.

 

1) 가산기

두 개 이상의 2진수를 입력받아서 이를 가산, 즉 합산한 결과를 출력하는 조합 논리회로이다. 이러한 가산기의 종류에는 반가산기, 전가산기, 병렬가산기 등이 존재한다.

2) 디코더

‘디코더’는 n이라는 이진코드가 존재한다면, 이진코드를 최대 2의 n승까지의 정보로 변환하는 기능을 한다. 이는 인코더와 정반대의 기능인데, 인코더가 수행하는 인코딩은 정보의 형태나 형식을 다른 형태나 형식으로 변환하는 것을 의미한다.

3) 멀티플렉서

다수의 입력이 있는 경우 그 중 하나의 입력만을 출력하도록 선택하는 회로로, 이러한 멀티플렉서에서는 N개의 입력이 있는 경우 log2N개만큼의 선택 신호가 필요하다.

 

3. 순차회로 종류

순차회로는 플리플롭의 형태에 다라 T플립플로버, JK 플립플롭 등의 형태가 존재한다. 이러한 플리플롭의 나열 및 배열을 통해 ‘레지스터’가 만들어질 수 있으며, 레지스터는 데이터를 이동시키는 방식에 따라 직렬, 병렬의 입력, 출력 방식으로 네 가지의 형태로 나뉜다. 이밖에도 양방향 이동 레지스터, 재순환 이동 레지스터 등이 존재하기도 한다. 레지스터 외에 ‘카운터’, 즉 계수기 역시 순차회로의 대표적인 예인데 구체적으로는 상향 및 하향 비동기식, 3비트 동기식 등으로 나뉜다. 그 외에도 플리플롭이 고리 모양으로 연결되어 있는 링 카운터와 같은 것 역시 순차회로의 형태 중 하나이다.

---

Ⅳ. 문제 6. [함수의 매개변수 전달방식인 값호출 방식과 참조호출 방식을 설명하고 비교하시오.]

 

1. 각 개념의 설명

 

부프로그램으로서 함수가 프로시저와 결정적으로 다른 점은 ‘결과를 반환한다는 점’에 있다. 즉 함수의 아이덴티티와 같은 부분이 바로 입력값에 따라 코드 실행 결과값이 일정하게 도출된다는 사실인데, 이러한 입력값, 즉 입력 대상인 데이터를 함수로 전달하는 것이 바로 ‘매개변수’이다.

 

프로그램 제작자는 프로그램의 작성을 위하여 필요한 경우마다 함수를 호출해야 하는데, 이때 해당 함수의 사용처 및 제작자의 필요에 따라 호출의 방식이 달라진다. 이때 사용되는 대표적인 호출의 방법이 바로 값호출, 참조호출이다.

 

2. 값호출의 경우

값호출은 C언어에서 대표적으로 사용되는 호출 방법으로, 함수가 호출 되었을 때 호출된 함수 내에서 자신을 호출한 함수의 인수 내용이 수정할 수 없기에 프로그램 내 실매개변수 값에 영향을 주지 않는 형식의 방식이다.

 

이러한 방식의 호출이 효과적으로 작용하는 것은 가령 [int sum (int a, int b);] [int main ( )] [int total = (5, 10); [int sum (int a, int b)]라는 형식의 코드가 존재할 경우 int a, int b에 값을 대입하는 경우와 같은 것이 대표적이다. 이러한 형태의 코드에서는 main 함수가 sum을 호출하며 각 값으로 5와 10을 받게 될 것이고, 결국 해당 함수는 원래의 목적인 sum을 실행함에 있어, 5와 10을 합한 값인 15라는 결과를 도출해낼 것이다.

 

3. 참조호출의 경우

 

앞에서 본 sum과 달리 가령 swap과 같은 함수 형태에서는 이러한 값호출 방식이 제대로 작동하지 않을 수 있다. 참조호출은 swap과 같은 함수 형태에서도 원하는 값을 얻어내기 위해 고안된 것으로, 실매개변수 자체가 형식매개변수의 값에 대입되어 호출된 함수 내에서 도출된 값이 그대로 실매개변수에도 적용되는 형태를 의미한다. C언어와 달리 ‘reference’라는 개념이 추가된 C++에서 효과적으로 사용된다.

 

4. 메모리에 대한 비교

 

결국 값호출과 참조호출은 그 호출 방식에서 차이가 있기 때문에 메모리에서도 차이를 보일 수밖에 없다. 가령 값호출의 경우 호출된 함수 내의 int a와 최종적인 sum 함수의 a가 별개로 취급되어 각 값을 갖게되기에 메모리 공간 역시 별개로 차지하게 될 것이고, 참조호출의 경우 int a로 호출된 값이 최종 sum 부분에도 영향을 미치기에 이는 하나의 메모리 공간만을 차지하게 되는 것이다.

---

Ⅴ. 문제 8. [OSI 참조 모델에 대해서 설명하시오.]

 

1. OSI 참조 모델

 

OSI 참조 모델은 컴퓨터 네트워크 연결에 있어서 근거리 통신망(LAN)의 연결과 관련하여 국제표준화기구(International Organization for Standardization)에서 1970년대에 국제전자기술자협회(Institute of Electrical and Electronic Engineers)와 협력하여 확립한 표준이며, TCP/IP의 등장 이전까지 네트워크 환경의 표준 모델로서 그 의의가 있다.

 

이러한 OSI 참조 모델의 구현은 네트워크 통신의 중요성에 대한 논의가 증가되며 통신 기능에 대해 표준화하여 그 확장을 용이하게 하기 위해 시작된 것인데, OSI 참조 모델은 프로토콜을 계층화하여 총 7개의 프로토콜 규격을 규정한 계층을 나누었다.

 

2. OSI 참조 모델의 7개 계층

 

OSI 참조 모델의 프로토콜 계층은 가장 아래 단계부터 물리 계층, 데이터링크 계층, 네트워크 계층, 전송 계층, 세션 계층, 표현 계층, 응용 계층까지 총 7단계로 분류된다. 각 계층은 헤더, 데이터단위로 정의되는데, 이중 헤더에는 각 계층의 기능에 관한 정보가 포함되며 해당 정보를 바탕으로 송신 계층이 헤더를 생성 및 전송하면 수신 계층이 해당 헤더, 즉 송신 정보를 활용하는 것이다. 이러한 절차를 통하여 OSI 참조 모델에서 데이터는 응용 계층에서 하위 계층으로 순차적인 전송이 이루어지는데, 물리 계층과 응용 계층을 제외한 나머지 계층에서는 데이터의 시작 부분과 끝 부분에 헤더나 트레일러 형태로 정보를 추가한다. 7단계의 계층은 서로 독립적이기에, 어느 한 계층이 변경되더라도 다른 계층에 영향을 미치지 않으며, 물리, 데이터링크, 네트워크 계층은 망과의 접속에 중점을 두고 있고 전송, 세션, 표현, 응용 계층은 사용자와의 접속에 그 중점을 두고 있다.

 

1) 물리 계층(physical layer)

물리 계층은 연결 될 시스템 간 링크를 활성화하고 관리하는 물리적 장치, 즉 전기나 기계적 특성 등을 정의하며, 허브나 라우터, 케이블 등 전송매체를 통해 비트 단위의 전송이 이루어지는 계층이다.

 

2) 데이터링크 계층(datalink layer)

네트워크 계층에서 받은 패킷을 프레임으로 구성하여 물리 계층으로 전송하는 역할을 수행하며, 이러한 전송을 위해 프레임의 시작과 끝, 수신자 주소 등의 추가적인 정보가 추가되는 계층이다.

 

3) 네트워크 계층(network layer)

데이터를 패킷 단위로 분할하여 전송 후 재결합하는 역할을 수행하며, 라우팅이 프로토콜을 통해 최적의 전송 경로를 제공(혼잡 제어, congestion control)하는 계층이다.

 

4) 전송 계층(transport layer)

두 시스템 간 신뢰성 있는 데이터 전송을 위한 계층으로, 오류 복구 및 흐름 제어 등을 통해 이러한 신뢰성을 높여주는 계층이다.

 

5) 세션 계층(session layer)

두 시스템 간 연결의 접속, 차단 등 통신을 제어하는 역할 및 데이터의 단위를 전송 계층으로 전송할 순서를 결정하는 역할을 수행하는 계층이다.

 

6) 표현 계층(presentation layer)

응용 계층에서 데이터가 잘 작동하도록 시스템 간 데이터 표현의 차이를 해결하는 계층으로, 각 시스템의 표현을 서로 다른 형식으로 변환하거나 공통 형식을 제공하는 계층이다.

 

7) 응용 계층(application layer)

통신의 최종 목적을 수행하는 계층으로, 사용자로부터 입력받은 정보를 하위 계층에 전달하고, 하위 계층으로부터 전달받은 데이터를 사용자에게 전달하는 역할을 수행한다.