Optimal Binary Search Tree (OBST) 최적 이진 검색 트리 Definitions (정의) Node Structure (노드의 구조) - \(\texttt{key}\) : 검색 대상이 되는 원소로, key는 검색 가능한 Ordered Set의 원소이어야 한다. - \(\texttt{probability}\) : 해당 노드의 key를 검색하게 될 확률이다. (\(p_{i}\) = \(Node_{i}\)를 검색할 확률) - \(\texttt{leftChild}\) : 해당 노드의 왼쪽 자식 노드를 가리키는 주솟값이다. - \(\texttt{rightChild}\) : 해당 노드의 오른쪽 자식 노드를 가리키는 주솟값이다. Average Search Time (AST, 평균 검색 시간) -..
Counting Sort 계수 정렬 - 정렬하고자 하는 원소들의 값이 \(O(n)\)을 넘지 않는 경우에 사용할 수 있는 알고리즘이다. (즉, 모든 입력값들이 입력의 개수를 넘지 않아야 한다.) - Time Complexity = \(\Theta(n)\) Mechanism (메커니즘) - 입력 배열 \(\texttt{A[1...n]}\)의 원소들을 차례대로 살펴보면서 \(1\)부터 \(k\)까지의 자연수가 각각 몇 번 나타나는지를 Counting한다. - 입력값들의 입력 빈도를 Counting함으로써 \(\texttt{A[]}\)의 각 원소가 몇 번째에 위치하는지를 계산할 수 있게 된다. Pseudo Code (의사 코드) countingSort(A[], B[], n) { // 입력 배열 A[1...n]..
Radix Sort 기수 정렬 - 입력값들을 자릿수별로 정렬시켜 나가는 알고리즘이다. - 입력이 모두 \(k\) 자릿수 이하의 자연수인 특수한 경우에 사용할 수 있다. - Time Complexity = \(\Theta(n)\) - 입력에 제한이 있는 특수 정렬 알고리즘으로, 제한이 있는 대신 비교 정렬 알고리즘보다 좋은 성능의 수행 시간을 보인다. Mechanism (메커니즘) - 입력값들의 아랫 자릿 수 부터 정렬해나아간다. - Stable Sort* 특성을 보인다. - 각 자릿수별로 정렬 시에, 기존의 비교 정렬 알고리즘을 사용하지 않고, 0~9까지 표시된 공간을 마련해서 해당 자릿수와 일치하는 원소를 저장하는 방식으로 구현한다. (이 원리가 지켜져야 기수 정렬이 입력값에 제한을 두는 대신 다른 비..
Six-Comparison Sort 여섯 가지 비교 정렬 알고리즘 - 비교 정렬 알고리즘은 최악의 경우 수행 시간이 절대 \(\Omega(n\log n)\)을 밑돌 수 없다. (이 명제에 대한 증명은, 본 포스트 아래에 결정 트리 모델을 참고하자.) - 여섯 가지 비교 정렬 알고리즘에 대한 설명은 아래 포스트를 참조하자. 1. Selection Sort (선택 정렬) 2. Bubble Sort (버블 정렬) 3. Insertion Sort (삽입 정렬) 4. Merge Sort (병합 정렬) 5. Quick Sort (퀵 정렬) 6. Heap Sort (힙 정렬) Decision Tree Model (결정 트리 모델) - 정렬할 원소끼리의 대소 비교 과정을 트리로 표현하는 데 이용되는 모델이다. - 노드..
Insertion Sort 삽입 정렬 - 선택 정렬과 버블 정렬과 달리, 삽입 정렬은 한 개 짜리 원소의 배열부터 시작하여 그 크기를 하나씩 늘려가는 방식으로 정렬한다. * Comparison Sort Algorithms (비교 정렬 알고리즘) Selection Sort (선택 정렬) (URL) Bubble Sort (버블 정렬) (URL) Insertion Sort (삽입 정렬) (URL) Merge Sort (병합 정렬) (URL) Quick Sort (퀵 정렬) (URL) Heap Sort (힙 정렬) (URL) Mechanism (메커니즘) - 배열 \(\texttt{A[1 ... n]}\)*에서 맨 왼쪽 원소부터 부분 배열에 하나씩 추가하고, 추가된 원소는 부분 배열의 모든 원소들과 대소관계를 ..
