728x90 알고리즘/자료구조(C)22 문자열 검색: 브루트-포스법(Brute force method) 검색할 문자열을 패턴(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){.. 2023. 9. 23. 비트 벡터로 집합 만들기 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.. 2023. 9. 23. 배열로 집합 만들기 구조체 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.. 2023. 9. 23. 힙 정렬(Heap Sort) 힙(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) { //힙을 만드는 .. 2023. 9. 22. 병합 정렬(Merge Sort) 병합 정렬(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.. 2023. 9. 22. 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 기준이 되는 피벗(pivot)을 기준으로 배열을 두 그룹으로 나눈 후 피벗을 기준으로 더 작은 값은 왼쪽으로, 큰 값은 오른쪽을 옮김. 1. 한 배열의 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 할 때 2. a[pl] >= x인 pl과 a[pr] x) pr--; if (pl name, y->name); } 2023. 9. 22. 이전 1 2 3 4 다음