알고리즘/문자열 탐색(StringSearch) (4) 썸네일형 리스트형 [알고리즘] 보이어-무어(Boyer-Moore) 알고리즘 - 코딩밥상 보이어-무어(Boyer-Moore) 알고리즘이란? 보이어-무어 알고리즘은 독특하게도 문자열을 오른쪽에서 왼쪽으로 비교해나갑니다. 하지만 '이동'만큼은 왼쪽에서 오른쪽을 이루어집니다. 패턴의 오른쪽 끝에 있는 문자와 본문의 문자가 불일치하고 그 본문의 문자가 패턴 내에 존재하지 않는 경우 이동 거리는 무려 패턴의 길이와 같습니다. 우리가 사용하고 있는 대부분의 프로그램의 문자열 탐색 기능은 이 알고리즘을 사용하고있습니다. 보이어-무어 알고리즘에는 크게 두 종류의 이동이 있습니다. 나쁜 문자 이동(Bad Character Shift)과 착한 접미부 이동(Good Suffix Shift)이 그것입니다. 완전히 반대 개념인 것처럼 이름이 붙여졌즈만, 이 둘의 목적은 같습니다. 불일치가 발생한 경우 최대의 효율로.. [알고리즘] KMP(Knuth-Morris-Pratt) 알고리즘 - 코딩밥상 KMP(Knuth-Morris-Pratt) 알고리즘이란? KMP 알고리즘은 '부르트 포스'처럼 탐색 위치를 본문 왼쪽부터 시작해서 오른쪽으로 옮겨가며 문자를 직접 비교하는 방식으로 작동합니다. 하지만 처음부터 끝까지 하나하나 모든 경우의 수를 다루는 부르트 포스 탐색과 달리 KMP 알고리즘은 비교할 필요 없는 부분은 지나치고 비교가 필요한 부분만 비교를 수행하는데에 차이점이 있습니다. 패턴과 본문 내 문자열을 한 차례 비교하고 나면, 다음 단계 탐색에서 사용할 수 있는 '정보'가 남으며 이 정보를 이용하면 불필요한 비교를 피할 수 있습니다. KMP 알고리즘은 이 '정보'가 무엇인지와 이 정보를 '어떻게 활용하는가'에 대한 것입니다. KMP 알고리즘의 동작 방식 어느 문자열이든 접두부(Prefix/문자열의.. [알고리즘] 카프-라빈(Karp-Rabin) 알고리즘 - 코딩밥상 카프-라빈(Karp-Rabin) 알고리즘이란? 카프-라빈 알고리즘은 문자열 탐색을 위해 해시 함수를 이용합니다. 패턴 내의 문자들을 일일이 비교하는 대신 패턴의 해시값과 본문 내의 있는 하위 문자열의 해시값만 비교하는 방식입니다. 해시 함수를 다음과 같이 임의로 정의해보겠습니다. 문득 여기서 궁금점은 각 패턴 문자열마다 해시값을 부여하면 문자열의 각 요소에 일일이 접근하여 곱셈연산을 하고 덧셈까지 하는 '비용'이 추가적으로 발생하기때문에 오히려 부르트 포스 알고리즘이 유리해 보입니다. 하지만 여기서 해시 함수의 비용을 획기적으로 줄이는 방법이 추가됩니다. 앞 단계에서 계산된 해시함수 값으로 다음 단계의 해시값을 간추리는 것입니다. 이렇게 되면 원래의 해시 함수로는 비교할 때마다 매번 패턴 길이 M 만큼 .. [알고리즘] 부르트 포스(Brute-Force) 알고리즘 - 코딩밥상 부르트 포스(Brute-Force)란? 부르트 포스란 일차원적으로 앞에서부터 끝까지 차근차근 탐색하는 알고리즘입니다. 즉 모든 경우의 수를 모두 따지는 것입니다. 이 알고리즘은 마치 요령 부리지 않고 우직하게 일하는 일꾼처럼 동작합니다. 따라서 고지식한 탐색이라고도 합니다. 이를 문자열 탐색에 사용한다면, 본문의 길이를 M, 패턴 길이를 N이라고 했을 때 본문 속에 있는 패턴을 찾기 위해 최악의 경우 N*M번의 비교를 수행합니다. 구현 int BruteForce(char* Text, int TextSize, int Start, char* Pattern, int PatternSize){ for(int i=Start; i 이전 1 다음
