목차
- 팔린드롬
- DP를 사용한 팔린드롬 찾기
- Manacher's Algorithm
1. 팔린드롬
우리나라 말로 하면 회문입니다.
'기러기'와 같이 앞뒤가 같은 단어를 뜻합니다.
2. DP를 사용한 핀란드롬 찾기
주어진 단어가 회문인지를 검사하는 것이 아닌 주어진 문자열에서 가능한 회문을 찾는 과정입니다.
지난 시간에서 살펴보았던 동적계획법(Dynamic Programming, DP)을 사용하여 회문을 찾는 과정을 보여드리겠습니다.
문자열은 arr라는 이름으로 저장합니다.
주어진 문자열의 크기를 n이라고 한다면, n * n크기의 boolean배열을 준비합니다.
DP[a][b] = a부터 b까지 확인할 때 회문이면 true 아니면 false
최종적으로 위와 같은 형태가 나타나게 됩니다.
다음으로 기본적인 작업이 필요합니다.
문자열의 크기가 1이라면 그 문자열은 회문입니다.
그렇기 때문에 아래와 같은 과정을 거칩니다.
for (int i = 1; i <= n; i++){
DP[i][i] = true;
}그리고 "aa"나 "bb"와 같은 문자열을 검사하기 위해 i 번째와 i + 1 번째 문자를 비교해 DP에 저장합니다.
for (int i = 1; i <= n - 1; i++){
if (arr[i] == arr[i + 1]) DP[i][i + 1] = true;
}길이가 1, 2인 회문은 다 찾았습니다.
3이상의 길이를 가진 문자열이 회문이기 위해선 아래와 같은 조건이 필요합니다.
- 문자열의 처음과 끝이 같아야한다.
- 처음과 끝을 제외한 가운데 문자열이 회문이여야 한다.
위 조건을 코드로 표현하자면 아래와 같이 표현할 수 있습니다.
for (int l = 2; l <= n - 1; l++){
for (int i = 1; i <= n - k; i++){
int j = i + k;
if (arr[i] == arr[j] && DP[i + 1][j - 1]) DP[i][j] = true;
}
}
"bananac"을 예시로 진행해 봅시다.
n은 7이되고, DP의 크기는 7 * 7이 됩니다.
길이 두개까지의 회문을 찾으면 아래와 같은 표가 완성됩니다.
길이 3이상의 회문을 찾는 과정을 진행하면 표가 다음과 같이 진행됩니다.
이런식으로 회문을 찾을 수 있습니다.
3. Manacher's Algorithm
팔린드롬으로 유명한 알고리즘입니다.
이 알고리즘을 진행하기 위해서 우선 배열 A를 만들어 주겠습니다.
A[i]는 i번째 문자를 중심으로 하는 회문의 반지름의 크기입니다.
(이 알고리즘에서는 i를 0부터 시작하겠습니다. A[0]를 사용합니다.)
여기선 지금부터 "bananac"을 예시로 설명하겠습니다.
int값 R, P를 준비합니다. 처음 값은 -1입니다.
1. i는 0부터 n - 1까지 진행됩니다.
2. 모든 j < i를 만족하는 j에 대하여 R = max(j + A[j])입니다. 이 때 max를 만족하는 j를 P라고 합니다.
3. i <= R 인지 여부에 따라 A[i]의 초깃값을 구할 수 있습니다.
3-1. i > R일 경우 A[i]는 0입니다.
3-2. i <= R의 경우 i는 p를 중심으로 하는 팔린드롬에 속한다는 이야기입니다. 이 때 i에 대한 대칭점 i'를 구합니다. (i' = 2 * P - i) 이 때 A[i] = min(R - i, A[i'])입니다.
4. A[i]의 초깃값부터 arr[i - A[i]] 과 arr[i + A[i]]가 같을 때까지 A[i]를 증가시킵니다. 이후 i를 증시킵니다.
이러한 과정을 거친 후 아래와 표를 얻을 수 있습니다.
4. 두 알고리즘의 차이점
첫번째 알고리즘의 경우 시간복잡도는 O(N^2)입니다.
이러한 경우 N의 값이 커지면 비효율적입니다.
N = 100000만 되어도 1억을 넘기게됩니다.
두번째 알고리즘의 경우 시간복잡도는 O(N)입니다.
첫번째 알고리즘과 확연한 차이가 나기 때문에 많은 사람들이 회문을 찾을 때 manacher's algorithm을 사용합니다.
