Rabin Karp1 12. String Match(KPM, Rabin-Karp, Palindrome) 0. 시작하기전에 - 한동안 알고리즘 공부를 하며 깨달은게 있다. - 알고리즘을 얼마나 외우고 있느냐는 코딩테스트에서는 중요하지 않다는 점이다. - 결국 이론적인 이해도와 지식에 대한 소화시간을 충분히 갖고, 이를 기반으로 응용적인 사고가 가능하냐는 부분이 가장 중요하다. - 그러므로 코드를 외우려 노력하지말고, 그 안의 규칙성과 논리를 이해하기 위해 더 시간을 투자하기를 바란다. 1. String Match - 문자열을 탐색하는 방법론이다. - 대표적으로 KMP 알고리즘과 Rolling Hash를 사용하여 구현한 Rabin Karp 알고리즘이 있다. - 일반적으로 String Match 알고리즘은 O(n)의 시간복잡도를 갖는다. a) 시간복잡도 - 문자열 탐색은 다음과 같은 과정을 거친다. string.. 2021. 10. 20. 이전 1 다음
