자료구조34 [Hash]36. Hashing 구현 목차 1. class Hashtable 2. __main__ 3. 예상 출력값 1. class Hashtable 사실 python에서는 이미 hashing에 의해 작동되는 함수들이 많지만, cs를 공부하는 의미로 제작해 보도록 하겠습니다. class Hashtable: def __init__(self): self.table = [None for _ in range(13)] def full(self)-> bool: tmp = True for i in self.table: if i==None: tmp = False break return tmp def put(self, key: int, value: str): if not(self.full()): while True: if self.table[key%13]=.. 2021. 3. 10. [Hash]35. Hashing 목차 1. Hashing 정의, 기본 개념 2. Hashing 충돌 관리 3. Separate Chaning 4. Linear Probing 5. Double Hashing 1. Hashing 정의, 기본 개념 Hashing은 데이터를 (key, value)화 시켜서 빠르게 저장하고, 빠르게 불러오는 방식을 말합니다. 사실 제가 활용하는 파이썬에서는 이미 딕셔너리가 hashing으로 구현되어 있지만, 그래도 한번 개념을 정리해보고 구현해보도록 하겠습니다. Hashing의 최종 목표는 골고루, 공평하게 데이터가 펼져디고록 배분하는 것이 최종 목표 입니다. 만일 정해진 규칙에 의하여 배분하였을 시 뒤에 서술하겠지만 충돌이 발생할 경우, 이를 해결하기 위한 방법을 마련해야 하기 때문입니다. Hashing의 기.. 2021. 3. 10. [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. 이전 1 2 3 4 5 다음
