문자열 매칭 및 비교 알고리즘 (1): 최장 공통 부분 수열 (Longest Common Subsequence, LCS)

1. LCS란?

LCS(Longest Common Subsequence)는 두 문자열에서 순서를 유지하면서 등장하는 가장 긴 공통 부분 수열(Subsequence)을 찾는 알고리즘이다. 이때 '부분 수열'이란 원래 문자열의 일부 문자를 삭제하여 얻을 수 있는 시퀀스를 의미하며, 반드시 연속될 필요는 없다.

 

예를 들어

• 문자열 A: "ACDBE"
• 문자열 B: "ABCDE"
• A와 B의 LCS: "ACDE"

LCS는 텍스트 비교, 유전자 서열 분석, 파일 차이(diff) 계산, 데이터 동기화 등에 널리 사용된다.

2. LCS 알고리즘의 동작 원리

LCS는 일반적으로 동적 계획법(Dynamic Programming)을 사용하여 해결한다. 이때 2차원 배열 dp[i][j]를 만들어, 문자열 A의 i번째 문자까지와 문자열 B의 j번째 문자까지의 LCS 길이를 저장한다.

2.1 점화식

• 문자열 A의 길이: n, B의 길이: m
• A[i - 1] == B[j - 1]이면, dp[i][j] = dp[i - 1][j - 1] + 1
• 그 외에는 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

2.2 예시

문자열 A = "ABCBDAB", B = "BDCAB"

LCS = "BCAB" 또는 "BDAB" (길이 4)

3. 구현 (Java)

public class LCS {
    public static int computeLCS(String a, String b) {
        int n = a.length();
        int m = b.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n][m];
    }

    public static void main(String[] args) {
        String a = "ABCBDAB";
        String b = "BDCAB";

        System.out.println("LCS 길이: " + computeLCS(a, b));
    }
}

4. 시간 및 공간 복잡도

	복잡도
시간	O(n × m)
공간	O(n × m) (단, 최적화로 O(min(n, m))까지 줄일 수 있음)

 

LCS 알고리즘은 문자열의 길이에 따라 성능이 크게 달라질 수 있으므로, 메모리 최적화가 중요한 경우 공간 복잡도 개선 기법을 함께 고려해야 한다.

5. LCS 알고리즘의 활용 사례

• 파일 비교: diff 명령어 또는 Git에서 변경점 추적
• 문서 유사도 측정: 텍스트 간 공통 부분 분석
• 생물정보학: DNA, RNA, 단백질 서열의 유사도 비교
• 자동 에세이 평가: 학생의 답안과 모범 답안 비교

6. LCS vs. 문자열 정렬/검색 알고리즘

	LCS	KMP / Boyer-Moore
목적	두 문자열의 유사도 측정	하나의 패턴이 전체 문자열에 존재하는지 확인
알고리즘 유형	동적 계획법	문자열 검색 기반
시간 복잡도	O(n × m)	O(n + m) / O(n × m) 등
활용 분야	비교 및 분석	검색 및 탐색

7. 결론

LCS 알고리즘은 두 문자열 간의 유사도를 측정하는 데 매우 유용한 도구로, 동적 계획법을 활용하여 최장 공통 부분 수열을 구함으로써 다양한 실제 문제에 응용할 수 있다. 문서 비교, 코드 변경 감지, 생물학적 서열 분석 등에서 활발히 활용되고 있으며, 문자열 처리 알고리즘의 핵심 개념 중 하나로 손꼽힌다.