프로그래민👨‍💻

KMP를 활용하는 문자열 문제이다. 이 문제를 맨처음엔 모든 문자열 패턴을 구해서 입력문자열에서 패턴을 찾는 방식으로 생각해보았다. 하지만 문자열 최대 길이가 5000이기에 모든 패턴을 구하는건 불가능했다. 그래서 생각해보니 KMP를 사용할때 접두사와 접미사를 이용하여 패턴의 길이를 구하는 pi를 활용하는 방안을 떠올렸다. 이것을 이용하면 2번이상 등자하며 최장길이를 구할 수 있게 되기에 적용해보았다. 단, abbcbba와 같은 패턴에서는 bb를 못찾기에 이것을 위해선 bbcbba를 확인해야하는 반례가 생긴다. 그래서 입력문자열의 앞에서부터 하나씩 줄여주며 pi를 구하는 방식으로 풀어보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..

2018 카카오 블라인드 채용 문제이다. 이문제는 문자열 찾기문제로 KMP를 사용하여 풀었다. 하지만 전처리를 해줘야할것이 많았다. 나는 일단 #을 처리하리 위해 translate라는 함수를 만들어 #이 붙은 문자들을 새로운 문자로 아예바꾸어서 문제를 해결하였다. 꼼꼼한 전처리와 KMP를 다룰 줄 알면 쉬운 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 ..

이문제는 문자열 패턴찾기 문제이다. 단순히 일반적으로 찾으면 시간초과가 생겨서 풀수 없는 문제이다. 그렇기에 대표적인 문자열 알고리즘의 대표적인 KMP를 사용하였다. KMP의 알고리즘의 간단한 원리는 일단 패턴문자열에 대해 해당 문자열의 위치마다에서 접두사와 접미사가 최대로 같아지는 것을 카운팅해주는 배열을 만든다음, 그 배열을 이용하여 접두사와 접미사를 확인해가며 일정간격을 건너뛰어 시간복잡도가 거의 O(n)에 가깝도록 해결하는 방식이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53..