yoongrammer

목차문자열 검색 알고리즘 : Boyer Moore - Good Suffix Heuristics 알아보기Bad character heuristics은 한 칸만 이동하는 경우가 있습니다. 이 경우 최대 이동 거리를 도출하기 위한 방법으로 Good Suffix Heuristics를 사용합니다.Good Suffix는 패턴의 문자 일부와 일치하는 텍스트의 부분 문자열을 말합니다.Good Suffix Heuristics는 세 가지 상황이 있으며 각 상황에 맞는 오프셋을 제공합니다. Case1. Good Suffix가 패턴의 다른 곳에도 있는 경우다른 곳에 있는 일치하는 패턴 문자를 Good Suffix와 일치하도록 패턴을 이동시킵니다.아래 그림에서 Bad character heuristics를 사용한다면 한칸만 이..

목차문자열 검색 알고리즘 : Boyer Moore - Bad Character Heuristic 알아보기boyer-moore 알고리즘은 문자열 검색 알고리즘으로써 패턴의 전처리로 얻은 정보를 가지고 패턴을 가능한 많이 이동시켜 텍스트와 비교 횟수를 줄입니다. boyer-moore 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다.그래서 기존 패턴 검색 알고리즘과 달리 boyer moore 알고리즘은 역방향 접근 방식을 사용합니다.패턴의 마지막 문자부터 시작하여 오른쪽에서 왼쪽으로 비교를 시작합니다. 이동 위치를 정하기 위해 boyer-moore 알고리즘은 두 가지 휴리스틱을 사용합니다.Bad Character HeuristicGood Suffix H..

목차문자열 검색 알고리즘 : Rabin-Karp 알아보기Rabin-Karp 알고리즘은 해시 함수를 사용하여 문자열을 검색하는 알고리즘입니다. 해시 함수를 사용하여 문자열을 숫자 값인 해시 값으로 변경합니다.ex) hash("hello") = 5. 해시 값이 다르다면 두 문자열은 다르다는 것이 보장됩니다.하지만 문자열이 달라도 해시 값이 같을 수 있습니다. 우리는 이것을 Spurious Hit라고 부릅니다.Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요합니다. 이 특징을 사용하여 Rabin-Karp 알고리즘은 패턴의 해시값을 텍스트의 부분 문자열의 해시 값과 일치하는지 비교하는 작업을 합니다.따라서 Rabin-Karp 알고리즘은 다음 문자열에 대한 해시 값을..

목차 KMP(Knuth Morris Pratt) 알고리즘 알아보기 navie 알고리즘은 최악의 경우 O(m(n-m+1))의 시간이 걸립니다. (n 패턴의 길이, m 텍스트 길이) 문자 하나하나 씩 비교하기 때문에 불필요한 문자 비교가 있을 수 있습니다. 다음은 navie 알고리즘으로 텍스트 T[]="banananobano"에서 패턴 P[]="nano"를 찾는 과정입니다. 이 동작에서 일부는 낭비입니다. i=2에서 T[3] = 'a', T[4]='n' 이라는 것을 확인했으니 i=3, 4에서 패턴 n과 비교하는 것은 불필요합니다. KMP 알고리즘은 lps(Longest Proper Prefix which is Suffix) 배열을 사용하여 문자열 검색 시 불필요한 문자 간 비교를 없애 성능을 개선시킨 알고리..

목차Naive Pattern Searching 알아보기naive pattern searching은 패턴 검색 알고리즘 중에서 가장 간단한 알고리즘입니다. 단순히 문자를 처음부터 끝까지 하나하나 비교해가며 패턴을 찾기 때문에 작은 문자열에서 패턴을 찾을 때 유용합니다.구현길이가 n인 텍스트 T안에 모든 위치에서 길이가 m인 패턴 P와 매치 여부를 검토합니다.패턴의 길이는 텍스트의 길이보다 작거나 같아야 합니다. (m ≤ n)T[0 ... n-1]P[0 ... m-1]패턴 P는 텍스트 T의 처음부터 n-m+1까지 이동하며 매치가 되는지 검토합니다.패턴이 발견되면 패턴의 위치를 출력하고 다음 일치 위치를 찾습니다. 구현하면 다음과 같습니다.void naivePatternSearch (char T[], char..