본문 바로가기

알고리즘18

Graph - 그래프 정의 및 특성 - Directed graph (digraph) - G = (V, E) - V: vertex들의 집합 - E: V 원소들의 순서쌍 집합 - directed edge (v, w)는 v->w 또는 vw로 나타냄. - Undirected graph - G = (V, E) - V: vertex들의 집합 - E: V 원소들의 순서가 없는 쌍 집합 - undirected edge {v, w}는 v-w 또는 vw, wv로 나타냄. - incident: 간선-정점 간의 연결 관계 / adjacent: 정점-정점 간의 인접 관계 - Weighted Graph - edge에 값이 있는 경우. - (V, E, W)또는 (V, E)로 나타냄 - Graph Representations - G = (V, E), n = |V|, .. 2021. 4. 30.
Radix Sort Radix sort 키값에 대한 속성이 주어졌을 때, 비교 연산이 아닌 다른 연산을 사용해 linear time에 정렬을 수행할 수 있다. 속성 예시 : 이름, 다섯 자리 10진수, 범위가 정해진 정수 정렬 과정 1. 서로 다른 pile에 분배 - θ(n) 2. 각각의 pile을 정렬 3. 정렬된 pile들을 합침 - θ(n) 최하위 숫자(or 비트, 문자, 필드)순으로 pile에 분배하면 정렬 과정을 생략 가능 Total O(d*(n+k)) (d: 필드 수(ex. 다섯 자리 십진수에서 5), k: pile 수(ex. 다섯 자리 십진수에서 10(0~9))) -> d, k가 constant라면 θ(n) 2021. 4. 9.
Heapsort Heap 구조((left) Complete binary tree)와 순서(부모 key값 >= 자식 key값)를 만족하는 binary tree HeapSort insert() -> upHeap() : 리프에서 루트까지 swap. O(logn) removeMax() -> deleteMax() : 끝값을 루트에 덮어씌운 뒤 리프까지 swap. findMax() : 루트노드의 키값 리턴. O(1) heapSort(E, n): 배열 E로부터 힙 H를 만든 뒤 max값을 빼서 E에 순서대로 넣는 과정을 n번 반복한다. deleteMax(H): 가장 마지막 노드 값을 가장 첫번째 값에 덮어씌움-> 마지막 노드 삭제-> fixHeap fixHeap(H, K): downHeap. 왼쪽 자식과 오른쪽 자식 중 더 큰 것과.. 2021. 4. 8.
Sorting - Merge Sort / Heap Sort 1. Merge Sort 1) Merge 정렬되지 않은 A, B 두 배열이 주어졌을 때 하나의 정렬된 배열 C를 만든다. A, B 각각의 맨 앞 원소를 비교해 더 작은 값을 C로 옮기는 과정을 반복한다. W(n) = n-1 (맨 마지막 원소는 비교 없이 옮기기 때문) 2) Merge Sort 의사코드 void mergeSort(배열 E, int first, int last) if(first 2021. 4. 2.
Sorting - Insertion Sort / Quick Sort - Unsorted data에서 key값을 찾는 데는 θ(n) 비교, Sorted data에서 key값을 찾는 데는 θ(logn) 비교가 필요하다. 따라서 Sorting이 중요하다. 1. Insertion Sort 인덱스 1부터 시작해 인덱스를 키워가며 앞의 값들과 비교해서 맞는 위치에 끼워 넣음. sorted segment 영역을 늘려간다. i번째 원소의 값이 i-1번째 값보다 작으면 위치 교환, 바뀐 i-1번째 값이 i-2번째 값보다 작으면 교환, 인덱스 0까지 반복. Input: n>=1인 배열 E, 인덱스 범위는 0~n-1 Output: 오름차순 정렬된 배열 E Loop invariant (루프 불변): 알고리즘의 correctness 증명법. 다음의 세 가지를 증명한다. Initializatio.. 2021. 4. 2.
Abstract Data Type (ADT) Abstract Data Type Structures/Funtions C++이나 Java의 Class와 같은 것 알고리즘을 디자인하고 정확도를 개선 Tree Root: 부모노드가 없는 노드 Degree: 자식노드의 수 External node(leaf): 자식노드가 없는 노드 Internal node: 자식노드가 있는 노드 Ancestor of a node x: 루트까지의 simple path의 노드들 (x 포함, proper ancestor: 자기 자신 제외) Descendant: ancestor의 반대 개념. 자신 아래에 있는 모든 노드들. Subtree rooted at a node x: x의 descendant들을 모은 트리. 루트는 x Depth: 0부터 시작하여 자식으로 내려갈수록 1씩 증가 .. 2021. 3. 26.

티스토리툴바