밤이 블로그

BOJ#1509 팰린드롬 분할 * 문제https://www.acmicpc.net/problem/1509 * 풀이- Manacher 알고리즘을 통해 임의의 범위의 문자열이 팰린드롬인지 구한다. - dp[i] : 0 ~ i 범위의 문자열을 팰린드롬 분할할 때 최소 분할 수 j ~ i 범위 문자열이 팰린드롬일 때, dp[i] = min(dp[i], dp[j-1] + 1)(여기서 j는 0 부터 i 까지) dp[0] = 1이고 -> dp[1] -> dp[2] -> ... -> dp[N-1]을 차례대로 구한다 * 나의 코드https://github.com/stack07142/BOJ/blob/d4b527b666ba54f7f53c1128f5a1523cb261d2b9/BOJ%231509/src/Main.java impo..

BOJ#10942 팰린드롬? * 문제https://www.acmicpc.net/problem/10942 * 풀이 문자열 중에서 팰린드롬에 대하여 지금 공부할지 아니면 나중에 공부할지 고민했습니다만..(알고리즘 대회가 아니면 별로 쓸 일이 없기 때문에) 간단히 O(N^2) 풀이와 O(N)풀이에 대해 공부해 보았습니다. 완벽히 이해한 상태가 아니기 때문에 설명은 나중에 추가하도록 하겠습니다.팰린드롬은 너무 어렵습니다.. 팰린드롬 공부 링크 : http://stack07142.tistory.com/128 * 나의 코드 O(N), Manacher's Algorithm - 어느 한 원소를 기준으로 좌/우로 넓혀가면서 검사 -> N이 홀수인 경우에는 문제없지만, N이 짝수인 경우에는 문제가 생김 -> 일괄적으로 2..

Manacher's Algorithm #1 : https://algospot.com/wiki/read/Manacher's_algorithm#2 : http://www.ideserve.co.in/learn/longest-palindromic-substring-manachers-algorithm 알고리즘 설명은 위 출처에 잘 되어 있습니다.- Time Complexity : O(n)- Space Complexity : O(n) * 관련 문제BOJ#10942 팰린드롬? https://www.acmicpc.net/problem/10942 * 코드 public class Manacher { public Manacher(String s) { char[] T = new char[s.length()*2 + 3]; T[..