변리사 2차
-
[56회 변리사 2차-2번] 최소신장트리(MST)알고리즘 2020. 5. 28. 18:01
2019년 제 56회 변리사 2차 데이터 구조론 2교시 2번 문제 해설 MST (Minimum Spanning Tree) 그래프 G에서 모든 정점을 연결하여 갈수 있도록 하되, 최소의 간선개수와 최소의 가중치로 이루어진 트리를 말한다. (즉, 정점 개수 V , 간선 개수 V-1, 간선은 무방향) 1. 그래프 G에 관하여 다음 물음에 답하시오 => 정점(Vertax) 의 개수 8 => 따라서 MST를 만족하는 간선의 개수 (8-1) = 7 개를 선택하면 된다. => 이 그래프에서의 MST가 가지는총 가중치의 합은 10이다. => 즉, 가중치의 합이 10인 MST를 구하는 3가지 알고리즘을 해설 한다. (1) 그래프 G에 대해 프림 알고리즘 (Prim's Algorithm)으로 최소신장트리를 구하는 과정을 ..
-
[변리사 2차-1번] 구간 히프 (Interval Heap)알고리즘 2020. 5. 25. 19:40
2019년 제 56회 변리사 2차 데이터 구조론 2교시 1번 문제 해설 1. 구간히프를 정의하고, 그 특성에 관하여 설명하시오.(5점) * 먼저 heap이란? 숫자의 최대값, 최소값을 빠르게 탐색하기 위해 고안된 완전이진트리 (Complete Binary Tree)이다. 기본적인 Heap의 각 노드는 하나의 숫자로 이루어져 있으며 삽입,삭제시 리프노드부터 시작하여 부모-자식간의 대소판별 경쟁을 통해 최소 또는 최대값이 항상 루트 노트들 차지한다. 이러한 성질 때문에 우선순위큐 (Priority Queue)는 최소,최대 힙으로 만들어져있다. * 구간 Heap? 구간 히프는 Heap과 동일한 완전이진트리의 형태면서 각각의 노드는 최대 두개의 숫자로 구성 되어있다. 노드에 적힌 두개의 숫자는 폐구간 [a,b]..