[알고리즘] C++ 백준 9251 LCS

 

백준 9251

https://www.acmicpc.net/problem/9251

9251번: LCS

풀이 전 나의 생각

이 문제는 최장 공통 부분 수열(LCS)을 구해야 한다. 언뜻보면 같은 문자열만 구하면 되는 것이 아닌가 생각할 수 있지만 수열이기 때문에 값을 뛰어 넘는 부분까지 생각해야 한다.

 

 

1. if (i == 0 || j == 0)

 

for문을 이용한 DP특성 상 이전에 저장된 값에 접근해야 하기 때문에 문자열을 1부터 시작하도록 만들어놓고

1 이전의 공간은 0으로 모두 채워준다.  ex) lcs[0 - 1][0 - 1] -> 배열 범위 오류 발생

 

2. else if (arr1[i] == arr2[j])
{
    lcs[i][j] = lcs[i - 1][j - 1] + 1;
}

 

배열을 탐색하면서 비교하는 문자의 값이 같을 때 이전에 구해놓았던 최장 공통 부분 수열값에 +1을 해준다.

예를 들어 ABEF와 CBGF의 LCS를 구한다고 가정해보자. 진행 과정 중 ABEF의 F와 CBGF의 F를 비교하는 순번이 왔다고 하면  lcs[i - 1][j - 1] + 1; 을 진행할 것이다. 직접 대입해보면 lcs[4 - 1][4 - 1] + 1; 즉, ABE와 CBG를 비교했을 때 나올 수 있는 최장 공통 부분 수열 ( lcs[4 - 1][4 - 1] ) 에 현재 공통된 비교값 F를 추가( + 1)하면 ABEF와 CBGF를 비교한 결과가 나오는 것이다. 요약하자면 ABEF와 CBGF의 LCS를 구하기 위해 이전 ABE와 CBG값에 접근하는 것이다.

 

3. else
{
    lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
}

 

2번에서는 비교하는 문자가 같을 때를 처리해주었다. 따라서 비교 문자가 같지 않으면서 현재까지의 최장 공통 부분 수열을 접근할 수 있게 만들어주는 과정이 필요하다. 예를 들어 ABEF와 CBGS가 있다고 가정하자. 2번과 똑같이 4번째 부분을 비교한다고 했을 때 똑같이 ABE와 CBG의 LCS값을 구하면 안된다. 이유는 ABE와 CBG의 LCS를 접근해서 값을 가져왔다 한들 ABE->F 분기의 LCS값과 CBF->S 분기의 LCS값이 다르기 때문이다. 좀 더 쉽게 설명하자면 실제로 값을 대입해보면 lcs[4 - 1][4], lcs[4][4 - 1]이 나오고 이는 ABE와 CBGS(lcs[4 - 1][4])를 비교했을 때의 LCS값과 ABEF와 CBG(lcs[4][4 - 1])를 비교했을 때의 LCS값을 비교하는 형식이 된다. 결과적으로 ABE와 CBG만 비교했을때의 문제점을 (ABEF, CBG) , (ABE, CBGS)로 구하여 비교하는 문자 값이 다를 때 얻어야 하는 모든 분기의 이전 LCS 값을 구한 것이다. 

 

 

요약

ABEF와 CBGF의 4번째 문자 값 비교 -> ABE와 CBG의 LCS값만 접근하면 된다.

ABEF와 CBGS의 4번째 문자 값 비교 -> ABEF와 CBG, ABE와 CBGS의 LCS값을 접근하여 최대값을 구한다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;
int lcs[1001][1001];
int arr1[1001];
int arr2[1001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string str1, str2;
	int res = 0;
	cin >> str1 >> str2;

	for (int i = 1; i <= str1.size(); i++)
	{
		arr1[i] = str1[i - 1];
	}
	for (int j = 1; j <= str2.size(); j++)
	{
		arr2[j] = str2[j - 1];
	}

	for (int i = 1; i <= str1.size(); i++)
	{
		for (int j = 1; j <= str2.size(); j++)
		{
			if (i == 0 || j == 0)
			{
				lcs[i][j] = 0;
			}
			else if (arr1[i] == arr2[j])
			{
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
			}
			else
			{
				lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
			}
		}
	}

	for (int i = 1; i <= str1.size(); i++)
	{
		for (int j = 1; j <= str2.size(); j++)
		{
			res = max(res, lcs[i][j]);
		}
	}

	cout << res;
}