cs51 [Dictionary]34. Dictionaries 목차 1. Dictionary ADT 2. List-based Dictionary 3. Search Table 1. Dictionary ADT Dictionary는 후에 배울 Binary Search Tree, AVL Tree, ADT 등등 탐색할 수 있는 ADT라고 생각하면 됩니다. 1) 특징 - 입력되는 데이터가 하나의 key로 간주된다 - data의 순서는 명시되어 있지 않음 (필요에 의하다면 추가 가능) - 중복되는 key를 지닐 수 있다 2) 기능 - find(k): key k에 해당하는 위치를 반환 - put(k, o): 해당 위치에 새로운 값 입력 - erase(k): key k에 해당하는 값 제거 - size(), empty() 2. List-based Dictionary Dictionar.. 2021. 2. 28. [Heap]33. Bottom-up Heap Construction 목차 1. Merging Two Heaps 2. Bottom-up Heap Construction 1. Merging Two Heaps Heap-sort도 충분히 빠른 수행이 가능한 강력한 방법이지만, heap을 구성하는 시간을 총 O(n)으로 단축할 수 있는 방법이 있습니다. 이는 두개의 node와 하나의 key값이 주어졌을 때, 이를 서로 합치는 Merging Two Heaps를 활용하여 해결할 수 있습니다. 순서는 1) 두개의 heap과 1개의 key값을 준비함 2) 1개의 key값을 root로 하고, 나머지 두개의 heap이 subtree가 되는 새로운 node를 만든다 3) root에서 downheap실행, heap의 규칙을 성립시킨다 2. Bottom-up Heap Construction Bo.. 2021. 2. 28. [Heap]32. Vector(array) Based Heap 구현 목차 1. class Heap 2. def swap 3. def upheap 4. def downheap 5. def insert, pop 6. def top, size, print 7. 테스트 1. class Heap class Heap: def __init__(self, dir: int): # 1 입력받으면 min-heap, -1 입력받으면 max-heap """heap을 생성하는 class입니다. Args: dir (int): 1이면 mean-heap, -1이면 max-heap """ self.array = [-1] # 0번째 index값은 사용 안함 self.dir = dir def is_empty(self)-> bool: # heap의 빈 여부 반환 return len(self.array)==1.. 2021. 2. 28. [Heap]31. Vector(array) Based Heap(벡터(배열)기반 힙) 목차 1. Vector(array) Based Heap 1. Vector(array) Based Heap Heap(힙)은 Complete Binary Tree이기 때문에, 배열 혹은 벡터에 충분히 저장 가능합니다. 배열 혹은 벡터로 구현한 heap은 다음과 같은 특성을 가집니다. 1) heap의 key 개수가 n이라면, 벡터의 크기는 n+1이다. 2) index i의 벡터 자리를 배정받은 node의 left child는 2i, right child는 2i + 1에 위치한다. 3) index 0번째는 실제로 사용되지 않는다(임시변수로 보통 활용함) 4) 마지막 node의 위치를 쉽게 알 수 있다 2021. 2. 27. [Heap]30. Heap-Sort(힙 정렬) 목차 1. Heap-Sort(힙 정렬) 2. 기존 PQ Sorting과 비교 1. Heap-Sort(힙 정렬) Heap을 활용한 sort은 다음과 같은 특징을 지닙니다. 1) 소요되는 메모리 양은 O(n) 2) insert, removeMin()은 O(logn)의 시간 소모 3) size, empty, min은 O(1)의 시간 소요 이때, insert과 removeMin에 O(logn)의 시간이 소모되므로, n개의 임의의 순서로 이루어져있는 배열을 정렬할 시, O(nlogn)의 시간만에 heap을 생성할 수 있습니다. 2. 기존 PQ Sorting과 비교 기존의 PQ Sorting을 사용할 시, Selection Sort 혹은 Insertion Sort은 Sorting에 O(n^2)의 시간이 소모되었습니.. 2021. 2. 27. [Heap]29. Insertion/Removal from a heap(힙에서의 삽입, 제거) 목차 1. Insertion into a heap(힙에서의 삽입) 2. Upheap 3. Removal from a heap(힙에서의 제거) 4. Downheap 5. Updating the last node(마지막 node 위치 업데이트) 1. Insertion into a heap(힙에서의 삽입) Heap에서 어떤 요소를 삽입하거나 삭제할 경우, heap이 가지는 특성인 1) 구조 맞추기, 2) 순서 맞추기, 이 2가지만 지키면 됩니다. 이중 구조는 일정하기 때문에, 우선 구조를 맞추고, 그 후에 순서를 맞추는 방식을 사용하게 됩니다. 따라서 heap에서 새로운 element를 삽입할 경우, 1) 해당 heap의 마지막 node를 찾고, 새로운 element가 들어갈 node의 위치를 확인한다. 2).. 2021. 2. 27. [Heap]28. Heap(힙) 목차 1. Heap(힙) 2. Height of a Heap(힙의 높이) 3. Heaps and Priority Queues(힙과 우선순위 큐) 1. Heap(힙) Heap(힙)은 특정한 규칙를 따르고 있는 binary tree입니다. 이 특정한 규칙은, 1) Heap-Order - 모든 internal node v에 대하여, 자식의 key값이 부모의 key값보다 항상 크거나 같아야 한다. - (단, root 제외) - key(v) >= key(parent(v)) 2) Complete Binary Tree - 이전에도 언급하였으나, heap은 complete binary tree를 따라야 한다. - 이는 모든 레벨의 node가 가득 차있어야 하며, 마지막 레벨의 node는 왼쪽으로 치우쳐있는 binary.. 2021. 2. 26. [Priority Queue]27. Priority Queue Sorting(우선순위 큐 정렬) 목차 1. Priority Queue Sorting(우선순위 큐 정렬) 2. Selection Sort 3. Insertion Sort 4. In-place Insertion Sort 1. Priority Queue Sorting(우선순위 큐 정렬) Priority Queue(우선순위 큐)가 중요한 내용을 먼저 꺼내는 ADT이니 만큼, PQ ADT는 들어온 데이터들을 key 값을 기준으로 정렬을 해야합니다. 이를 Priority Queue Sorting이라고 하며, 이를 구현할 수 있는 방법은 다양합니다. 2. Selection Sort Selection Sort(선택정렬)은 PQ-sort의 일종으로, 해당 priority queue가 정렬되지 않는 sequence와 연결되어 있는 구조를 뜻합니다. Se.. 2021. 2. 26. 이전 1 2 3 4 5 6 7 다음
