진진진 개발일지

검색할 문자열을 패턴(pattern), 문자열 원본을 텍스트(text)라고 함 프루트-포스법 텍스트의 첫 문자부터 1칸씩 옮기며 순서대로 패턴과 비교 이전에 검사를 진행한 위치를 기억하지 못하므로 효율이 좋지 않음 #include int bf_match(const char txt[], const char pat[]){ int pt = 0; //txt 커서 int pp = 0; //pat 커서 while(txt[pt] != '\0' && pat[pp] !='\0'){ if(txt[pt] == pat[pp]){ pt++; pp++; } else{ pt = pt - pp +1; pp = 0; } } if(pat[pp] == '\0') return pt-pp; return -1; } int main(void){..

문자열의 선언과 초기화 char str1[10] = "ABCD"; char str2[10]; str2 = "ABCD" //오류 -> 초기화와 대입은 다름 포인터와 문자열 char st[] = "12345"; //배열에 의한 문자열의 크기는 6bytes char *pt = "12345"; //포인터에 의한 문자열의 크기는 sizeof(char *) + 6bytes 포인터는 문자열 리터럴을 저장하기 위한 영역 외에도 pt가 갖는 메모리 영역이 더 필요 pr을 위한 영역: sizeof(char*) 공백 포함 문자열 입력 받기 1. scanf("%[^\n]s",str); [^'문자'] : 해당 문자가 나오기 전까지 모든 문자열을 받겠다는 의미 [^"문자열"] : 문자열을 구성하는 문자 중 하나라도 나오기 전까지..

unsigned long형이 32비트라고 가정. 정수를 구성하는 비트의 나열을 비트 벡터(bit vector)라고 함 아래 비트부터 B0, B1, ..., B31이라고 할 때 32비트의 부호가 없는 정수 하나로 {0, 1, ..., 31}을 전체 집합으로 표현 가능 매크로 SetOf(no) typedef unsigned long BitSet; #define SetOf(no) ((BitSet)1 있으면 {n}, 없으면 0(공집합) int IsMember (BitSet s, int n){ return s & SetOf(n); } Add 함수 집합 s에 n을 추가하기 위해서는 집합 s와 {n}을 논리합(OR) 연산 -> 집합 s의 n에 대응하는 비트가 0에서 1로 변경됨 void Add(BitSet* s, i..

구조체 IntSet: int형 원소를 갖는 집합을 관리 typedef struc{ int max; //집합의 최대 크기 int num; //집합의 원소 개수 int* set; //집합 } IntSet; 헤더 파일 IntSet.h #ifndef ___IntSet #define ___IntSet typedef struct { int max; int num; int *set; } IntSet; int Initialize(IntSet *s, int max); int IsMember(const IntSet *s, int n); int IsFull(const IntSet *s); void Add(IntSet *s, int n); void Remove(IntSet *s, int n); int Capacity(cons..

힙(Heap) 부모의 값이 자식의 값보다 항상 크다(또는 작다)는 조건을 만족하는 완전이진트리 트리의 레벨 순서대로 배열에 저장하면 a[i] 노드에 대하여 다음과 같은 관계가 성립: 1. 부모는 a[(i-1) / 2] 2. 왼쪽 자식은 a[i*2 +1] 3. 오른쪽 자식은 a[i*2 +2] 힙 정렬(Heap sort) 가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘 -> 힙에서 루트를 없앤 다음 다시 힙을 만들어야 함 1. 마지막 요소를 루트와 바꿈 2. 큰 값을 가지는 자식과 위치를 바꾸며 내려가는 작업을 정렬되지 않은 부분에서 반복. 자식이 더 작거나 leaf에 도달하면 종료. static void downheap(int a[], int left, int right) { //힙을 만드는 ..

병합 정렬(Merge sort) 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 후 둘을 병합하여 정렬하는 알고리즘 배열의 요소 개수가 2개 이상인 경우: 1. 앞부분을 병합 정렬로 정렬 2. 뒷부분을 병합 정렬로 정렬 3. 배열의 앞부분과 뒷부분을 병합 (두 배열의 요소를 하나씩 선택하여 비교한 후 작은 값을 대입) #include #include static int* buff; //작업용 배열 static void __mergesort(int a[], int left, int right) { if (left < right) { int center = (left + right) / 2; int p = 0; int i; int j = 0; int k = left; __mergesort(a, left, ce..

퀵 정렬(Quick Sort) 기준이 되는 피벗(pivot)을 기준으로 배열을 두 그룹으로 나눈 후 피벗을 기준으로 더 작은 값은 왼쪽으로, 큰 값은 오른쪽을 옮김. 1. 한 배열의 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 할 때 2. a[pl] >= x인 pl과 a[pr] x) pr--; if (pl name, y->name); }

삽입 정렬(Insertion Sort) i (0 tmp; j--) { a[j] = a[j - 1]; // tmp가 더 작으므로 정렬된 부분을 한 칸씩 뒤로 미룸 } a[j] = tmp; // 찾은 자리 j에 tmp를 넣음 } } 시간 복잡도: O(n^2) - avg, worst (best는 O(n))

선택 정렬(Selection sort) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 1. 정렬되지 않은 부분에서 가장 작은 키의 값을 선택 2. 아직 정렬하지 않은 부분의 첫 번째 요소와 교환 이 과정을 n-1회 반복 void selection(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++) { int min = i; for (j = i + 1; j < n; j++) if (a[j] < a[min]) min = j; swap(a[i], a[min]); } } 시간복잡도: O(n^2) - best, avg, worst 모두 동일

버블 정렬(Bubble sort) 서로 인접한 두 원소를 비교하여 정렬되어 있지 않은 경우에 교환하는 정렬 알고리즘 *일련의 비교 과정을 패스(pass)라고 함 비교 횟수: (n-1) + (n-2) + ... + 1 = n(n-1)/2 이므로 시간복잡도 O(n^2) (best, avg, worst 모두) #include #include #define swap(x, y) do {int t = x; x = y; y = t;} while(0) void bubble(int a[], int n) { int i, j; for (i = n-1; i > 0; i--) { for (j = 0; j a[j + 1]) swap(a[j], a[j + 1]); } } } int main..