[2019 5급 공무원 2차] 자료구조론 제 3문

2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 3문

 

제 3 문. 다음은 어떤 프로젝트에서 수행해야 할 작업 간의 선행관계를 나타내는 AOV (activity on vertax) 네트워크이다. 이때 정점은 작업(activity)을 나타내며 방향 간선은 작업 간의 선행관계를 나타낸다. 물음에 답하시오. (총 20점)

 

 

AOV네트워크

- Activity On Vertax-

 

정점 (Vertax) : 작업

간선 (Edge) : 선행 관계

정점 A, 정점 B가 있을 때

A->B 는

B라는 작업을 하기 위해서 A가 먼저 선행되야함을 뜻한다.

이러한 선행관계로 구성된 단방향 그래프 G를 AOV 네트워크라고 한다.

 

1) 다음의 선행관계에 대한 정의 중에서 수행 가능한 프로젝트를 표현하는 AOV 네트워크에 존재하지 않아야 하는 것을 모두 고르시오. (4점)

 

 

㉠이행적(transitive) 선행관계
㉡반사적(reflexive) 선행관계
㉢부분 순서(partial order)
㉣방향 사이클
㉤위상 순서(topological order)

 

 

해설)

 

AOV 네트워크 그래프는 정점이 작업을 나타내고 간선이 작업의 선후관계를 나타내는 방향 그래프이다. 이 그래프는 다음과 같은 성질을 가진다.

 

부분 순서(Partial order)

이행적, 비반사적인 선행 관계를 말한다. 즉, 방향 사이클이 없는 그래프와 같다.

 

위상 순서(Topological order)

임의의 두 정점(작업) i,j가 있을 때 i가 j의 선행자(먼저 수행되어야 하는 작업)이라면 선형 순서에서도 i가 j앞에 있는 그래프여야 한다.

 

따라서 위 성질에 의해 답은 ㉡,㉣ (반사적 선행관계, 방향 사이클)이 된다.

 

2) 다음은 주어진 AOV 네트워크가 수행 가능한 프로젝트인지 판단하는 알고리즘의 C언어 형식의 의사코드이다. 입력 매개변수인 그래프(Graph)는 주어진 AOV 네트워크를 의미하고, n은 총 정점의 수를 의미한다. 수행가능한 프로젝트일 경우 true, 수행이 불가능한 프로젝트인 경우 false를 반환하여야 할 때, 의사코드가 올바르게 수행되기 위해 빈칸 ㉠과 ㉡을 완성하시오. (6점)

 

 

해설)

위상정렬 기법과 같은 논리이다.

하단코드에 주석으로 해설내용을 기술한다.

 

 

 

01: typedef struct node *nPointer;
02: typedef struct {
03:         int vertex; //정점 번호
04:         nPointer link; //다음 정점을 가르킴
05:         } node;
06: typedef struct {
07:         int count; //진입 차수이다. 정점으로 들어오는 간선의 개수 
08:         nPointer link; //다음 정점을 가르킴
09:         } heads;
10: 
11: bool isWorkable(heads graph[], int n) {
12:    int i, j, k, t=-1;
13:    nPointer ptr;
14:    for (i=0; i<n; i++) {
15:       if (graph[i].count == 0) { //진입 차수가 0인 정점을 발견했다면
16:           graph[i].count = t;
17:           t = i;  //해당 정점 번호를 기록
18:       }
19:    }
20:    for (i=0; i<n; i++) { 
21:       if (t == -1) //-1이라는 것은 진입차수가 0인 정점을 발견하지 못했거나 사이클이다.
22:          return false;
23:       else {
24:          j = t; //진입을 시작할 정점번호를 j에 기록
25:          t = ㉠   -> // 답 : t = -1; 초기화
26:          for (ptr = graph[j].link; ptr; 
                 ptr = ptr->link) { //연결리스트들을 순회한다.
27:             k = ㉡ // 답 : k = ptr->vertax; //다음 정점 번호.
28:             graph[k].count--;
29:             if (graph[k].count == 0) { //다음 정점 번호가 0이라는 것은 새로운 진입 대상
30:                graph[k].count = t;
31:                t = k; //진입해봐야하 정점 번호 기록
32:             }
33:          }
34:       }
35:    }
36:    return true;
37: }

 

 

1. i=0 일 때 j=0

 

첫번째 반복문에서 진입차수 0인 정점번호 0이 t값에 기록되어 있기 때문에

j값은 0이다.

이후

ptr->link를 통해 1,2번 정점을 한번씩 방문하면서 count 값 (진입차수)를 -1씩 한다. 이것은 방향 간선을 제거하는 것과 같은 의미다.

이 과정에서 2번 정점을 방문할 때, 2번 정점의 진입차수가 0이 되므로 t값은 2로 갱신된다.이 뜻은 새로운 진입 정점이 2로 변경되었다는 뜻이다.

 

* Update된 진입차수 테이블은 다음과 같다.

 

 

 

 

 

 

2. i=1 일 때 j=2 (새로운 진입정점 번호)

 

t값은 새로운 진입 정점인 2로 기록되어 있으므로 2번 정점에서 새로운 선형 탐색을 시작한다.

정점 2에서 1 방문 : 1번 진입차수가 0이되면서 새로운 진입 정점 번호 1로 기록

 

 

 

* Update된 진입차수 테이블은 다음과 같다.

 

 

 

3. i=2 일 때 j=1 (새로운 진입정점 번호)

 

t값은 새로운 진입 정점인 1로 기록되어 있으므로 1번 정점에서 새로운 선형 탐색을 시작한다.

정점 1에서 3 방문 : 3번 진입차수가 0이되면서 새로운 진입 정점 번호 3로 기록

 

* Update된 진입차수 테이블은 다음과 같다.

 

 

 

4. i=3 일 때 j=3 (새로운 진입정점 번호)

 

t값은 새로운 진입 정점인 3로 기록되어 있으므로 3번 정점에서 새로운 선형 탐색을 시작한다.

정점 3에서 4 방문 : 4번 진입차수가 0이되면서 새로운 진입 정점 번호 4로 기록

 

* Update된 진입차수 테이블은 다음과 같다.

 

 

 

 

5. i=4 일 때 j=4 (새로운 진입정점 번호). 반복문의 마지막.

 

4번 정점에서 더이상 갈 정점이 없으므로 여기서 반복문이 종료되고 최종적으로 return true를 반환하면서 AOV 네트워크가 정당함으로 판단되며 끝난다.

 

 

 

4) 주어진 AOV 네트워크의 총 정점의 개수를 n, 총 간선의 개수를 e라고 할 때에, 2)의 의사코드의 시간복잡도를 비오(Big-Oh) 표기법으로 표현하고 이를 증명하시오. (4점)

 

해설)

 

시간복잡도는 다음과 같다.

 

각 정점을 한번씩 보면서 그 정점에 연결된 간선들을 끊어내는 작업으로 선형 시간 내에 끝난다.