Juno's daily

Boyer-Moore법은 브루트 포스법을 개선한 KMP법 보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용되는 알고리즘이다. R.S Boyer과 J.S Moore가 만든 Boyer-Moore법은 KMP법보다 효율이 더 좋은데, 원리는 텍스트와 패턴을 비교할때, 패턴의 마지막 문자부터 앞으로 검사를 진행하며, 일치하지 않는 문자가 있으면 미리 준비한 Skip table 에 따라서 패턴을 옮길 크기를 정하는 것이다. Boyer-Moore 법은 두 접근 방식의 결합이다. (1) Bad Character Heuristic (2) Good Suffix Heuristic 위 두 방법은 텍스트에서 패턴을 찾는데 있어 독립적으로 사용될 수 있다. 두 독립적인 접근 방법이 어떻게 Boyer Moore알고리..

1. KMP알고리즘이란 문자열 검색 알고리즘을 지난번 브루트 포스 알고리즘으로 하나하나 반복해서 검색하는 것을 알아보았었다. M개의 문자열(text)에서, N문자열(pattern)이 어디에 포함되어 있는지를 검색하기 위해서, text를 돌면서 pattern과 일치하는 지를 하나하나 검색했었다. 따라서 시간복잡도는 O(MN)이였다. 이를 O(M+N)의 시간 복잡도로 줄일 수 있는 방법이 바로 KMP 알고리즘이다. Knuth, Morris, Pratt 세 사람이 거의 같은 시기에 고안했기 때문에 이들의 이름 앞 글자를 각각 따서 KMP 법이라고 부른다. 그럼 KMP 알고리즘은 어떻게 문자열 검색을 하기에 시간복잡도를 O(N+M)으로 낮출 수 있을까 2. KMP알고리즘을 이해 하기에 앞서 알아야 하는것 (1)..

오늘 백준 Brute-force 알고리즘에 관련한 문제를 풀다 한번 정리 하고 싶다는 생각이 들어 글을 작성한다. 아래 글은 reference에도 남기겠지만, 'Do it! 자료구조와 함께 배우는 알고리즘 입문'을 정리한 글이다. 1. 브루트-포스(Brute-force)법 완전탐색 알고리즘이다. 모든 경우의 수를 탐색하면서, 요구 조건에 충족되는 결과만을 가져 온다. 선형 검색을 확장한 알고리즘이다. 예시로 문자열을 검색하는 알고리즘을 들어 보자. 문자열에 특정 문자열이 들어 있는지 조사하고, 들어 있따면 그 위치 index 값을 반환하는 프로그램을 작성한다 생각해보자. 텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트포스법을 이용해 검색하는 순서는 다음과 같다. (1) 문자열의 첫 문자 'A..

방법 1. N 보다 작은 자연수들로 모두 나눠본다. 임의의 수 N이 1과 N을 제외한 다른 수를 약수로 갖는 다면, 그 수는 소수가 아니고, 그렇지 않다면 소수이다. public class PrimeNumber { public static boolean isPrime(int num){ if (num