전체 글(21)
-
CH04 : Sorting 4 - Accelerated Heap Sort
기존 heap sort는 W(n)=2nlogn+O(n) time이 걸린다. Acclerated heap sort의 경우 이를 nlogn으로 단축시킬 수 있다. (2배 speedup) fixHeap을 fixHeapFast로 개선한다. Acclerated Heap Sort아이디어 binary search에선 중앙값과 K의 비교를 통해 앞으로 살펴볼 영역의 절반을 없앤다. 즉 수평적으로 divide and conquer 전략을 사용한다. acclerated heap sort에선 수직적으로 divide and conquer 전략을 사용한다.전략 현재 heap의 height h에 대하여, h2가 될 때까지 vacant의 위치를 내린다.현재 vacant의 key값과 부..
2025.04.07 -
CH04 : Sorting 3 - Heap Sort
Heap Heap의 조건 Heap이 되기 위한 조건은 다음의 두 개이다.구조조건 : complete binary treeheight h에 대하여, h-1까지는 complete tree (꽉 찬 트리)모든 leaves는 depth h나 h-1에 위치, depth h의 leaves는 왼쪽부터 채워진다.순서조건 : partial order tree propertymaxheap 기준, parent의 key 값이 나보다 크거나 같아야 한다. minheap일 땐 parent의 key 값이 나보다 작거나 같아야 한다. 아래는 heap인지, 아닌지를 구분하는 예시이다.Heap ADT 삽입 : insert()삭제 : deleteMax()*max heap 기준탐색 : getMax()*max heap 기준W(n)$O( \..
2025.04.06 -
CH04 : Sorting 2 - Merge Sort
Merge sort는 sorting(정렬) 문제의 optimal 알고리즘으로, O(nlogn) time을 필요로 한다.Merge에 대하여 - 정렬된 sequences의 mergeMerge 문제 오름차순으로 정렬된 sequence A, B에 대하여, A, B를 합하여 하나의 정렬된 sequence C를 만들어라. 전략 A의 첫 원소와 B의 첫 원소 중 최솟값으로 C의 첫 원소를 구한다. 이가 A의 원소였다고 가정하자. 그럼 문제는 A의 나머지 원소와 B의 원소를 merge하는 것으로 재정의된다. 만약 A 혹은 B가 empty하다면, 남은 배열의 원소들을 C의 뒷부분에 붙인다. Algorithm & Analysis Algorithmmerge(A, B, C)//A or B가 e..
2025.04.04 -
CH04 : Sorting 1 - Insertion Sort, Quick Sort
정렬 문제에서의 Optimal SolutionUnsorted data에서 key를 비교해 탐색하는 경우, optimal solution은 θ(n)를 필요로 한다. Sorted data에서 key를 비교해 탐색하는 경우, optimal solution은 θ(logn)를 필요로 한다. 즉, input의 형태에 따라 문제의 복잡도는 변화한다.Insertion Sort (삽입정렬)Strategy n개의 원소를 가진 배열에 대하여 index 1부터 n-1의 원소까지가 삽입되듯이 동작한다. 삽입된 해당 원소가 swap을 이용해 적절한 위치로 이동한다. Example회색 영역은 정렬된 원소들, 검은색 영역은 현재 삽입되어 정렬될 원소,..
2025.03.30 -
CH02 : 데이터 추상화와 기본적인 자료구조
Abstract Data Type (ADT)ADT란 추상자료형으로, C++의 class와 비슷한 개념이다. ADT 동작과 그 설명을 기반으로 알고리즘을 설계하고, 정확성을 증명한다.ADT를 정의하기 위해선 다음의 것들을 명시해야 한다.자료구조가 저장할 데이터 명시ex. queue면 front, near 등지원하는 함수 명시ex. insert, delete 등동작 설명what은 설명하고, how는 설명하지 않는다. 즉 무엇을 수행하는지는 설명하지만, 어떻게 수행되는지는 설명하지 않는다.error 처리 명시TreeTree 용어root [루트] : 트리의 최상위 노드. 부모가 없는 노드라고도 한다.node의 degree [차수] : 자식의 수. 비어있지 않은 subtree의 수라고도 한다.external no..
2025.03.27 -
CH01 : [예시] 정렬된 배열에서의 탐색 알고리즘
문제 정의1. input : 오름차순으로 정렬된 n개의 원소를 가진 배열 E, 값 K2. output : E에 K가 존재할 경우 K의 index, 그 외의 경우 -1해결책 AStrategy A모든 원소를 순차적으로 확인한다.Algorithm Aint seqSearch(int[] E, int n, int K)int ans, idx;ans = -1; //Assume Failurefor (idx = 0; idx Analysis AWorst CaseW(n)=n 발생조건 : 배열의 마지막 원소만 K이거나, K가 배열에 없는 경우Average CaseA(n)=q⋅n+12+(1−q)n $A(n) = Pr(succ)A_{succ}(n) + Pr(fail)A_{fail}(n)..
2025.03.25