접근
팰린드롬 문자열의 전체 분할 갯수의 최솟값을 구하는 문제이다.
문자열의 최대 길이는 2,500자이기에 인덱스 연산으로 팰린드롬 분할 전체를 구해내는 것은 힘들어보였다. 사실 이 문제는 DP 문제인데. 팰린드롬 공부를 좀 더 자세히 해보고싶어서 찾아보다, Manacher's Algorithm을 알게 되었다. 그래서 팰린드롬을 공부하는겸 Manacher's Algorithm을 이용해서 한번 문제를 해결해봤다.
해결
Manacher's Algorithm
Manacher씨가 개발한 Longest Palindromic Substring을 $ O(n) $ 의 시간복잡도로 찾는 엄청난 알고리즘이다.
이 문제를 해결하면서 아래의 링크들을 참고했다.
Longest palindromic substring - Wikipedia
From Wikipedia, the free encyclopedia Computer science problem In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palin
en.wikipedia.org
[알고리즘] Manacher’s Algorithm - 마나커(마나허) 알고리즘
어떤 문자열에서 팰린드롬의 개수와 위치를 찾는 알고리즘인 "Manacher's Algorithm"에 ...
blog.naver.com
[BAE/<JOON> 문제풀이] 1509. 팰린드롬 분할
www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}
steins-gate.tistory.com
위의 슈테인-게이트님 덕분에 마지막에 점화식을 작성하는 부분에 시간이 너무 많이 들어서 참고해서 해결할 수 있었다.
Manacher's Algorithm은 팰린드롬의 부분문자열을 가장 길게 갖도록 업데이트해 나가는 일종의 동적프로그래밍과 느낌이 비슷하다.
예를들어 "bananas" 라는 문자열에서 나올 수 있는 팰린드롬 부분문자열은 무엇이 있을까? 1글자인 문자를 제외하고, "ana", "nan", "ana", "anana" 등이 있을 수 있다. 근데 우리가 맨앞에서부터 순차탐색을 진행한다면, 팰린드롬을 이루는 문자열이 최대가 되지 않고, 분할이 이상하게 될 수 있다. 그렇기 때문에 전체 팰린드롬인 문자열을 체크해나가면서, 가장 긴 팰린드롬 부분문자열을 갖도록 해줘야한다.
그 과정을 어떻게 수행하는지 한번 살펴보자.
가장 맨 위의 위키백과 레퍼런스에 보면, Manacher's 보단 느린 알고리즘의 의사코드가 있다. 바로 Manacher's로 들어가면, 너무 어렵기 때문에(내가 이해하는데 시간이 너무 들었다...) 조금 더 느린 의사코드를 해석하면서 한번 시작해보자.
일단 스포를 조금 하자면, Manacher's Algorithm은 홀수길이의 문자열에서 대칭성을 이루는 것을 체크하도록 수행하기 때문에 짝수길이의 문자열은 홀수길이로 만들어줘야한다.
그 방법으로 짝수길이의 문자열은 아래와 같은 위치에 해당 문자열에 쓰이지 않는 특수문자('@', '#', '|' 등)을 추가해줘야한다.($ N = 2n $ -> $ N` = 2n(original) + (2n+1)(fake char numbers) = 4n+1(odd Numbers) $
- 문자열의 양 끝
- 문자열 사이
Slower Algorithm
Longest_Palindrome_SLOW(string S, string S') {
// S' : S에 가짜 문자(여기선 '|')가 삽입된 문자열
// S'의 각각의 문자를 중심으로 하는 가장 긴 팰린드롬 반지름을 저장해두기 위한 array
// note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1
array PalindromeRadii = [0,...,0]
Center = 0
while Center < length(S') {
// (Center-Radius) ~ (Center+Radius)부터 가장 긴 팰린드롬 반지름(Radius) 확인
Radius = 0
while Center-(Radius + 1) >= 0 and
Center+(Radius + 1) < length(S') and
S'[Center-(Radius + 1)] = S'[Center+(Radius + 1)] {
Radius = Radius + 1 // 문자가 대칭이라면, 반지름 계속 확장
}
// 가장 긴 반지름을 위에 선언한 array에 저장
PalindromeRadii[Center] = Radius
Center = Center + 1 // 그 다음 중심점 확인
}
// 가장 긴 팰린드롬의 길이는 PalindromeRadii의 Max값을 구하면 된다.
// 만약 S'[i] == '|', PalindromeRadii[i]이 짝수이면, PalindromeRadii[i]에 1씩 더해줄 수 있는데, 이는 각 테두리에 '|' 를 추가로 삽입한 것과 같다.
// 문자열S'에서 '|'에 대해 나온 팰린드롬은 문자열 S에서 짝수 팰린드롬에 대응된다는걸 기억해야한다.
// 만약 S'[i] != '|', PalindromeRaii[i]이 홀수면, 홀수 팰린드롬에 대응한다.
// 이 경우엔, 중심에 대한 팰린드롬의 길이는 x=PalindromeRaii[i]이 된다.
// 우리가 중심에 대해서 양쪽에 (x-1)/2 개의 문자를 갖고 있고,
// 대칭의 중심이 되는 문자 1개를 더해서 (x-1)/2*2+1=x 이 길이가 된다.
longest_palindrome_in_S = max(PalindromeRadii)
return longest_palindrome_in_S
}위키백과에 있는 의사 코드의 주석을 해석해서 작성해봤다.
의사코드가 복잡하지 않으니 쉽게 이해할 수 있을 것이라 생각한다.
문자열을 전체 탐색하면서, 해당 문자를 중심으로 하는 팰린드롬 반지름을 모두 구한다. 저장해놓은 모든 반지름의 길이에서 가장 긴 길이를 찾는다.
바깥쪽 반복문이 $ O(N) $, 안쪽 반복문이 $ O(N/2) $의 시간복잡도를 가지면서, 전체 알고리즘의 시간복잡도는 $ O(N^2) $ 이 된다. 이 방법이 Manacher's Algorithm의 기본적인 내용과 동일하다. 이제 Manacher's Algorithm을 통해 어떻게 효율적으로 개선했는지 보자.
Manacher's Algorithm
Longest_Palindrome(string S, string S') {
// S' : S에 가짜 문자(여기선 '|')가 삽입된 문자열
// S'의 각각의 문자를 중심으로 하는 가장 긴 팰린드롬 반지름을 저장해두기 위한 array
// note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1
array PalindromeRadii = [0,...,0]
Center = 0
Radius = 0
while Center < length(S') {
// 반복문의 시작에, Radius는 이미 '가장 긴 radius'의 하한으로 설정해둔다.
// 처음 반복에서는 Radius가 0이지만, 반복이 진행될수록 더 높아질 수 있다.
// (Center-Radius) ~ (Center+Radius) 까지의 가장 긴 팰린드롬 길이를 구한다.
while Center < length(S') and
Center+(Radius+1) < length(S') and
S'[Center-(Radius+1)] = S'[Center+(Radius+1)] { // 위의 의사코드랑 구하는 과정은 동일
Radius = Radius+1
}
// 가장 긴 팰린드롬 반지름을 위의 array에 저장
PalindromeRadii[Center] = Radius
// 아래 코드는, Center를 증가시킨다.
// 미리 계산된 값이 있다면, 재사용할 수 있다.
// 또한 Radius는 0보다 클 수 있다.
OldCenter = Center
OldRadius = Radius
Center = Center+1
// 아래 반복문이 끝나게 되면, Radius의 기본값은 0이 된다.
Radius = 0
while Center <= OldCenter + OldRadius {
// Center는 오래된 팰린드롬안에 있고, 팰린드롬 안에 있는 모든 문자들은 Center에 대해 "반사된" 문자를 가지고 있다.
// 그렇기 때문에 우리는 Center의 반사된지점에 대해서 미리 계산된 데이터를 사용할 수 있다.
MirroredCenter = OldCenter - (Center - OldCenter) // 현재 Center의 OldCenter에 대해 반사된 지점
MaxMirroredRadius = OldCenter + OldRadius - Center // 반사된 지점에 대한 최대 Radius
if PalindromeRadii[MirroredCenter] < MaxMirroredRadius { // 만약 MirroredCenter의 팰린드롬 반지름이 MaxMirroredRadius보다 작다면,
// MirroredCenter의 팰린드롬은 OldCenter의 팰린드롬에 전체가 포함된다.
// 그래서, MirroredCenter와 Center는 동일한 사이즈의 팰린드롬을 갖는다.
PalindromeRadii[Center] = PalindromeRadii[MirroredCenter]
Center = Center+1
} else if PalindromeRadii[MirroredCenter] > MaxMirroredRadius { // 만약 MirroredCenter의 저장된 Radius가 MaxMirroredRadius보다 크면
// MirroredCenter의 팰린드롬이 OldCenter의 팰린드롬을 넘어 확장될 수 있다는 것이다.
// Center의 팰린드롬은 OldCenter의 팰린드롬의 가장자리에서 끝나야만 하지만, 그렇지 않으면 OldCenter의 팰린드롬이 더 커질 수 있다.
PalindromeRadii[Center] = MaxMirroredRadius
Center = Center+1
} else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius
// MirroredCenter의 팰린드롬이 완벽히 OldCenter의 가장자리에서 끝난다면,
// Center의 팰린드롬은 더 커질 수 있다. 그렇기에 Radius의 최소 크기를 MirroredCenter의
// 최댓값으로 설정하여, 불필요한 체크를 하지않도록 만든다.
Radius = MaxMirroredRadius
break
}
}
}
// 팰린드롬의 사이즈는 2 * 반지름이 되어야한다. 그러나 우리는 위에서 도입한 가짜문자를 기준으로 양쪽으로
// 반지름을 고려했기때문에, 실제로는 2 * (Radius / 2)와 상응한다.
// 그렇기에 우리가 저장해둔 PalindromeRadii Array의 Radius 값과 상응한다.
longest_palindrome_in_S = max(PalindromeRadii)
return longest_palindrome_in_S
}
위의 코드에 대한 설명을 그림을 통해 예시로 수행해보자.
예시 단어는 "bananas"다.
짝수 길이라고 한다면, 가짜 문자(@, #, | 등)을 넣어서 수행해야하지만, 일단 그냥 수행해보겠다.
Center=0
'b'문자 양쪽으로는 대칭이 되는 문자가 없기 때문에, Radius가 0이 된다.
OldCenter = 0
OldRadius = 0
Center = 1
Center <= OldCenter + OldRadius 조건을 만족하지 않기 때문에, 그에 따라 나머지 수정이 없다.
Center=1
'a'문자 양쪽으로도 대칭이 되는 문자가 없기 때문에, Radius가 0이 된다.
OldCenter = 1
OldRadius = 0
Center = 2
Center <= OldCenter + OldRadius 조건을 만족하지 않기 때문에, 그에 따라 나머지 수정이 없다.
Center=2
'n'문자 양쪽으로는 대칭이 되는 문자가 하나 있기 때문에, Radius가 1이 된다.
그에 따라 OldRadius=1이 된다.
이제 Center=3, OldCenter=2, OldRadius=1로 Center <= OldCenter + OldRadius가 조건인 While문이 수행될 수 있다.
MirroredCenter = 2 - (3 - 2) = 1로 Center 3의 OldCenter 2 에 대한 반사 지점이다.
MaxMirroredRadius = 2 + 1 - 3 = 0 반사 지점에 대한 최대 팰린드롬 반지름은 현재는 0이다.
PalindromeRadii[MirroredCenter=1] = 0, MaxMirroredRadius = 0 으로 두 값은 같기 때문에, MirroredCenter의 팰린드롬이 OldCenter의 팰린드롬에서 완벽히 끝난다는 것을 알 수 있다. 그렇기에 Radius = MaxMirroredRadius로 설정하고, 반복문을 탈출한다. 어차피 0이라 여기서는 무슨말인지 잘 이해가 안될 수 있다.
Center=3
이번 'a'문자는 양쪽으로 대칭이 되는 문자가 2개나 있기 때문에, Radius가 2가 된다.
그에 따라 OldRadius = 2가 된다.
Center = 4
OldCenter = 3
OldRadius = 2
Center <= OldCenter + OldRadius 가 만족하기 때문에, 반복문이 시작된다.
MirroredCenter = 3 - (4 - 3) = 2, Center 4의 OldCenter 3에 대한 반사 지점은 2
MaxMirroredRadius = 3 + 2 - 4 = 1, 반사 지점의 최대 Radius는 1
PalindromeRadii[MirroredCenter=2] = 1, MaxMirroredRadius = 1로, 완벽히 가장자리에서 끝나기에,
Radius = MaxMirroredRaidus=1 로 수정해주고 반복문을 마친다.
Center=4, 5
현재 Radius = 1로 초기화가 되어 있다.
앞서 수행한 반복문에서, 그 다음 탐색을 위한 초기화를 진행해줬기에 Radius=0부터 다 탐색할 필요가 없고, 1까지는 팰린드롬이 보장된다는 의미이기에, 그 이후부터 탐색하는 것이라고 생각하면 된다.
Center = 5
OldCenter = 4
OldRadius = 1
Center <= OldCenter + OldRadius가 만족하기 때문에, 반복문이 시작된다.
MirroredCenter = 4 - (5 - 4) = 3, Center 5의 OldCenter 4에 대한 반사 지점은 3
MaxMirroredRadius = 4 + 1 - 5 = 0, 반사 지점의 최대 Radius는 0
PalindromeRadii[MirroredCenter=3] = 2 > MaxMirroredRadius = 0으로, 반사 지점의 팰린드롬 반지름이 OldCenter를 넘어서 더 커질 수 있다는 것이다.
그럼으로 현재 탐색 중인 PalindromeRadii[Center=5] = MaxMirroredRadius=0 으로 설정한다.
그 다음 Center는 범위를 넘어가기에 반복문을 중지한다.
Center=6
Center = 7
OldCenter = 6
OldRadius = 0
Center <= OldCenter + OldRadius 가 만족하지 않기 때문에, 이대로 반복문을 수행하지 않고 알고리즘을 종료한다.
장황하게 설명을 진행한 것 같은데, 결론적으로는 팰린드롬의 성질을 이용해서 해당 문자를 중심으로 가장 긴 반지름이 될 수 있는 값을 미리 저장해두고, 그 다음 탐색 때 사용함으로써 더욱 효율적으로 팰린드롬 길이를 구할 수 있는 것이다.
위키백과의 코드가 너무 복잡해보일 수 있다. 그렇다면 Ref 2번의 런타임 에러님의 블로그에 들어가서 더욱 간결히 표현된 코드를 참고해보자. 나도 그 형태로 구현했다.
또한 위에선 짝수 문자열만 가짜 문자를 넣어서 팰린드롬 길이를 구하고 했지만, 이 문제를 해결할 땐 그냥 다 넣어서 구해야 한다. 왜냐면, 중간에 등장하는 짝수 팰린드롬(A[BB]CD)이 존재할 수 있기에, 넣어서 구해줘야한다.
DP를 이용한 해결법도 구성해봐야 할 것 같다.
코드
sentence = input()
len_S = len(sentence)
mod_sentence = "@"
for i, s in enumerate(sentence):
mod_sentence += s
mod_sentence += "@"
sentence = mod_sentence
len_S = len(sentence)
P = [0] * len_S # i번째 문자 중심 가장 긴 팰린드롬 반지름 크기
r = 0 # i-1단계 까지의 모든 팰린드롬의 끝나는 인덱스 중 가장 큰 값
c = 0 # i-1단계 까지 r의 값이 최대가 되게 하는 중심 인덱스
for i in range(len_S):
if r < i: # i-1단계 까지 팰린드롬이 끝나는 인덱스 중 가장 큰 값이 현재 탐색하려는 인덱스보다 작다면, 현재(i번쨰)문자 중심 가장 긴 팰린드롬 반지름 크기 = 0 -> 현재 문자는 이전에 탐색한 팰린드롬에 포함되지 않는다는 거니까, 현재 문자 중심 팰린드롬 반지름 크기는 0이 된다.
P[i] = 0
else: # i-1단계 까지 팰린드롬 끝나는 인덱스 중 가장 큰 값이 현재 탐색 인덱스를 넘어간다면, 이전 팰린드롬에 현재 문자가 속한다는거임
P[i] = min(P[2*c - i], r-i) # i의 이전 팰린드롬의 중심 인덱스에 대해서 대칭인 곳에서의 가장 긴 팰린드롬 반지름 크기와, 이전의 팰린드롬이 끝나는 인덱스 중 가장 큰 값에서 현재 인덱스를 뺀 위치까지 중 더 작은 값을 현재 인덱스에서의 초기 반지름 크기로 지정한다. => 진짜 어려움 이렇게 하는 이유에 대한 이해는 Ref: https://m.blog.naver.com/jqkt15/222108415284 확인
while (i - P[i] - 1 >= 0 and i + P[i] + 1 < len_S) and (sentence[i - P[i] -1] == sentence[i + P[i] + 1]): # 현재 문자에 대해서 최대 팰린드롬 반지름 탐색
P[i] += 1
if r < i + P[i]: # i-1단계 까지 팰린드롬이 끝나는 인덱스 중 가장 큰 값이, 현재보다 더 작다면, 업데이트 해줘야함
r = i + P[i] # 팰린드롬이 끝나는 인덱스 업데이트
c = i # 더 큰 반지름이 나오는 중심 인덱스 업데이트
dp = [float('inf')] * len_S
dp[0] = 0
for t in range(1, len_S):
if sentence[t] == "@" and P[t] == 0:
dp[t] = dp[t-1]
continue
dp[t] = dp[t] if dp[t] < dp[t-1] + 1 else dp[t-1] + 1
for j in range(1, P[t]+1):
st = t - j -1
ed = t + j
if st < 0:
dp[ed] = 1
continue
dp[ed] = dp[ed] if dp[ed] < dp[st] + 1 else dp[st] + 1
print(dp[len_S-1])'알고리즘(Algorithm)' 카테고리의 다른 글
| [BOJ] 1562번 : 계단 수(DP, BitMask) (1) | 2023.12.31 |
|---|---|
| [BOJ] 1208번 : 부분수열의 합 2(중간에서 만나기, 이분 탐색) (1) | 2023.12.29 |
| [BOJ] 1202번 : 보석 도둑(정렬, 우선순위 큐, 그리디) (0) | 2023.12.22 |
| [BOJ] 1197번 : 최소 스패닝 트리(Kruskal) (0) | 2023.12.21 |
| [BOJ] 1005번 : ACM Craft(위상 정렬, dp) (1) | 2023.12.20 |