[동적계획법] Longest Palindrome SubString

동적계획법(Dynamic Programing)이란?

 

복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법

동적계획법은 분할된 모든 경우의 수를 검토한다. 

중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 

 

 

Longest Palindrome SubString

 

예제) 문자 수열이 주어질 때, 대칭을 이루는 부분수열 중 최대길이를 구하라. 

 

[ b, a, a, b, c ]

 

 

Palindrome이란, 정방향으로 읽어도 역방향으로 읽어도 같은 배열을 의미한다. b, a, a, b 는 → 으로 읽어도 ← 으로 읽어도 같다. 이런 성질을 가진 부분수열 중 최대길이를 구해야 한다. 

 

Palindrome은 몇가지 특징을 가진다.

 

1) Prlindrome 성질을 가진 가장 최소길이는 문자 한 개이다. 

2) Parindrome 부분수열의 부분수열도 Palindrome 성질을 가진다.

 

 

큰 단위에서 작은 단위로 분할되어도 같은 성질을 띄는 특징은 동적계획법의 Top-Down 방식과 어울린다. 그러나 어떤 방식으로 분할을 시작해야 할지 감이 잡히지 않는다. 이럴 때는 Bottom-Up 방식으로 작은 단위부터 올라가는 것도 방법이다. 

 

Palindrome 성질을 파악하려면 양 끝을 비교해야한다. 그래서 포인터가 두 개 필요한다. 

 

1) from 포인터

2) to 포인터

 

from포인터와 to포인터가 동일한 값을 가리킨다면 Palindrome 성질을 띈다고 할 수 있다. 모든 경우의 수를 따져보기 위해 이차행렬을 그려보자.

 

 

1)  행렬 안 값은 Parlindrom의 길이를 의미한다. 문자열 한 개은 Parlindrom 성질을 갖으므로 대각선은 모두 1을 갖는다.

 

 

 

2) From 포인터와 To 포인터가 가리키는 값이 '동일'해야 Parlindrom이라 할 수 있다. 

 

 

ba, aa, ab, bc 중 aa만이 From 포인터와 To 포인터가 가리키는 값이 동일하므로 Parlindrom하다. From 포인터과 To 포인터가 가리키는 문자를 합쳐 2가 된다. 

 

 

3) 문자열이 3개 일 때, From 포인터와 To 포인터가 가리키는 값이 '동일'해야 Parlindrom이라 할 수 있다. 

 

 

baa나 aab나 abc는 모두 Parlindrom 하지 않는다. 

 

 

4) 문자열이 4개 일 때, From 포인터와 To 포인터가 가리키는 값이 '동일'해야 Parlindrom이라 할 수 있다.

 

 

 

b a a b 는 a a라는 Parlindrome 부분 문자열을 갖는다. From과 To가 가리키는 문자 2개와 a a의 문자열 길이 2를 합쳐서 총 4가 된다. 

 

5) b a a b c 는 From과 To과 동일하지 않으니 Palindrom이 아니다. 

 

 

 

 

대각선 반대 방향은 결과가 동일하므로 생략한다. 길이가 가장 긴 부분 문자열은 4이다. From포인터가 0이고 To포인터가 3이다. 그러므로 [ b, a, a, b ]가 가장 긴 부분수열이 된다. 

 

 

---

 

참고자료