yoongrammer
목차 문자열 검색 알고리즘 : Boyer Moore - Bad Character Heuristic 알아보기 boyer-moore 알고리즘은 문자열 검색 알고리즘으로써 패턴의 전처리로 얻은 정보를 가지고 패턴을 가능한 많이 이동시켜 텍스트와 비교 횟수를 줄입니다. boyer-moore 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다. 그래서 기존 패턴 검색 알고리즘과 달리 boyer moore 알고리즘은 역방향 접근 방식을 사용합니다. 패턴의 마지막 문자부터 시작하여 오른쪽에서 왼쪽으로 비교를 시작합니다. 이동 위치를 정하기 위해 boyer-moore 알고리즘은 두 가지 휴리스틱을 사용합니다. Bad Character Heuristic Good Su..
목차 문자열 검색 알고리즘 : 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..
목차 플로이드 와셜 알고리즘 (Floyd-Warshall Algorithm) 알아보기 플로이드 와셜 (Floyd-Warshall) 알고리즘은 최단 경로(Shortest path) 문제 중에 모든 정점 쌍(All-pairs)에 대해 최단 거리를 구하는 알고리즘입니다. 플로이드 와셜 알고리즘은 Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, 또는 WFI algorithm 이라고도 합니다. 특징 Dynamic Programming을 사용합니다. 유향 또는 무향 가중 그래프에서 최단 경로를 찾을 수 있으며 음수 사이클이 있는 경우는 찾지 못합니다. 그래프에 음수 사이클 여부를 확인할 수 있습니다. 구현 플로이드 와셜 알고리즘은 각각..