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

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

9251번: LCS (acmicpc.net)

9251번: LCS

두 문자열이 주어졌을 때 구할 수 있는 최장의 공통 부분 수열을 구하는 문제다. 

 

예전에 파이썬으로 풀었던 문제다. 그때 당시에 풀기 위해서 굉장히 시간을 많이 투자했던 것으로 기억한다. 그러다 보니 오늘 풀 때도 전보다는 굉장히 수월하게 풀었다. 물론 한 번에 푼 건 아니었고.. 예전과 같은 문제를 거치면서 통과했다. 그러면서 느낀 게 이제는 틀렸을 경우 스스로 틀린 테스트케이스를 찾는 연습도 해야겠다. 그래야 이런 일들의 반복을 막을 것 같다.

아래는 예전에 파이썬으로 풀고 올렸던 글이다. 오늘 풀이도 이 글에서의 설명과 다르지 않다. 근데 오늘이 더 간단하게 설명할 것 같다.

[백준알고리즘] 9251번: LCS -Python (tistory.com)

[백준알고리즘] 9251번: LCS -Python

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

음 문제를 설명하기 어려운 것 같다.

 

일단은 동적 계획법을 풀어야 한다. 이전의 최장 부분 수열을 현재 더 증가시킬 수 있는가에 집중하기 때문이다. 그래서 이전의 최장 부분 수열의 길이를 기억해두어야 하며, 이전 상태를 기반으로 현재 값이 정해진다.

 

그래서 주어진 문자열 \( A \), \( B \)에 해당하는 길이가 \( lenA \), \( lenB \) 일 때, \( lenA \times lenB \) 크기의 배열을 정의해두고 메모이제이션에 사용한다.

 

 

수열의 길이가 정해지는 경우는 \( strA [i] == strB [j] \) 일 때다. 이 경우에는 \( strA [i] \)와 \( strB [j] \)를 소모해서 최장 수열을 늘린다는 개념이기 때문에 \( strA [i] \)와 \( strB [j] \)가 소모되지 않은 상태에서의 최장 길이인 \( dp [i-1][j-1] \)를 이용한다.

 

따라서 \( strA [i] == strB [j] \) 일 때, \( dp [i][j] = dp [i-1][j-1] + 1 \)이다. 

 

반면, \( strA [i]!= strB [j] \) 일 때에는 \( strA [i] \)와 \( strB [j] \)를 소모해서 최장 부분 수열의 길이를 늘릴 수 없기 때문에 \( strA [i] \)와 \( strB [j] \)가 소모된 상태인 최장 부분 수열의 최대 길이인 \( dp [i-1][j] \)와 \( dp [i][j-1] \)을 이용한다. 

 

따라서 \( strA [i]!= strB [j] \) 일 때, \( dp [i][j] = max ( dp [i-1][j], dp [i][j-1] ) \)인 것이다.

 

해당 점화식들을 이용해 문제를 풀면 아래의 C++ 코드처럼 된다. 

앞서 말했듯이 혼자 테스트케이스를 만들어 실패하는 경우를 찾아가는 연습을 더 해야겠다.

#include <iostream>
#include <string>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

int lcs(std::string strA, std::string strB)
{
	int lenA = strA.size();
	int lenB = strB.size();

	std::vector<std::vector<int>> dp(lenA, std::vector<int>(lenB, 0));

	for (int i = 0; i < lenA; i++)
	{
		if (0 < i)
			dp[i][0] = dp[i - 1][0];

		if (strA[i] == strB[0])
			dp[i][0] = 1;
	}

	for (int j = 0; j < lenB; j++)
	{
		if (0 < j)
			dp[0][j] = dp[0][j - 1];

		if (strA[0] == strB[j])
			dp[0][j] = 1;
	}

	for (int i = 1; i < lenA; i++)
	{
		for (int j = 1; j < lenB; j++)
		{
			dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
		
			if (strA[i] == strB[j])
				dp[i][j] = dp[i - 1][j - 1] + 1;
		}
	}

	return dp[lenA - 1][lenB - 1];
}

void solve(void)
{
	std::string strA, strB;
	std::cin >> strA >> strB;

	std::cout << lcs(strA, strB);
}