백준 9251, 9252 - Longest Common Subsequence

9251 코드 : www.acmicpc.net/problem/9251

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string a,b;
int arr[1001][1001];
// LCS 알고리즘
// 2차원 배열을 통해 같은 문자열을 저장한다
// 여기에 저장된 값중 최대값이 최대 공통 요소가 된다
// 열까지 해당하는 문자열, 행까지 해당하는 문자열 중
// 최대 같은 길이가 배열에 값으로 저장된다
int main(){
    cin >> a >> b;

    int maxA = a.size();
    int maxB = b.size();
    for(int i = 1; i <= maxA; i ++){
        for(int j = 0; j <= maxB; j++){
            if(a[i-1] == b[j-1])
                arr[i][j] = arr[i-1][j-1] + 1;
            else
                arr[i][j] = max(arr[i-1][j], arr[i][j-1]);
        }
    }

    cout << arr[maxA][maxB] << '\n';
}

9252 코드 : www.acmicpc.net/problem/9252

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string a,b;
int arr[1001][1001];
string lcs[1001][1001];
int main(){
    cin >> a >> b;

    int maxA = a.size();
    int maxB = b.size();
    for(int i = 1; i <= maxA; i ++){
        for(int j = 0; j <= maxB; j++){
            // 공통부분 발견
            if(a[i-1] == b[j-1]){
                arr[i][j] = arr[i-1][j-1] + 1;
                // 최대 배열값 갱신
                lcs[i][j] = lcs[i][j] + lcs[i-1][j-1] + a[i-1];
            }
            else{
                // 공통부분이 없다면 남아있는 것들 중 최대를 고름
                arr[i][j] = max(arr[i-1][j], arr[i][j-1]);

                if(lcs[i-1][j].length() > lcs[i][j-1].length())
                    lcs[i][j] = lcs[i-1][j];
                else
                    lcs[i][j] = lcs[i][j-1];
            }
                
        }
    }

    cout << arr[maxA][maxB] << '\n';
    cout << lcs[maxA][maxB] << '\n';
}

---

주요 개념

위 코드에서 사용되는 LCS 2차원 배열의 경우 행과 열을 가리키고 있으며 해당하는 행, 열 위치에는 최대로 길이가 같은 값이 들어갑니다. 아래 표를 통해 배열의 상태를 직접 보는게 이해하기가 쉬웠습니다.

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A
P

 

초기 CAPCAK의 첫 C를 비교해보면 2번째 부터 같은 값이 나오게 됩니다.

같은 값이 나오는 경우  대각선 위와 비교한 뒤 값을 +1 해준다.

(같은 값이 아닌 경우 왼쪽과 위쪽중 큰 값을 저장     - 최대 부분수열을 저장해야 하기 때문)

 

아직은 이해가 잘 안되니 다음 수열을 계속 넣어보자

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3

이런식으로 되어 있다.

 

여기서 파란색 밑줄이 그어진 부분이 왜 2를 저장했는지 따져보면

   CAP 와 ACA의 부분 수열중 최장 길이는 2

라는 뜻으로 2를 저장한 것이다.

 

한마디로 행과 열에 해당하는 문자열의 최장 부분수열의 길이를 저장하는 작업을 하는 것이다.

if(a[i-1] == b[j-1])
	arr[i][j] = arr[i-1][j-1] + 1;
else
	arr[i][j] = max(arr[i-1][j], arr[i][j-1]);

그래서 저 과정을 코드로 나타내면 저렇게 되는 것이다.

 

이런 과정을 통해 LCS를 계산하는 시간 복잡도는 O(mn)이 된다. 

 - 기존에는 부분수열을 전부 만들어야 하기 때문에 2^n*2^m이라는 괴랄한 시간복잡도를 가진다고 한다.

 문제 풀이시 키워드

1. 최대 부분 수열이다

 - ACAYKP / CAPCAK의 최대 부분수열은 ACAK이다. 순서가 같은걸 찾는게 아니라는 뜻이다.

   ACAYKP에는 ACA (Y) K 이런 식으로 있다.

2. 배열이 어떤 것을 저장하는지 기억

3. 9252문제의 경우 새 배열 추가 외에 배열을 역추적하는 방법으로 최대 배열을 구할 수 있다.