CS17 [자료구조] Hash Table - (1) 앞서 Map을 다룰 때, key가 꼭 integer가 될 필요는 없음을 보았다. 만일 우리가 각 key를 (전체 길이 내의) 특정한 integer 값으로 바꿀 수 있다면, 이 integer 값을 index로 활용해 O(1) 시간에 map에 저장된 element에 접근할 수 있을 것이다. Hash Table이란 hash function을 이용해 구현된 map이다. hash function이란 바로 윗 문단에서 설명한 'key를 특정한 integer 값으로 바꿔 주는 함수' 이다. 이 때의 값을 'hash value' 라고 한다. 즉 어떤 pair (key, value)가 있고, hash function을 h(x)라고 하면, 이 hash table에서 value는 M[h(key)]에 저장된다. 보다 엄밀히 .. 2024. 4. 17. [자료구조] Map 정의 Map은 pair를 저장하는 자료구조이다. Map은 여기에 더해 다음 두 가지 특성을 가진다. 1. key는 반드시 자연수가 아니어도 괜찮다.(non-numeric key) 2. key가 반드시 연속될 필요는 없다.(non-consecutive key) 3. value는 중복될 수 있지만, key는 반드시 unique해야 한다. 응용 어떤 unique한 key로 무엇인가를 분류해야 하는 경우에 사용할 수 있다. - 주민등록번호(key),이름(value): 이름은 동명이인이 있을 수 있지만 주민등록번호는 각 개인이 모두 고유한 값을 가지기 때문에 map을 이용하는 것이 적절하다. - 국가 이름(key):각 국가가 사용하는 화폐(value) : 각 국가 이름은 고유하지만, 화폐는 여러 국가가 같은 화폐.. 2024. 3. 15. [자료구조] Heap(2) 새로운 last node 위치 찾기 앞선 포스팅에서 heap의 insertion, removal 연산이 last node를 필요로 한다는 것을 언급하였다. insertion 연산은 맨 끝에( 새로운 last node 위치에) 새 node를 삽입한 후 up-heap bubbling을 통해 heap을 업데이트하였고, removal 연산은 제거하고자 하는 node를 last node와 교환한 후 down-heap bubbling을 통해 heap을 업데이트하였다. 따라서 heap에서는 last node 위치를 적절히 업데이트 해 주는 것이 필수적이다. insertion 연산을 할 때는 다음 절차를 거쳐 새 last node가 삽입될 위치를 구한다. 1. 기존 last node로부터, 어떠한 node의 left .. 2024. 3. 5. [자료구조] Heap (1) 정의 Heap은 Binary Tree의 일종으로, 다음과 같은 특징을 가진다. 1) Heap-Order: 부모 node의 key와 그 자식 node의 key간 특정한 순서가 존재한다. 부모의 key가 항상 자식의 key보다 큰 경우를 max-heap, 작은 경우를 min-heap 이라 한다. 이러한 특성 때문에 heap에서는 항상 가장 큰 key 값을 가진(max-heap의 경우), 또는 가장 작은 key 값을 가진(min-heap의 경우) node가 root node가 된다. 2) Complete Binary Tree heap은 complete binary tree 구조로, 각 level이 가질 수 있는 최대한의 node를 가지고 있다(1->2->4...). 따라서 n개의 element를 가진 heap.. 2024. 3. 4. 이전 1 2 3 4 5 다음
