KMP 문제들 - 바킹독 문제집

링크: 설명 / 문제집

처음 KMP 알고리즘을 접했을 땐, 이해하는데 1시간 반이 걸렸습니다. 그래도 한번 공부해서 그런지, 오랜만에 봐도 이해하는데 30분밖에(?) 걸리지 않았네요. 되돌아서면 헷갈리는 알고리즘입니다.

 

문제 풀이

백준 16916번 부분 문자열, 백준 16172번 나는 친구가 적다 (Large)

 - 기본적인 KMP 활용 문제입니다. Python에서 in 연산이 O(N)이라, 코테에서 이런 유형의 문제가 나오면 python 및 C++의 library를 활용하는 것이 낫습니다.

 

백준 1786번 찾기

 - 기본 KMP 문제인데, 위 두 문제와 다르게 '부분 문자열이 몇 번 나왔으며, 시작 위치가 어디인지'를 구해야 합니다. KMP 알고리즘을 활용해서 풀었다면 위 문제에서 '부분 문자열을 찾은 순간' 끝내는 대신 횟수 및 위치를 기록한 후, j = f[j-1]로 바꿔주어 계속 진행하면 됩니다. 

 

백준 1893번 시저 암호

 - 원문 및 암호문을 알파벳이 아닌 '순서'로 저장합니다: 가령, A = "ABC", W = "ABC"라면 원문을 [0, 1, 2]와 같은 방식으로  저장합니다. 이후 원문을 0 ~ |A|-1번 shift하여, 원문이 암호문에 1번만 포함되는지 확인합니다.

 

백준 1305번 광고

 - 전체 문자열에서의 실패 함수 값 f(N-1)을 구하면, N - f(N-1)이 최소 길이가 됩니다.

 - 증명은 귀류법으로 할 수 있는 듯...?

 

백준 4354번 문자열 제곱

 - N - f(N-1)이 '반복될 수 있는 문자열의 최소 길이'가 됩니다.

 - 따라서, N이 N - f(N-1)로 나누어떨어지지 않거나 f(N-1) == 0 이라면 1, 나머지 경우는 N / (N - f(N-1))이 됩니다.

 

백준 11585번 속타는 저녁 메뉴

 - 이리저리 머리 굴려봤는데 잘 모르겠더라고요.

 - 그래서 찾아보니 회문에서 횟수를 찾으려면 찾는 문자열 s를 2배 늘려주어(즉, s+s) 거기서 KMP를 수행하면 된다고 합니다.

  - 보니까 유명한 테크닉인거 같더라고요. 역시 문제는 좀 풀다가 모르면 바로 찾아보는게 낫습니다.

 - 다만, 원문을 중복하여 세지 않도록 처리해줍니다. i의 범위를 2*|s|-1 미만에서만 찾으면 될 거예요.

 

백준 10266번 시계 사진들

 - 시계의 상태를 문자열로 어떻게 표현할지가 관건입니다.

 - 저는 시침의 거리 차이를 기록했는데, 이럴 경우 시침의 종류를 구분해버리기 때문에 안 됩니다.

 - 그래서 인터넷에서 찾아보니, 크기가 36만인 배열을 만들어, 시침이 있는 경우 1(or true 등...)을 저장하면 된다고 합니다.

 - 가령, 예제 입력 1의 '1 2 3 4 5 6'은 [0, 1, 1, 1, 1, 1, 1, 0, 0, ... , 0] 으로 저장할 수 있습니다.

 - 이후, 시계를 '돌려서 같은 걸 찾는다는 점'에서 위 문제랑 동일한 아이디어를 적용하면 됩니다.