글쓰는 개발자

알고리즘 카테고리의 첫 포스팅은, KMP 알고리즘이다. Knuth, Morris, Pratt 이라는 세 사람의 첫 글자를 따선 만든 알고리즘인데, 쉽게 정의하자면 서로 다른 문자열을 비교하는 알고리즘이라고 보면 된다. 예를 들어, 'aaaabbccaab' 라는 문자열이 있을때, 'aab'라는 문자열이 몇번째 인덱스에 있는지 찾고자한다면 어떻게 찾아야 할까? 당장 떠오르는 방법은 아마도 'aaaabbccaab'의 첫번째글자와 'aab'의 첫 번째 글자를 비교해서 동일하면, 각각 두번째 글자를 비교하고 또 동일하면 세번째 글자를 비교하고. 만약 세번째에서 동일하지 않다면, 비교의 시작점이었던 'aaaabbccaab'의 두번째 글자로 돌아와서, 다시 'aab'의 첫 번째 글자와 비교를 할 것이다. 이 방법의 ..