안녕하세요. 오랜만에 문어체로 시작하는데요, 학부동안 배운 알고리즘 또는 배우지 못한 다양한 알고리즘 및 자료구조 이론을 정리해보려고 합니다. 설명 과정에 틀린 부분이나 추가해야할 부분이 있으면 언제든지 답글 달아주시면 감사하겠습니다. 오늘 배워볼 알고리즘은 KMP 알고리즘입니다. 문자 검색을 하는 가장 기본적인 방법은 부르트포스 방법으로 순차적으로 패턴을 비교하는 방법이지만 이 방법으로하면 패턴(M)이 길어지거나 문자(N)가 길어진다면 O(NM)의 시간복잡도를 가지게 됩니다. (여기서는 부르트포스 방법은 설명하지 않겠습니다.) KMP (Knuth Morris Partt Algorithm) 앞서 언급했듯이 부르트포스 방법으로 구현한다면 시간 복잡도는 O(NM)입니다. KMP 알고리즘은 부르트포스 알고리즘..
