메타 스터디 그룹

제129회 예상문제(토픽)

정보관리 118회 3교시

6. 당신은 어느 한 프로젝트의 PM이다. 아래 사항을 참조하여 다음을 설명하시오.(문경숙)
-----------------------------------------------------------------------------------------------
1. 프로젝트 수행기간의 목표는 25일이다.
2. A 액티비티는 소요기간이 10일이다.
3. B 액티비티는 A 액티비티가 완료된 후에 시작할 수 있으며, 소요기간이 13일이다.
4. C 액티비티는 소요기간이 12일이다.
5. D 액티비티는 C 액티비티 완료된 후에 시작할 수 있으며, 소요기간이 15일이다.
-----------------------------------------------------------------------------------------------
가. 네트워크 다이어그램을 작성하시오.
나. 주경로의 수행기간을 계산하시오.
다. 목표 수행기간을 맞추기 위해서 수행기간을 단축할 수 있는 방법을 설명하시오.
라. 일정을 단축하기 위해 기존팀원 5명에 더해 팀원 1명을 추가로 투입하였다. 의사소통 수(커뮤니케이션 통로의 수)가 기존보다 얼마나 더 늘어나는지 계산하시오.
마. 프로젝트 획득가치관리(Earned Value Management)보고서에 EV=95백만원, PV=110백만원, AC=100백만원, BAC=950백만원이다. CV와 CPI를 구하고 현재까지의 작업효율이 유지될 경우의 EAC를 계산하고 설명하시오.
(단, EV : Earned Value, PV : Planned Value, AC : Actual Cost, BAC : Budget At Completion,
CV : Cost Variance, CPI : Cost Performance Index, EAC : Estimate At Completion이다.)

문6) 1)네트워크다이어그램, 2)주경로 수행기간계산, 3) 수행기간단축방법, 4) 의사소통수증가량계산 5) CV, CPI, EAC 계산, 설명

답)

I. 네트워크 다이어그램

[활동 표현방법 예]

여유시간=늦은종료일(LF)-빠른종료일(EF)=늦은 개시일(LS)-빠른 개시일(ES)

II. 주경로의 수행기간 계산

- 주공정법(Critical Path Method)은 프로젝트의 최소 기간 결정에 사용되는 일정 네트워크 분석 기법

- 주공정 경로(Critical Path)는 여유시간(float)이 '0'인 활동을 연결한 최소 경로

-. 프로젝트 목표는 25일이나 현재 프로젝트 주경로 수행기간은 27일. 프로젝트를 성공적으로 수행하기 위해서 2일의 일정단출이 필요함

-. 일정 단축기법인 공정압축법(Crashing)과 공정중첩 단축법(Fast Tracking) 활용하여 기간 단축 수행

III. 목표 수행기간을 맞추기 위해서 수행 기간을 단축할 수 있는 방법 설명

IV. 기존 팀원 5명에 더해 팀원 1명 추가 투입, 의사소통수 증가량 계산

-. 의사소통채널수=N*(N-1)/2

기존대비 추가 인력 1명 투입시 의사소통채널수는 6증가함

프로젝트 관리자는 의사소통의 복잡성을 나타내는 의사소통 채널수를 고려해야함

의사소통채널 수를 계산할 때 프로젝트관리자를 포함하여 채널 수 계산

V. CV, CPI, EAC 계산, 설명

- EV=95 백만원, PV=110 백만원, AC=100 백만원, BAC=950 백만원

- EV : Earned Value, PV : Planned Value, AC: Actual Cost, BAC: Budget At Completion, CV : Cost Variance, CPI: Cost Performance Index, EAC : Estimate At Completion

CP < 1 비효율적인 지출과 SPI <1 프로젝트 일정도 지연되고 있음

현재 상태로 프로젝트가 진행될 경우, 예산의 초과와 일정의 초과가 예상됨

제129회 예상문제(토픽)

정보관리 117회 4교시
4. 운영체제에서 페이지 교체 알고리즘을 사용한다.
가. 페이지 교체 알고리즘을 사용하는 이유에 대하여 설명하시오.
나. 페이지 교체 알고리즘의 종류를 나열하고, 각 종류별 동작 과정에 대하여 설명하시오.

문제4) 1) 페이지교체 알고리즘 사용 이유, 2) 페이지 교체 알고리즘 종류, 3) 각 종류별 동작과정

답)

I. 페이지 교체 알고리즘 사용 이유

페이징기법으로 메모리를 관리하는 운영체제에서 페이지 부재가 발생했을 경우 가상 기억장치의 필요한 페이지를 주기억장치의 어떤 페이지 프레임을 선택/교체하는지 결정하기 위해 사용

II. 페이지 교체 알고리즘의 종류

III. 오래된 페이지 교체 알고리즘 동작 과정

가 FIFO

각 페이지가 주기억 장치에 적재될 때마다 그 때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

(FIFO Page Fault: 6회 발생)

나. LRU

최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법으로 시간적인 오버헤드가 발생함

LRU Page Fault: 5회 발생

IV. 최소 호출 예정 페이지 교체 알고리즘

가. LFU

사용빈도가 가장 적은 페이지를 교체하는 기법

LFU Page Fault: 5회 발생

나. OPT

페이지 부재횟수가 가장 적게 발생하는 가장 효율적인 알고리즘

OPT Page Fault: 4회 발생

-OPT 알고리즘이 페이지 부재횟수가 가정 적게 발생, 현실에서는 앞으로 사용되지 않을 페이지를 알 수없으므로 비현실적

제129회 예상문제(토픽)

정보관리 117회 3교시
3. MST(Minimum Spanning Tree)를 구하는 알고리즘인 크루스칼(Kruskal) 알고리즘, 프림(Prim)알고리즘을 설명하시오

문3) MST(Minimum Spanning Tree) 크루스칼(Kruskal) 알고리즘, 프림(Prim)알고리즘

답)

I. MST(Minimum Spanning Tree) 개요

- 각 간선에 가중치(비용, 거리, 시간, 교통량 등)가 있는 무방향 그래프 G에서 모든 정점들을 연결하는 가중치의 합이 최소가 되는 신장 트리

- 특징: 모든 정점 연결, 가중치 최소, 간선의 개수 n-1개, cycle 제거

II. 크루스칼(Kruskal) 알고리즘 

가. 크루스칼 알고리즘 개념 

-사이클 생성여부는 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사(union-fid 알고리즘 활용)

나. 크루스칼 알고리즘 절차

순서	도식	상세설명
1		- 초기상태 - 간선의 가중치 오름차순으로 정렬 수행
2		AD 와 CE 가 가장 짧은(가중치가 가장 작은) 간선 임의로 AD 선택
3		CE 가 가중치가 5 로서, Cycle 을 생성하지 않는 가장 짧은 간선이므로 CE 선택
4		가중치 6 인 DF 선택
5		다음으로 가장 짧은 간선은 AB 와 BE 인데 임의로 AB 선택 - BD 선택시 ABD 를 연결시키면 Cycle 이 형성되기 때문에 제외
6		- 가중치 7 인 BE 선택 - Cycle 을 형성하는 BC,EF,DE 제외
6		- EG 선택하면 모든 노드들이 연결되므로 알고리즘 수행 종료

- 간선의 개수를 E, 정점의 개수를 V 라고 할때 O(ElogV)의 시간복잡도를 가짐

II. 프림(Prim) 알고리즘

가. 프림알고리즘 개념 

- 정점을 기준으로 간선을 선택 후 하나의 집합으로 보고 인접한 정점중 최소 간선을 선택

나. 프림 알고리즘절차

순서	도식	상세설명
1		초기상태  정점 D를 시작점으로 선택
2		- D 와 연결되어 있는 정점을 선택 - A, B, E, F 중 가중치가 가장 작은 A 선택
3		정점 D 또는 A 와 연결되어 있는 간선 중 가중치가 가장 작은 것 선택 - B,E, F 중 가중치가 가장 작은 F 선택
4		정점 D, A, F 와 연결되어 있는 간선 중 가중치가 가장 작은 것 선택 - B 선택
5		정점 D, A, F, B 와 연결되어 있는 간선 중 가중치가 가장 작은 것 E 선택
6		정점 D, A, F, B, E 와 연결되어 있는 간선 중 가중치가 가장 작은 것 C 선택
7		정점 G는 E, F와 연결가능하나 가중치가 작은 정점 E와 연결하면 모든 정점이 연결되어 알고리즘 수행 종료

간선의 개수를 E, 정점의 개수를 V라고 할 때, 이진힙 사용시 O(ElogV)의 시간복잡도를 가지며, 피보나치힙 사용시 O(E+VlogV)의 시간 복잡도를 가짐

IV. 크루스칼 알고리즘과 프림 알고리즘 비교

- MST 는 정보통신, 건설분야 등에서 배선의 최소길이, 최단 통신선로, 가장 짧은 도로구간, 최단 배관길이 구성 등에 사용됨

[신기술 목차]

DID 개념

- 온라인상에서 분산원장을 기반으로 사용자가 스스로 신원(사용자의 이름, 나이, 개인 고유 식별정보, 인증정보 등) 등에 대한 증명 관리, 신원정보 제출 범위 및 제출대상 통제 등을 수행할 수 있도록 하는 신원관리 체계

DID 

DID 요소기술

[자료구조 목차]

스택의 개념

- 선형 리스트 구조의 특별한 형태로 데이터의 삽입과 삭제가 한쪽 끝(TOP)에서만 일어나는 선형 구조

- 푸쉬(PUSH)와 팝(POP)을 통해 가장 최근에 보관한 자료가 나오는 LIFO(Last In First Out) 구조

스택 동작방식

- 마지막에 삽입(Last-In)한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제(First-Out)되는 구조

스택 연산

큐의 개념

- 데이터가 들어오는 위치는 가장 뒤(Rear 또는 Back)에 있고, 데이터가 나가는 위치는 가장 앞(Front)에 있어서, 먼저 들어오는 데이터가 먼저 나가게 되는 선입선출(First In First Out, FIFO)의 자료구조

큐의 동작방식

- Front는 데이터를 get 할 수 있는 위치를, Rear는 데이터를 put 할 수 있는 위치를 의미

큐의 유형

구현방안	개념도	설명
선형 큐		- 배열을 선형으로 사용하여 큐를 구현 - 삽입을 계속하기 위해서는 요소들을 이동시켜야 했으나 실제로 데이터를 옮기는 대신 전단과 후단의 위치만 관리 - 데이터의 삽입/제거가 몇 번 수행되고 나면 전단과 후단이 모두 뒤로 후퇴해서 더이상 사용할 수 없게 됨.
순환 큐 (환형 큐)		- 배열의 시작과 끝 구분이 없음 - 고성능이나, 구현은 링크드 큐에 비해 복잡
링크드 큐		- 용량에 구애받지 않고, 포인터로 연결하기 때문에 큐가 가득 차 있는지, 큐가 비어있는지 신경 쓸 필요가 없음 - 구현이 간단하나, 노드의 생성/삭제 연산 필요