최소힙
-
[2019 5급 공무원 2차] 자료구조론 제 4문알고리즘 2020. 6. 22. 17:42
2019년 국가공무원 5급 [기술] 공개경쟁채용 제 2차 시험 제 4문 제 4 문. 다음과 같은 순서로 데이터를 탐색 구조에 삽입할 때, 물음에 답하시오. (총 20점) 7,5,11,10,2,3,6,8,15,13 정답 ) 주어진 데이터를 삽입한 각 트리에 대한 결과이다. * 이진 탐색 트리 (Binary Search Tree) * 최소 힙 * AVL 트리 * 레드블랙 트리 (Red-Black Tree) 문제에서는 레드 링크를 이중 실선으로 표시하라 하였지만 편의상 실제 노드의 색으로 표현한 결과 트리이다. 2) n개의 원소가 삽입되어 있는 이진 탐색 트리, 최소 힙, AVL 트리, 레드블랙 트리에 새로운 원소를 삽입할 때, 최악의 경우의 시간복잡도를 빅오(Big-Oh)표기법으로 표현하시오. 정..
-
[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..
-
[변리사 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]..