[C/C++] 백준 9251번 - LCS(Longest Common Subsequence, 최장 공통 부분 수열)

 

 

<LCS 코드>

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int DP[1002][1002];
string s1, s2;
int len1, len2;

int main()
{
	cin >> s1 >> s2;

	len1 = s1.size();
	len2 = s2.size();

	for (int i = 1; i <= len2; i++)
	{
		for (int j = 1; j <= len1; j++)
		{
			if (s2[i - 1] == s1[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[len2][len1];
}

 

재귀로 풀려고 시도해봤으나 풀지 못하고 고민 끝에 답을 검색해봤다. LCS(Longest Common Subsequence, 최장 공통부분 수열)라는 문제를 처음 접해봤으며, 풀이 방법도 지식이 부족해 풀 수 없었던 문제였던 것 같다. (참고한 페이지는 아래에 출처를 남기겠습니다.)

먼저 위의 코드를 실행시켜 얻은 DP를 살펴보면

DP[ ][ ]	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

빨간색 '2'인 DP[2][4]의 의미는 ACAY와 CA의 LCS길이는 2라는 뜻이며(LCS = CA),
파란색 '3'인 DP[5][5]의 의미는 ACAYK와 CAPCA의 LCS길이는 3이라는 뜻이다.(LCS = ACA)

DP[i][j]값을 구하는 알고리즘은 첫 번째 입력 문자열이 s1, 두 번째 입력 문자열이 s2라 한다면,

1. s1[i]와 s2[j]가 같다면 이전의 LIS값(왼쪽 대각 위 값, DP[i-1][j-1])에서 +1을 해준 값을 적는다.

2. s1[i]와 s2[j]가 다르다면, 왼쪽값(DP[i][j-1]), 위쪽값(DP[i-1][j]) 중에서 큰 값을 적는다.

 

이러한 알고리즘으로 DP값을 구하게 되면 DP의 마지막 값이 해당하는 두 문자열의 LCS길이가 된다.

 

처음 접해보는 알고리즘이라서 생각해내기 쉽지 않다고 생각되며, 이해하는데 시간이 좀 걸렸던 것 같다.

 

www.acmicpc.net/problem/9251

9251번: LCS

 

 

 

참고자료 - melonicedlatte.com/algorithm/2018/03/15/181550.html