LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열) : 여러 문자열의 부분 수열 중 공통되는 부분 수열. 그 중 가장 긴 길이를 가진 부분 수열을 뜻한다.

• LCS를 구하는 알고리즘의 순서는 다음과 같다.

1. N개의 문자열들의 LCS를 구하기 위해 문자열 길이를 행과 열로 하는 N차원 배열로 만든다.

2. 문자열들의 각각의 문자들을 비교하면서 배열을 채운다.($N_1*N_2*...$) 다음과 같은 규칙으로 정한다.
   2-1. 문자가 같다면, 배열 왼쪽 위 대각선의 값에 1을 더한 뒤 채운다.
   2-2. 문자가 다르다면, 배열 왼쪽과, 위의 값 중 가장 큰 것을 골라 채운다.
   (왼쪽위 대각선, 왼쪽, 위의 값을 참조해야하므로 0으로만 채워진 행, 열 하나를 더 추가해 계산을 편이하게 한다.)

3. 배열 중 마지막 행과 마지막 열에 위치한 값이 해당 문자열들의 LCS 길이가 된다.

4. 만약, LCS가 무엇으로 이루어져있는지 확인하고 싶다면 해당 조건을 따라한다.
   4-1. 탐색은 마지막 행과 마지막 열부터 시작한다.
   4-2. 첫번째로 현재 값과 왼쪽에 있는 값을 비교한다. 만약 똑같다면 탐색 위치를 왼쪽으로 이동한다.
   4-3. 만약 같지 않다면, 두번째로 현재 값과 위쪽에 있는 값을 비교한다. 만약 똑같다면 탐색 위치를 위쪽으로 이동한다.
   4-4. 만약 같지 않다면, 세번째로 현재 값과 왼쪽 위 대각선에 있는 값을 비교한다. 만약 현재 값보다 -1 만큼 차이가 난다면 탐색 위치를 왼쪽 위 대각선으로 이동한다. → 그리고 이동하기 전, 현재 위치에 해당되는 문자를 저장해놓는다.
   4-5. 위 탐색을 현재 위치의 값이 0일 때까지 반복한다.
   4-6. 탐색을 종료한 뒤 저장해놓은 문자를 역순으로 출력하면 LCS가 된다.

• 해당 알고리즘은 전에 계산했던 결과를 다시 사용하는 것이다. 즉 DP라 할 수 있다.
• 2-1에서 왼쪽 위 대각선의 값에 1을 더하는 것은, 해당 비교 이전에 나온 LCS의 길이에 현재 비교한 문자의 개수까지 카운트하는 것과 똑같다.

: 문자열 'AC'와 'C'를 비교했을 때, LCS 길이는 1이다. 만약 해당 문자열 뒤에 각각 A 문자를 더하여 비교한 것이 현재 표시한 위치이다. 즉, 현재 비교 이전 결과를 불러와 더한 것이다. 문자열 'ACA'와 'CA'를 비교했을 때, LCS 길이가 2인 것을 알 수 있다.

• 2-2에서 왼쪽, 위의 값을 비교하고 큰 값을 택하는 것은, 해당 비교 이전에 나온 LCS의 길이를 저장하는 것과 똑같다.

: 문자열 'ACA', 'CA'의 LCS 길이가 2인것은 알았다. 이제 'ACAY', 'CA'의 LCS 길이를 비교해보기 위해서, (1) 'ACAY', 'C' (2) 'ACA', 'CY' 의 LCS 길이 중 가장 큰 값을 선택한다. (Y!=A 이므로)

예제

백준 9252 LCS 2

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 
모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

	for (int i = 1; i <= S1.size(); i++) {
        for (int j = 1; j <= S2.size(); j++) {
               memo[i][j] = max(max(memo[i][j-1], memo[i-1][j]), memo[i-1][j-1] + S1[i-1] == S2[j-1]);
        }
    }

    int x = S1.size(), y = S2.size();
    while (memo[x][y] != 0) {
        if (memo[x][y] == memo[x][y-1]) {
            y--;
        }
        else if (memo[x][y] == memo[x-1][y]) {
            x--;
        }
        else if (memo[x][y] - 1 == memo[x-1][y-1]) {
            ans.push_back(S1[x-1]);
            x--; y--;
        }
    }