컴퓨터공학/자료구조 및 알고리즘5 Binary Search Tree binary search tree는 해당 노드보다 큰 값을 갖는 노드는 자신의 오른쪽 노드에, 보다 작은 값을 갖는 노드는 자신의 왼쪽 노드에 배치되는 binary tree이다. 왼쪽 자식 key) inorder_traversal(root->right) 다음은 보다 복잡하지만 재귀를 사용하지 않는 Morris Traversal이라는 inorder traversal 기법이다. 다음 기법은 threaded tree의 기법을 응용한다. morris_traversal(root) if root==NULL return current_node=root while current_node != NULL if current_node->left==NULL print(current_node->key) current_node=.. 2022. 7. 8. Selection Problem, 중앙값과 순서통계량 i 번째 순서통계량이란 n개의 원소집합 중 i번째로 작은 원소를 말한다. 논의를 간단하게 하기 위해 배열의 원소 개수가 짝수일 경우 (n+1)/2의 floor를 중앙값으로 간주하겠다. 또한, 모든 배열의 원소들이 서로 다른 집합을 가정한다. 그러나 같은 값을 포함하는 집합으로의 확장 역시 가능할 것이다. 선택문제는 정렬을 사용하면 O(n log n)의 시간에 풀 수 있다. 그러나 정렬하지 않고 선택만을 할 경우 O(n)시간에 풀 수도 있다. 1. 최소값과 최대값 모두가 짐작할 수 있는 가장 간단한 방법은 처음부터 끝까지 탐색을 하며 최대/최소값을 찾는 것이다. 이는 n-1번의 비교가 필요하며, 이 이하로 적게 비교는 불가능하다. minimum(A) min=A[1] for i=2 to A.length if.. 2022. 7. 5. Counting sort 지금까지 살펴본 알고리즘들은 원소들 간의 비교를 통해 정렬작업을 수행한다. 어떤 비교 정렬 알고리즘이라도 원소 n개를 정렬할 때, 최악의 경우 O(n log n)이상의 수행속도를 갖을 수 없다. 그러나, counting sort는 비교 알고리즘이 아니기 때문에 O(n)에 수행이 가능하다. counting sort는 두 가지를 전제한다. 1) n개의 입력원소 모두가 0~k 사이의 정수이다. 2) k=O(n)이다. 즉 k가 n에 비해 압도적으로 크지 않다. counting sort는 각 입력원소 x에 대해 x보다 작은 원소의 갯수를 셈으로써, 출력배열에서 원소 x의 위치를 정해가며 정렬한다. counting_sort(ary,sorted_ary,k) //count를 위한 ary 초기화 count_ary[0~k.. 2022. 7. 5. Quick sort 퀵정렬은 최악의 경우 O(n^2)의 수행시간으로, 평균 O(n log n)의 수행시간으로 배열을 정렬하는 알고리즘이다. O(n log n) 내에 숨겨진 상수인자가 매우 작아 속도 면에서 매우 효율적이며, 내부 정렬로 작동하기 때문에 실제 문제에서 가장 유용한 정렬 방법 중 하나이다. (내부정렬이란, 정렬하고자 하는 배열 이외의 추가적인 배열공간을 필요로 하지 않는 것을 의미한다.) 퀵정렬은 사전에 배열이 보다 많이 정렬되어 있을수록, 배열 내의 겹치는 원소 수가 많아질 수록 수행시간이 O(n^2)에 가까워진다. 이에 대한 자세한 내용은 후술한다. 퀵정렬은 divide&conquer방식으로 작동한다. A[first~last]의 본래 배열을 A[first~mid-1] A[mid+1~ last]로 분할한다. .. 2022. 7. 4. HEAP Heap이란 용어는 본래 힙정렬로부터 나온 말이다. 프로그래밍 언어가 제공하는 공간개념인 Heap 역시 이 자료구조에서 유래한 표현이다. Heap 자료구조란 complete binary tree를 배열로 구현한 형태의 자료구조를 의미한다. complete binary tree를 기반으로 하기 때문에 원소의 갯수가 n인 heap의 높이는 O(log n)이다. ary의 index 1부터 배열을 채우기 시작한다. 부모, 자식노드는 일반적으로 다음 매크로/인라인을 통해 구현한다 #define PARENT(i) (i>>1) #define LEFT(i) (i 2022. 7. 1. 이전 1 다음