[DP] Longest Increasing Subsequence(가장 긴 증가하는 부분 수열), Longest Common Subsequence(최장 공통 부분 수열)

Longest Increasing Subsequence(가장 긴 증가하는 부분 수열)이란?

: 하위 시퀀스의 모든 요소가 오름차순으로 정렬되도록 주어진 시퀀스의 가장 긴 하위 시퀀스의 길이를 찾는 것이다.

<코드>

#include <iostream>
#include <algorithm>
using namespace std;
int d[1001];
int a[1001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	int i;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int j;
	int max=1;
	for(i=0;i<n;i++){
		d[i]=1; // 모든 LIS 길이를 1로 초기화
		for(j=0;j<i;j++){
			if(a[j]<a[i]&&d[i]<d[j]+1){ 
				d[i] = d[j]+1;
			} // LIS 길이 갱신, 증가하는 하위 시퀀스가 존재할 때
			if(max<d[i]) max = d[i]; // 가장 긴 증가하는 부분 수열의 길이 갱신
		}
	}
	cout<<max<<'\n';
	
}

예시

itearator
arr[i]	10	22	9	33	21	50	41	60
LIS	1	2	1	3	1	4	4	5
				갱신 2->3		갱신 3->4		갱신 5->6

 

LIS는 주어진 배열 arr[]의 해당 인덱스에서 끝나는 가장 긴 증가하는 하위 시퀀스의 길이를 저장하는 배열입니다.

(결과물) : idx가 커지면서, 값을 지속적으로 변경해준 결과 (이전에 값을 참조하여 계속 갱신해줘야 한다)

{10, 22} {10,22,33} {10,22,33,50} {10,22,33,50,60}과 같이, 이전 값을 참조하여 다음 값을 갱신해줬다고 볼 수 있습니다. 그래서 동적 계획 알고리즘의 한 형태가 될 수 있습니다. 

 

Longest Common Subsequence(최장 공통 부분 수열)이란 ?

두 시퀀스가 주어지면 두 시퀀스에 모두에 존재하는 가장 긴 하위 시퀀스의 길이를 찾아야 합니다.

하위 시퀀스는 동일한 상대적 순서로 나타나지만, 반드시 연속적이지 않는 시퀀스입니다. 

m = L1의 문자열의 길이, n = L2의 문자열의 길이

ex) L1 = "AGGTAB", L2 = "GXTXAYB" 

case 고려 

case 1) 마지막 문자가 일치하는 경우

LCS[i][j] = LCS[i-1][j-1] + 1

 

case 2) 마지막 문자가 일치하지 않는 경우

max(L1[m-1]L2[n], L1[m]L2[n-1])

 

LCS Table

LCS	0(길이 0)	A	G	G	T	A	B
0(길이 0)	0	0	0	0	0	0	0
G	0	0	1(G)	1(G)	1(G)	1(G)	1(G)
X	0	0	1(G)	1(G)	1(G)	1(G)	1(G)
T	0	0	1(G)	1(G)	2(GT)	2(GT)	2(GT)
X	0	0	1(G)	1(G)	2(GT)	2(GT)	3(GTA)
A	0	1(A)	1(G)	1(G)	2(GT)	3(GTA)	3(GTA)
Y	0	1(A)	1(G)	1(G)	2(GT)	3(GTA)	3(GTA)
B	0	1(A)	1(G)	1(G)	2(GT)	3(GTA)	4(GTAB)

<코드>

#include <iostream>
#include <algorithm>

using namespace std;
int lcs(string arr1 , string arr2, int m, int n)
{
    int L[m+1][n+1];
    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(i==0 || j==0) L[i][j] = 0; // 길이가 0인 LCS
            else if(arr1[i-1] == arr2[j-1]) L[i][j] = L[i-1][j-1] + 1; // 마지막 문자 같은 경우
            else L[i][j] = max(L[i-1][j],L[i][j-1]); 
        }
    }
    return L[m][n]; // 하위 시퀀스 길이의 최종 값
}

int main()
{
    string a = "AGGTAB";
    string b = "GXTXAYB";

    cout<<lcs(a, b, a.size(),b.size());
}