변리사
-
[56회 변리사 2차-4번] 이진트리 (Binary Tree)알고리즘 2020. 6. 3. 19:39
2019년 제 56회 변리사 2차 데이터 구조론 2교시 4번 문제 해설 이진 트리 (Binary Tree) 하나의 노드가 최대 두개의 자식 노드를 가지는 트리를 말한다. 이진 트리 개념 속 여러 용어가 있지만 중요한 몇가지 용어를 소개한다. 노드의 차수 (Degree): 노드의 서브트리 수 단말(Terminal) 노드: 리프(leaf) 노드라고하며 차수는 0 비단말 노드: 차수가 0이 아닌 노드 노드 레벨: 루트 (레벨 1) 트리의 차수: Max(노드의 차수) 트리의 높이 (Height , Depth) : Max(노드 레벨) 자식 (Child) ,형제 (Sibling) 선조 (Ancestor): 루트까지의 경로상에 있는 모든 노드 자손 (Descendants): 한 노드의 서브트리에 존재하는 모든 노드 ..
-
[56회 변리사 2차-3번] Heap Sort알고리즘 2020. 6. 2. 16:52
2019년 제 56회 변리사 2차 데이터 구조론 2교시 3번 문제 해설 Heap Sort (힙 정렬) 힙정렬을 하기 위해서는 데이터가 힙구조 상태여야한다. 따라서 힙정렬 전에 데이터를 먼저 Heapify Algorithm으로 힙구조를 만든다. (힙구조는 여러개 나올 수 있다.) 오름차순 정렬을 위해 Max Heap을 구성하여 Max Heap의 가장 끝에 해당하는 리프노드와 root를 Swap하면 가장 큰 값이 가장 끝에 위치하게 된다. 가장 끝에 가장 큰 값이 위치 했으므로 가장 끝의 위치를 N이라고 하면 N-1의 위치에 그 다음으로 가장 큰 값을 위치시키면 된다. 이후 부터 다시 Max Heap 만들고 리프와 루트의 Swap (N-1)번 작업하며 정렬하는 알고리즘이다. 참고 ↓ https://www..
-
[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]..