워드프로세서등을 사용하다가 Ctrl + F 를 이용해서 특정 키워드 즉 문자열을 검색해본 경험이 모두들 한번씩은 있을 것이다. 이때 내가 원하는 문자열을 찾는 것을 문자열 패턴 매칭이라고 한다. 미리 밝혀두지만 일상 생활에서는 아주 유용하게 사용되는 기능이지만 APS에서는 한정된 알고리즘을 알면 대부분 풀리는 문제들이기 때문에 출제의 빈도는 매우 낮은 편이고 알고리즘 복잡도는 높다. 바쁜 경우는 생략하는 것도 좋은 선택이다. 문자열 패턴 매칭의 방법은 크게 4가지 정도가 활용된다. - Brute Force - Rabin-Karp - K.M.P - Boyer Moore 이중에 Brute Force, Rabin-Karp, KMP 3가지 방법에 대해서 알아보자. 이번 포스트에서는 각 방법을 사용해보면서 백준의..
문자열 패턴 매칭 1 - Brute Force
워드프로세서등을 사용하다가 Ctrl + F 를 이용해서 특정 키워드 즉 문자열을 검색해본 경험이 모두들 한번씩은 있을 것이다. 이때 내가 원하는 문자열을 찾는 것을 문자열 패턴 매칭이라고 한다. 미리 밝혀두지만 일상 생활에서는 아주 유용하게 사용되는 기능이지만 APS에서는 한정된 알고리즘을 알면 대부분 풀리는 문제들이기 때문에 출제의 빈도는 매우 낮은 편이고 알고리즘 복잡도는 높다. 바쁜 경우는 생략하는 것도 좋은 선택이다. 문자열 패턴 매칭의 방법은 크게 4가지 정도가 활용된다. - Brute Force - Rabin-Karp - K.M.P - Boyer Moore 이중에 Brute Force, Rabin-Karp, KMP 3가지 방법에 대해서 알아보자. 이번 포스트에서는 각 방법을 사용해보면서 백준의..
2020.02.28