LCS 알고리즘으로 문자열 비교

1. LCS 문제 개요

LCS (Longest Common Subsequence)

두 문자열이 주어졌을 때, 두 문자열 모두에서 순서를 유지하면서 선택할 수 있는 공통 문자의 최대 길이의 나열을 찾는 문제를 LCS 문제라고 합니다.

부분수열(Subsequence)

원본 문자열의 순서를 유지하되, 일부 문자를 제거해서 얻은 문자열

예시:

문자열 A: ACAYKP
문자열 B: CAPCAK
두 문자열에서 ACAK는 공통 부분수열 중 하나이며, 그 길이는 4입니다.

2. 동적 계획법(DP)을 활용한 LCS 알고리즘

LCS 문제는 모든 가능한 부분수열을 직접 비교하는 대신, 동적 계획법(DP)을 사용하여 문제를 작은 단위로 쪼개서 해결합니다. 이 과정에서 dp 테이블을 활용하여 두 문자열의 부분 문제 결과를 저장하고, 이를 바탕으로 전체 문제의 해답을 구합니다.

2.1. dp 테이블 정의

dp[i][j]:

문자열 A의 처음 i개 문자와 문자열 B의 처음 j개 문자를 비교했을 때의 LCS 길이를 저장하는 2차원 테이블

초기 조건:

문자열 A 또는 B가 빈 문자열이면 LCS 길이는 0이므로, dp 테이블의 첫 행과 첫 열은 모두 0으로 초기화합니다.

2.2. 점화식 (Recurrence Relation)

dp 테이블을 채우는 규칙은 두 가지 경우로 나뉩니다.

문자가 일치하는 경우 (A[i] == B[j]):

해당 이유:

두 문자열에서 동일한 문자를 발견했으므로, 이전까지 찾은 LCS에 현재 문자를 추가하면 길이가 1 증가합니다.

점화식:

dp[i][j] = dp[i-1][j-1] + 1;

문자가 일치하지 않는 경우 (A[i] ≠ B[j]):

해당 이유:

현재 문자를 포함하지 않은 두 경우(즉, A에서 현재 문자를 제외하거나, B에서 현재 문자를 제외하는 경우) 중 더 긴 LCS를 선택해야 합니다.

점화식:

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

2.3. dp 테이블 채우기

구현 개요:

이중 for문을 통해 각 (i, j) 위치에서 위 점화식을 적용합니다. 최종적으로 dp[A의 길이][B의 길이]에는 전체 문자열에 대한 LCS 길이가 저장됩니다.

3. 예제: “ACAYKP”와 “CAPCAK”의 dp 테이블 구성

Tip:

문자열 앞에 공백을 추가하여 인덱스를 1부터 사용하면, 초기 조건(빈 문자열 처리)을 보다 쉽게 구현할 수 있습니다.

문자열 A: " A C A Y K P"
문자열 B: " C A P C A K"

3.1. 초기 상태

dp 테이블의 첫 행과 첫 열은 0으로 초기화됩니다.

“”	A	P	C	A	K
“”	0	0	0	0	0	0
A
C
A
Y
K
P

3.2. 채우는 과정 (일부 행 예시)

Row 1 (문자 A):

dp[1][1]: A vs. C → 다름 → 0
dp[1][2]: A vs. A → 같음 → 0 + 1 = 1
dp[1][3]: A vs. P → 다름 → max(0, 1) = 1
…
결과: Row 1은 [0, 0, 1, 1, 1, 1, 1]

Row 2 (문자 C):

dp[2][1]: C vs. C → 같음 → 0 + 1 = 1
dp[2][2]: C vs. A → 다름 → max(1, 1) = 1
dp[2][4]: C vs. C → 같음 → 1 + 1 = 2
…
결과: Row 2는 [0, 1, 1, 1, 2, 2, 2]

나머지 행도 동일한 방식으로 채워나가면, 최종적으로 dp[6][6] = 4가 되어 두 문자열의 LCS 길이가 4임을 알 수 있습니다.

결과: 두 문자열의 LCS 길이는 4

“”	A	P	C	A	K
“”	0	0	0	0	0	0
A	0	1	1	1	1	1
C	1	1	1	2	2	2
A	1	2	2	2	3	3
Y	1	2	2	2	3	3
K	1	2	2	2	3	4
P	1	2	3	3	3	4

4. LCS 문자열 역추적 (Backtracking)

dp 테이블이 완성된 후, 실제 LCS 문자열을 복원하기 위해 역추적을 진행합니다.

4.1. 역추적 시작점

시작 위치:

dp 테이블의 마지막 셀, 즉 dp[n][m] (예제에서는 dp[6][6] = 4)

4.2. 진행 방식

문자가 일치하는 경우:

조건: A[i] == B[j]
행동:
현재 위치의 문자를 결과 문자열에 추가
대각선 위쪽 셀 (i-1, j-1)로 이동

문자가 일치하지 않는 경우:

행동:
위쪽 셀 (dp[i-1][j])와 왼쪽 셀 (dp[i][j-1]) 중 더 큰 값을 가진 방향으로 이동

4.3. 종료 조건

i 또는 j가 0에 도달하면 역추적을 종료합니다.
역추적 과정에서 추가한 문자는 역순으로 저장되므로, 최종 결과 문자열을 뒤집어 올바른 순서로 복원합니다.

4.4. 예시 역추적 과정

(6, 6):

A[6] = ‘P’ vs. B[6] = ‘K’ → 다름
비교 결과, dp[5][6] (4)가 더 크므로 (5, 6)로 이동

(5, 6):

A[5] = ‘K’ vs. B[6] = ‘K’ → 일치
‘K’ 추가 후 대각선 (4, 5)로 이동

(4, 5):

A[4] = ‘Y’ vs. B[5] = ‘A’ → 다름
비교 결과, dp[3][5] (3)이 더 크므로 (3, 5)로 이동

(3, 5):

A[3] = ‘A’ vs. B[5] = ‘A’ → 일치
‘A’ 추가 후 대각선 (2, 4)로 이동

(2, 4):

A[2] = ‘C’ vs. B[4] = ‘C’ → 일치
‘C’ 추가 후 대각선 (1, 3)로 이동

(1, 3):

A[1] = ‘A’ vs. B[3] = ‘P’ → 다름
비교 결과, dp[1][2] (1)이 더 크므로 (1, 2)로 이동

(1, 2):

A[1] = ‘A’ vs. B[2] = ‘A’ → 일치
‘A’ 추가 후 대각선 (0, 1)로 이동 → 종료

역추적 결과:

역순으로 저장된 문자: ‘K’ → ‘A’ → ‘C’ → ‘A’

최종적으로 뒤집으면 “ACAK”가 LCS가 됩니다.

5. 코드 예시 (Java)

백준 9251번 (LCS 길이 출력)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_LCS {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = " "+br.readLine();
        String str2 = " "+br.readLine();

        int[][] mat = new int[str1.length()][str2.length()];
        for(int i = 1; i < str1.length(); i++){
            for(int j = 1; j < str2.length(); j++){
                if(str1.charAt(i) == str2.charAt(j)){
                    mat[i][j] = mat[i-1][j-1] + 1;
                }else{
                    mat[i][j] = Math.max(mat[i][j-1], mat[i-1][j]);
                }
            }
        }
        
        System.out.println(mat[str1.length()-1][str2.length()-1]);
        

    }
}

백준 9252번 (LCS 길이 및 문자열 출력)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = " "+br.readLine();
        String str2 = " "+br.readLine();

        int[][] mat = new int[str1.length()][str2.length()];
        for(int i = 1; i < str1.length(); i++){
            for(int j = 1; j < str2.length(); j++){
                if(str1.charAt(i) == str2.charAt(j)){
                    mat[i][j] = mat[i-1][j-1] + 1;
                }else{
                    mat[i][j] = Math.max(mat[i][j-1], mat[i-1][j]);
                }
            }
        }
        
        System.out.println(mat[str1.length()-1][str2.length()-1]);
        
        char[] resultSet = new char[mat[str1.length()-1][str2.length()-1]];
        int i = str1.length()-1;
        int j = str2.length()-1;
        int idx = resultSet.length-1;
        while(true){ 
            if(mat[i][j] == 0) break;
            

            if(str1.charAt(i) == str2.charAt(j)){
                resultSet[idx] = str1.charAt(i);
                i--;
                j--;
                idx--;
            }else if(mat[i-1][j] < mat[i][j-1]){
                j--;
            }else{
                i--;
            }
        }
        System.out.println(String.valueOf(resultSet));
    }
}

참고

[[알고리즘] 그림으로 알아보는 LCS 알고리즘 – Longest Common Substring와 Longest Common Subsequence](https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence)