본문 바로가기
728x90

분류 전체보기247

문자열 검색: Boyer-Moore법 Boyer-Moore법 -> KMP법보다 효율이 더 좋음 ! 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정함 건너뛰기 표 패턴의 문자열의 길이가 n일 때 옮길 크기는 다음과 같이 결정: 1. 패턴에 들어 있지 않은 문자를 만난 경우: n 2. 패턴에 들어 있는 문자를 만난 경우 2-1. 해당 문자가 패턴 안에 중복되지 않으면서 마지막에 있는 경우: n 2-2. 그 외의 패턴의 마지막 문자의 인덱스가 k일 때: n - k - 1 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산해야 하므로 건너뛰기 표의 요소 개수는 UCHAR_MAX + 1 (UCHAR_MAX: 표현할 수 있는 문자의 개수로 에 객체 형식 매크로로 정의되어 있.. 2023. 9. 23.
문자열 검색: KMP법 KMP법 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높임 '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 표로 만들어 저장 (건너뛰기 표, skip table) -> 패턴 내에서 중복되는 문자의 나열을 먼저 찾아야 함. 패턴과 패턴을 한 칸씩 비교 ! 연속해서 겹치는 횟수를 기록 예를 들어 패턴이 "ABCABD"일 때, 4번째에서 처음 겹치고(1) 5번째에서 연속으로 겹친다(2) 따라서 건너뛰기 표는 "- 0 0 1 2 0"가 된다. skip[idx]: idx번째 문자가 일치하지 않을 때 다시 되돌아가야 할 위치 ! KMP법으로 문자열 검색 #include int kmp_match(const char txt[], const c.. 2023. 9. 23.
문자열 검색: 브루트-포스법(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.
문자열, 공백 포함 문자열 입력 문자열의 선언과 초기화 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); [^'문자'] : 해당 문자가 나오기 전까지 모든 문자열을 받겠다는 의미 [^"문자열"] : 문자열을 구성하는 문자 중 하나라도 나오기 전까지.. 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.

티스토리툴바