[알고리즘] LCS

구현 방식

• 동적계획법을 사용한다.
• 배열 acc를 다음과 같이 정의한다.

// 문자열 s1 의 i 번째와
// s2의 j 번째 문자 지점까지 비교했을 때의 최대 부분 수열
acc[i][j] 

• 예제 입력을 그림과 같이 구할 수 있다.

• 따라서 아래와 같은 점화식을 세울 수 있다.

// 문자열 s1 의 i 번째, s2의 j번째가 같다면
// s1 의 i-1 번째와 s2의 j번째를 비교했을 때의 최대값
// 이전 문자열의 자리수에서의 최대값 + 1 과 비교
// **이전에 해당 자리에서 비교한 값과 그전까지 비교했던 최대값 +1 중 큰거 택**
acc[i][j] = max(acc[i-1][k] + 1, acc[i-1], j) (k = 0 ~ j - 1)
// 문자열 s1 의 i 번째, s2의 j번째가 같다면
// s1 의 i-1 번째와 s2의 j번째를 비교했을 때의 최대값
// 이전 문자열의 자리수에서의 최대값과 비교
acc[i][j] = max(acc[i-1][k], acc[i-1], j) (k = 0 ~ j - 1)

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>


using namespace std;

void solution(string s1, string s2);
void dp(string s1, string s2);

const int MAXSIZE = 1000;
int acc[MAXSIZE][MAXSIZE] = {};

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

	solution(s1, s2);
}



void solution(string s1, string s2)
{
	dp(s1, s2);

	int result = 0;
	int lastRIdx = s1.size() - 1;
	for (int i = 0; i < s2.size(); i++)
	{
		result = max(acc[lastRIdx][i], result);
	}
	cout << result;
}

void dp(string s1, string s2)
{
	for (int i = 0; i < s1.size(); i++)
	{
		for (int j = 0; j < s2.size(); j++)
		{
			if (0 <= i - 1) acc[i][j] = acc[i - 1][j];

			if (s1[i] == s2[j])
			{
				acc[i][j] = max(1, acc[i][j]); // i == 0 || j == 0 일 때
				for (int k = 0; k < j && 0 <= i -1 ; k++)
				{
					acc[i][j] = max(acc[i - 1][k] + 1, acc[i][j]);
				}
			}
			else
			{
				for (int k = 0; k < j && 0 <= i - 1; k++)
				{
					acc[i][j] = max(acc[i - 1][k] , acc[i][j]);
				}
			}

		}
	}
}