문자열 검색2 Boyer Moore 법 단순하게 처음부터 끝까지 일일히 검사하는 브루트 포스법은 간단하지만 비효율적이라는 단점을 가지고있습니다. 이런 단점을 보완하고자 고안된 방식이 Boyer Moore법이며, 이 방식이 많이 사용되고 있습니다. 1. Boyer Moore 법 Boyer Moore 법은 브루트 포스와는 다르게 키의 마지막 글자부터 처음 글자 순서로 검사를 진행합니다. 검사를 진행하다가 불일치하는 부분이있으면 그 부분만을 집중적으로 검사하고 그 칸수만큼 훌쩍 뛰어넘어 검사를 진행해서 검색 속도를 향상시키는 방법입니다. 다음 배열에서 'ABC'를 검색하려고 합니다. 우선 문자열에 키를 맞춘후 제일 마지막 요소 부터 검사를 시작합니다. 검사를 시작하는데 불일치하는 지점이 발견되었습니다. 그러면 불일치 지점에 대해 키를 이동시켜 비교.. 2021. 11. 12. 브루트-포스 법 선형 검색과 이진 검색 두가지 방식은 대게 숫자와 같은 요소들을 검색하는데 편리한 방식이었습니다. 하지만 문자열에 이 방식들을 대입하기엔 쉽지 않습니다. 그래서 문자열들을 검색할 수 있는 몇 가지 방법들을 소개하려고 합니다. 1. 브루트 포스 법 브루트 포스 법(Brute Force Method)는 마치 선형 검색처럼 모든 요소에 대해 일일히 비교하는 방식입니다. 한 문자열에서 'aba'라는 문자열을 찾으려고 한다면 다음과 같이 나타낼 수 있습니다. 우선 문자열의 인덱스 0과 키의 인덱스 0을 비교합니다. 이때 그 요소가 일치했다면 그 다음 인덱스와 키의 두번째 인덱스를 비교합니다. 비교한 결과가 일치했다면 3번째 인덱스를 다시 검사하겠지만 여기서는 불일치했기 때문에 키를 이동시켜 원 문자열 배열의 1번.. 2021. 11. 10. 이전 1 다음 300x250
