* 본 포스팅은 인사이트 프로그래밍대회에서 배우는 알고리즘 문제해결 전략을 참조해서 작성되었습니다. 다음으로는 '비교해보지 않고도 알수 있는 것이 있다'는 KMP에 대해 알아보자. 이 알고리즘은 Knuth-Morris-Pratt 세 사람의 이름을 딴 알고리즘이다. Brute Force는 한 칸씩 이동하면서 비교하기 때문에 불필요한 비교 회수가 많이 발생하는데 이를 줄여서 연산을 빠르게 수행하는것이 K.M.P 알고리즘이다. KMP는 패턴 비교 과정에서 발생한 부분일치 문자열을 버리지 않고 건너뛸 수 있는 기회로 사용한다. 다음 그림을 살펴보자. 타겟과 패턴 문자열을 비교해보니 처음 비교에서 7번째에서 불일치가 발생했다. Brute Force방식을 적용한다면 이후 한 칸씩 패턴을 이동시켜보면서 타겟과의 일치..