[알고리즘/정수론] 에라토스테네스의 체 - C++
에라토스테네스의 체 Sieve of Eratosthenes 소수를 판정하기 위한 기본적인 정수론 알고리즘이다. 2부터 90까지의 수 중 소수를 구한다고 해 보자. (1은 소수가 될 수 없으므로 제외) 2를 확인하였을 때, 2는 소수이므로 이후 2의 배수는 모두 소수가 아닌 것으로 처리해준다. 3을 확인하였을 때, 3은 소수이므로 이후 3의 배수는 모두 소수가 아닌 것으로 처리해준다. 4를 확인하였을 때, 4는 이미 소수가 아닌 것으로 표시가 되어있으므로, 건너뛰고 5를 확인. 5를 확인하였을 때, 5는 소수이므로 이후 5의 배수는 모두 소수가 아닌 것으로 처리해준다. 모두 진행하게 되면 이와 같이 소수만 남게 된다. 이에 대한 코드는 아래와 같다. bool prime[101] = {false}; // 1..
KMP 알고리즘 (Knuth-Morris-Pratt Algorithm) KMP 알고리즘 (수행시간 : O(N)) : 문자열 탐색에 있어 겹치는 부분을 미리 탐색해 불필요한 검색을 하지 않도록 점프시키는 알고리즘. 일반적인 문자열 탐색 알고리즘을 사용하는 경우, 글의 길이가 M, 패턴의 길이가 N이라고 하면 수행시간은 O(MN)이 된다. 이때 어떻게 하면 이러한 중복 문자열 탐색을 줄일 수 있을까 하여 나온 방법이 KMP 알고리즘이다. 수행 원리 문자열을 탐색할 때 겹치는 부분이 있는데, 일반적인 탐색의 경우 이를 무시하고 다시 처음부터 탐색을 진행하게 된다. KMP는 미리 탐색한 이러한 겹치는 문자열을 어떻게 활용할지를 고안하여 만들어낸 알고리즘이다. 우리는 접두사(Prefix)와 접미사(Suffix)의..