접근 팰린드롬 문자열의 전체 분할 갯수의 최솟값을 구하는 문제이다. 문자열의 최대 길이는 2,500자이기에 인덱스 연산으로 팰린드롬 분할 전체를 구해내는 것은 힘들어보였다. 사실 이 문제는 DP 문제인데. 팰린드롬 공부를 좀 더 자세히 해보고싶어서 찾아보다, Manacher's Algorithm을 알게 되었다. 그래서 팰린드롬을 공부하는겸 Manacher's Algorithm을 이용해서 한번 문제를 해결해봤다. 해결 Manacher's Algorithm Manacher씨가 개발한 Longest Palindromic Substring을 $ O(n) $ 의 시간복잡도로 찾는 엄청난 알고리즘이다. 이 문제를 해결하면서 아래의 링크들을 참고했다. https://en.wikipedia.org/wiki/Longes..
