MZ 개발자

이 문제는 I,O로 구성된 문자열 중 IOI 가 몇개 포함되어 있는지 갯수를 구하는 문제이다. 처음 단순 부르트포스 방식으로 접근했다면 당연히 만점을 받지 못했을 것이다. 서브테스크 1의 경우 N> s; solution(); } 다음은 KMP 알고리즘을 활용한 풀이이다. 자세한 알고리즘 설명은 여기를 확인하면 된다. 알고리즘 - KMP 안녕하세요. 오랜만에 문어체로 시작하는데요, 학부동안 배운 알고리즘 또는 배우지 못한 다양한 알고리즘 및 자료구조 이론을 정리해보려고 합니다. 설명 과정에 틀린 부분이나 추가해야할 부 devconf.tistory.com #include #include #include using namespace std; int n, m; string s; vector getSkipTabl..

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