LCS(Longest common subsequence; 최장 공통 부분 수열)
DP를 활용하는 알고리즘입니다.
예를 들어
ACAYKP
CAPCAK
두 문자열의 가장 긴 공통부분 수열을 구하는 문제입니다.
|
A |
C |
A |
Y |
K |
P |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
0 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| P |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
0 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| K |
0 |
0 |
0 |
0 |
0 |
0 |
| 다음과 같은 표를 만듭니다. |
|
|
|
|
|
|
세로줄을 기준으로 연산을 진행하겠습니다.
|
A |
C |
A |
Y |
K |
P |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| P |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
0 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| K |
0 |
0 |
0 |
0 |
0 |
0 |
같은 문자가 있다면, 왼쪽 대각선 위의 값에 +1한 값으로 바꿔 주겠습니다.
해당 연산을 계속 진행하면 다음과 같습니다.
|
A |
C |
A |
Y |
K |
P |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| P |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
0 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| K |
0 |
0 |
0 |
0 |
0 |
0 |
|
A |
C |
A |
Y |
K |
P |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
1 |
0 |
2 |
0 |
0 |
0 |
| P |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
0 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| K |
0 |
0 |
0 |
0 |
0 |
0 |
|
A |
C |
A |
Y |
K |
P |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
1 |
0 |
2 |
0 |
0 |
0 |
| P |
0 |
0 |
0 |
0 |
0 |
1 |
| C |
0 |
0 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| K |
0 |
0 |
0 |
0 |
0 |
0 |
|
A |
C |
A |
Y |
K |
P |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
1 |
0 |
2 |
0 |
0 |
0 |
| P |
0 |
0 |
0 |
0 |
0 |
1 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
| K |
0 |
0 |
0 |
0 |
0 |
0 |
|
A |
C |
A |
Y |
K |
P |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
1 |
0 |
2 |
0 |
0 |
0 |
| P |
0 |
0 |
0 |
0 |
0 |
1 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
2 |
0 |
0 |
0 |
| K |
0 |
0 |
0 |
0 |
0 |
0 |
|
A |
C |
A |
Y |
K |
P |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
1 |
0 |
2 |
0 |
0 |
0 |
| P |
0 |
0 |
0 |
0 |
0 |
1 |
| C |
0 |
1 |
0 |
0 |
0 |
0 |
| A |
0 |
0 |
2 |
0 |
0 |
0 |
| K |
0 |
0 |
0 |
0 |
1 |
0 |
따라서 가장 긴 공통 문자열의 길이는 2라는 사실을 알 수 있습니다.