DataStructure

Problem definition (문제 정의)text : simple string of characters (문자열을 찾을 텍스트)pattern : simple string of characters (찾을 텍스트 - 패턴)to do : find where in the text the patter occurs 패턴이 나타나는 텍스트 찾기AlgorithmAlgorithm시간공간naive $O(mn)$ $O(n)$ or $O(1)$DFA (Deterministic Finite Automaton) $O(\sum m + n)$ - 테이블 제작 + 텍스트 읽기 $O(\sum m$ - 테이블 메모리KMP (Knuth Morris Pratt) $O(m+n)$ $O(m)$* n : 텍스트의 길..

Unpacked unsorted빈 자리들이 흩어져 있음 - item 별로 사용중인지 아닌지 표시가 필요함free list head로 빈 칸들의 리스트를 만든다빈 칸인 인덱스를 계속 따라가면 다른 빈 칸인 인덱스를 알 수 있음실제 free block의 번호 > 다음 free block 의 번호search : O(n) - binary searchinsert : [search O(n)] O(n) (free list head 추가시 O(1))delete : [search O(n)] O(1)Unpacked sorted지울 때 값을 지우는 것이 아닌 다른 배열에 존재 하는지 하지 않는지 마킹함지우지 않은 칸, 지운 칸 모두 유지해서 sorting order가 맞아야함#include int a[100] = {0};i..

Packed sorted정렬이 되어있다는 것을 가정하므로 search 시 binary search를 사용할 수 있음item의 개수를 표시하는 변수가 필요함 (packed의 특징)insert : search를 통해 계속 좁혀오다가, 두 개의 리턴 값을 보낼 수 있음 (그 사이 혹은 그 곳에 insert)#include int a[100] = {0};int size = 0;int r, l, m;int arr_search(int a[], int n, int x){ int s, e, m; s = 0; e = n-1; while(s x) e = m-1; else s = m+1; } l = e; r = s; return -1;}void arr_insert(i..

Array (배열): 연속된 주소, 같은 타입array는 에를 들어, 8개의 자리가 있어도 꽉 차있지 않을 수도 있음 > 빈 칸이 있을 수도 있다는 것 how to store items in an array? (배열에 데이터를 어떻게 저장하는가)packed vs unpacked빈 자리를 한 쪽으로 모으는지 여부에 따른 것packed : 사용하는 칸을 한 쪽으로 뭉쳐놓기unpacked : 사용하지 않는 칸과 사용하는 칸이 섞여 산발적으로 데이터가 흩어져있음sorted vs unsorted item들이 정렬된 상태를 유지하는지의 여부에 따른 것같은 값들이 없다는 전제 하에 이루어짐sorted : 정렬된 상태unsorted : 정렬되지 않은 상태 Packed Unsorted index0123456value30..

Merge Sort : 두 개의 sorting된 배열을 비교하여 더 작은것부터 정렬하여 전체 sortingint sort(int a[], int n){ int h; int b[n]; h = n/2; //copy a[] to b[] sort(b,h); // 왼쪽 sorting sort(b+h, n-h); //오른쪽 sorting // merge two halves in b to a return ;} Proof of invariantsorting의 정의 (invariant)sorting이 끝난 후 배열에 저장된 값들을 b[0], b[1] …b[n-1]라고 부르자 (같은 배열이지만 구별하기 위해)조건 1 : {a[0], a[1], … a[n-1]} = {b[0], b[1] … b[n]} 집합으로 같음조건 2 ..

proof of correctness of sorting (정렬에 대한 증명, 정렬이란 무엇인가)입력 : 정수 집합 {a[0], a[1], ... a[n-1]}sorting이 끝난 후 배열에 저장된 값들을 {b[0], b[1], ... b[n-1]}이라고 하자 (같은 배열이지만 구별하기 위함조건 1 : {a[0], a[1], ... a[n-1]} = {b[0], b[1], ... b[n-1]} 집합으로 같음조건 2 : b[0] Selection sort (선택 정렬) int sort(int a[], int n){ int i, j, m, t; for(i = 0; i a[j]) m = j; t = a[i]; a[i]=a[m]; a[m]=t; } return;}proof of..

Binary search (이진 탐색)#include int binary_search(int a[], int n, int x){ int l = 0; int r = n-1; while(l x) r = m-1; // 찾는 수가 더 작은 경우 else l = m+1; // 찾는 수가 더 큰 경우 } return -1; // ... (1)}int main(){ int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; printf("%d\n", binary_search(a, 10, 3)); return 0;}index가 있으면 index를 return 하고, 없으면 -1을 return l은 왼쪽 끝의 index, r은 오른쪽 끝의 인..

Array (배열)정의 : 연속된 주소, 동일한 타입장점 : n개 중 k번째 access가 상수 시간에 가능, Search가 빠름(경우에 따라 다를 수는 있음)단점 : 크기 변화 비용이 크다, Insert, Delete가 느릴 수 있다.사용 : 변화가 없거나 드문 자료에 사용함Linear Search (선형 검색)순서대로 전부 탐색하는 검색 방법 #include int linear_search(int a[], int n, int x){ for (int i = 0; i 찾지 못하면 -1을 return 하도록 약속함배열의 이름은 주소 : a[i] == *(a+i)O(n) Sorting이 되면 더 빨리 검색할 수 있음

수학적 귀납법수학적 귀납법의 기본형Base : P(1)이 참이다Step : P(n-1) → P(n)이 참이다 ( p→ q 형태 )Result : P(n)은 모든 자연수에 대해 참이다우리가 증명하려는 것은 전체가 참이라는 것을 보이는 것이다. 하나하나가 참인지 거짓인지는 알지 못해도 됨.그 이유는, P(n-1)이 거짓일 때는 무조건 T가 되기 때문에 P(n-1)이 참일때 전체가 참이면 무조건 P(n)은 참이다. * P : 무엇인지 모르는 것 > 이름, 명제 등* n : 자연수 ex) Prove that $1 + 2 + 3 ... + n =  \frac{n(n+1)}{2}$ for all $n \epsilon \mathbb{N}$(1) Base : \(P(1) = 1 = \frac{1 \times 2..