목록자료구조 (22)

오늘도 더 나은 코드를 작성하였습니까?

Heap의 정의와 kotlin 구현

정의 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다. 힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙(max_heap)', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙(min_heap)'이라고 부른다. 키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 각 노드의 자식노..
자료구조 2023. 11. 18. 02:45
Hash Collision(해시 충돌) Chaining(체이닝) 및 kotlin 구현

해시 충돌 hash function이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황 Chainning (체이닝) hashTable의 각 슬롯이 연결 리스트의 형태로 데이터를 저장하여, 동일한 출력을 값을 가지는 데이터가 들어 오더라도 같은 hash table의Idx에 저장하여 충돌을 해결한다. 새로운 데이터를 넣을때는 각 해당 슬롯의 가장 앞에 삽입한다. 그러면 항상 O(1)의 시간이 걸린다. 하지만, 검색 및 삭제는 해당 슬롯의 충돌되어 삽입된 갯수에 따라 성능이 좌우된다. 이때, hashFunction을 C-Universal Function을 사용하면, 각 슬롯의 평균적인 연결리스트의 길이는 O(1)이라 이미 증명되어 있다. class ChainingHashTable(private va..
자료구조 2023. 11. 14. 22:29
HashTable Open Addressing(Linear Probing) kotlin 구현

class OpenHashTable(private var initTableSize: Int = DEFAULT_TABLE_SIZE) { companion object { private const val DEFAULT_TABLE_SIZE = 20 private const val FULL = -1 } private enum class State { OCCUPIED, EMPTY } private data class Slot(var state: State, var key: K? = null, var value: V? = null) { var hashCode = key.hashCode() } var size: Int = 0 private var table: Array = Array(initTableSize) { S..
자료구조 2023. 11. 10. 03:19
Hash Collision(해시 충돌) Open Addressing(개방 주소법)

해시 충돌 hash function이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황 Open Addressing(개방 주소법) 해시 충돌이 발생하면 테이블 내의 사용되지 않는 곳을 탐사(Probe) 한 후, 비어있는 곳에 충돌된 데이터를 저장하는 방식 - Linear Probing (선형조사) 비어있는 곳을 선택할 때, 바로 다음 빈 공간으로 한다. 1. 함수의 결과에 따른 index의 슬롯이 비어 있으면 데이터를 저장한다. 2. 비어 있지 않다면, 이전에 저장된 데이터의 key 비교한다. 3. key 값이 같다면, 값을 업데이트한다. 다르면 바로 다음 index를 확인합니다. 3. 빈 슬롯을 찾을때까지 1칸씩 이동하여, 빈 슬롯을 찾으면 데이터를 저장합니다. *저장을 하는 배열은 원형이라..
자료구조 2023. 11. 9. 18:47
이전 Prev 1 2 3 4 5 6 Next 다음