Hash Table 해시 테이블 - 데이터의 저장, 검색에서 극단적인 효율을 추구하는 자료구조이다. - 원소가 저장될 자리(주솟값)를 원소의 값으로 계산한다. - 즉, 저장된 원소들과 비교하여(트리와 같이) 자리를 찾아나가는 것이 아닌, 원솟값을 이용하여 단 한 번의 계산(상수시간 내 계산)으로 저장할 자리를 찾아낸다. Terminology (용어 정리) Hash Function (해시 함수) - 저장할 원소의 Key값을 Argument로 입력받아서 해당 원소가 해시 테이블상에 저장될 주소값(해시값)을 리턴하는 함수이다. Properties for Hash Function (해시 함수의 성질) - 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. - 해시값 계산이 간단해야 한다. Hash Value..
Red Black Tree 레드 블랙 트리 * 검색 트리의 종류 (URL) - 이진 검색 트리가 Build될 때 Balance(균형)이루지 못하게 되면 데이터의 저장과 검색에 \(\Theta(n)\)에 비례하는 시간이 소요된다. - 이진 검색 트리의 Balance를 일정 수준으로 유지해가며 Build하도록 고안된 대표적인 자료구조가 Red Black Tree와 AVL Tree이다. - 레드 블랙 트리는 어떤 노드를 삽입/삭제해도 레드 블랙 특성을 유지하게끔 트리를 자동으로 수선하는 자료구조이다. Background (배경지식) * Red Black Properties (레드 블랙 특성) - 레드 블랙 트리는 모든 노드에 레드 혹은 블랙의 색상을 칠하는데, 아래의 "레드 블랙 특성"을 만족시켜 가면서 색상..
Binary Search Tree 이진 검색 트리 * 검색 트리의 종류 (URL) Mechanism & Pseudo Code (메커니즘과 의사 코드) - 이진 검색 트리의 각 노드는 하나의 Key를 갖는다. - 각 노드의 Key값은 서로 달라야 한다. - 최상위 Level에 Root 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다. - 임의의 노드의 Key 값은 자신의 왼쪽에 있는 모든 노드의 Key 값보다 크고, 오른쪽에 있는 모든 노드의 Key 값보다 작다. * 이진 검색 트리의 예시 Search Operation (검색 연산) treeSearch(t, x) { // t: 트리의 루트노드를 함수에 건네서, 트리를 전달한다. // x: 검색하고자 하는 Key if(t == NULL or ke..
Search Tree 검색 트리 - 데이터를 찾는 Index(색인) 역할을 하는 자료구조이다. - 일반적으로, 트리에는 레코드 전체가 삽입되지 않고, 해당 레코드의 Key와 레코드가 저장된 위치 정보만을 저장한다. (메모리 효율성을 제고하기 위함이다.) - Binary Search Tree (이진 검색 트리) (URL) - Optimal Binary Search Tree (최적 이진 검색 트리) (URL) - B-Tree (B-트리) (URL) - AVL-Tree (AVL-트리) (URL) - Red Black Tree (레드 블랙 트리) (URL) - KD-Tree (KD-트리) (URL) - KDB-Tree (KDB-트리) (URL) - R-Tree (R-트리) (URL) Terminology (용어..
Advanced Selection Algorithm 개선된 선택 알고리즘 - 일반적인 선택 알고리즘과 같이, 입력값들중 i번째로 작은(큰) 원소를 찾는 알고리즘이다. - 개선된 선택 알고리즘은 \(\texttt{partition()}\) 함수가 수행하는 분할의 균형을 어느정도 보장함과 동시에, 그에 따른 Overhead까지 통제하여 최악의 경우에도 선택 알고리즘이 \(\Theta(n)\)에 수행되도록 한다. Background (배경지식) * Selection Algorithm (선택 알고리즘) (URL) * Quick Sort (퀵 정렬) (URL) - 일반적인 선택 알고리즘의 경우, \(n\)개의 입력값들에 대해 평균적으로 \(\Theta(n)\)에 비례하는 시간이 소요되고, 최악의 경우, \(\Th..
Selection Algorithm 선택 알고리즘 - 입력값들중 \(i\)번째로 작은(큰) 원소를 찾는 알고리즘이다. - \(n\)개의 입력값들에 대한 전체적인 검색이 필요하기 때문에 \(\Omega(n)\) 만큼의 실행시간이 요구된다. - 가장 우수한 일반 정렬 알고리즘의 성능이 \(O(n\log n)\)이기 때문에, 선택 알고리즘의 실행 시간은 적어도 \(O(n\log n)\) 과 같거나 더 우수해야 한다. Time Complexity: 평균적으로 \(\Theta(n)\), 최악의 경우 \(\Theta(n^2)\) Background (배경지식) * Quick Sort (퀵 정렬) (URL) [Algorithms] Quick Sort | 퀵 정렬 Quick Sort 퀵 정렬 - 퀵 정렬은 고급 정렬 ..
Sequential Search 순차 탐색 - 리스트의 처음 혹은 끝 부분부터 반대편까지 순차적으로 원소를 검색해나간다. - 정렬되지 않은 리스트를 검색할 때 주로 사용되는 방법이다. - 정렬된 리스트의 경우, Binary Search 알고리즘(\(\Theta(\log n)\))을 사용하는 것이 실행 시간 측면에서 더 효율적이다. * Time complexity of Sequential Search: \(\Theta(n)\) Implementation (구현) C++ template void SequentialSearch(const T list[], const int size, T key, int& location) { location = 0; while (location < size && list[lo..
