[C, python] 백준 9251번 : LCS

문제

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

 

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

 

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

풀이

 

LCS 문제는 두 수열을 그림과 같이 2차원 배열을 만들어서 해결할 수 있습니다.

 

 

먼저 두 수열을 0번째 행과 열에 차례로 넣어줍니다.

그 다하음 반복문을 통해 배열의 모든 칸을 채워주어야 합니다.  원래 수열보다 작은 수열끼리의 최장공통 부분열의 길이를 배열에 저장해놓고 수열을 원래대로 확장해가며 최장공통 부분열의 길이를 구하는 방식으로 문제를 해결할 수 있습니다.

 

이 문제에서는 A와 C가 서로 다른 문자라 (1,1)은 0이 되고 그 후 C와 C가 같은 문자여서 (1,2)는 1, 이런식으로 값을 얻어나갈 수 있습니다. 배열의 모든 칸을 반복문으로 돌면서 그 칸의 0번째 행과 열에 있는 문자를 비교했을 때 같다면 대각선 위의 값에 1을 더한 값을 다르다면 위나 왼쪽의 값중 큰 값을 가져와서 새로운 값을 만들어주면 됩니다. 이 과정이 작은 수열들에 한 문자씩 추가해가면서 그 전까지 이미 구해놨던 최장공통 부분열의 길이를 이용하여 한 문자를 더했을 때 한번의 연산만으로 연장된 수열들의 최장공통 부분열의 길이를 구하는 과정입니다.

 

 

C++

 

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
 
int DP[1005][1005];
char str1[1005];
char str2[1005];
 
int main() {
    scanf("%s", str1);
    scanf("%s", str2);
    int lan1 = strlen(str1), lan2 = strlen(str2),MAX=0;
    for (int i = 1; i <= lan1; i++)
    {
        for (int j = 1; j <= lan2; j++)
        {
            if (str1[i-1] == str2[j-1]) DP[i][j] = DP[i - 1][j - 1] + 1;
            else DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
            MAX = max(MAX, DP[i][j]);
        }
    }
    printf("%d\n", MAX);
}

 

python

 

first_string = input()
second_string = input()
first_len = len(first_string)+1
second_len = len(second_string)+1
 
DP = [[0 for i in range(first_len)] for j in range(second_len)]
 
for i in range(1,second_len):
    for j in range(1,first_len):
        if first_string[j-1]==second_string[i-1] :
            DP[i][j] = DP[i-1][j-1]+1
        else :
            DP[i][j] = max(DP[i-1][j],DP[i][j-1])
 
print(DP[second_len-1][first_len-1])