문제 URL:
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력하는 프로그램을 작성하자.
*최장 공통 부분 문자열은 연속되어야 하지만 최장 공통 부분 수열은 연속되지 않아도 됨
다음 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제로 예시를 통해서 문제를 이해해 보자.
i: 문자열 A의 문자 중 하나의 위치
j: 문자열 B의 문자 중 하나의 위치
DP[i][j]: 처음~i와 처음~j를 비교했을 때까지의 공통 부분 수열의 최대 길이
먼저, 비교하는 두 문자가 같을 때이다.
문자열 "ABDEG"와 "ABECG"가 존재할 때 마지막 G에서 값은 "ABDE"와 "ABEC" 까지의 최장 공통 부분수열 + 1이 된다.
이를 DP를 이용한 식으로 나타내면 다음과 같다.
DP[i][j] = DP[i-1][j-1] + 1;
반대로 4번째 자리의 E와 C 같이 비교하는 두 문자가 다를 때에는
이전 "ABD", "ABE"까지의 최장 공통 부분 수열에 E를 포함한 경우와 C를 포함한 경우를 각각 두고 둘 중 더 큰 값을 취하면 된다.
식으로 표현하면 다음과 같다.
DP[i][j] = max(DP[i-1][j], DP[i][j-1]); // max(): algorithm 헤더의 함수
위 과정을 포함한 문자 비교를 두 문자열이 끝날 때까지 수행하면 마지막 DP에 두 문자열의 최장 공통 부분 수열의 길이가 저장된다.
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string A, B;
int DP[1001][1001]; // 처음~i와 처음~j를 비교했을 때까지의 공통 부분 수열의 최대 길이
int main(){
cin >> A >> B;
int a_size = A.size();
int b_size = B.size();
for(int i=1; i<=a_size; i++){
for(int j=1; j<=b_size; j++){
if(A[i-1] == B[j-1])
DP[i][j] = DP[i-1][j-1] + 1;
else
DP[i][j] = max(DP[i-1][j], DP[i][j-1]);
}
}
cout << DP[a_size][b_size] << '\n';
return 0;
}