알고리즘 이론

LCS(Longest Common Subsequence)

행수쌤 2023. 3. 5. 14:03
728x90
반응형

LCS(Longest Common Subsequence)는 두 개 이상의 문자열에서 공통으로 나타나는 가장 긴 부분 문자열을 찾는 알고리즘입니다.

LCS 알고리즘은 동적 프로그래밍(Dynamic Programming)을 활용하여 구현할 수 있으며, 다양한 응용 분야에서 사용됩니다. 예를 들어, LCS는 DNA 염기서열 분석, 문서 비교 및 유사성 검색, 음악 분석, 이미지 처리 등에서 사용됩니다.

LCS 알고리즘의 시간 복잡도는 O(nm)이며, n과 m은 각각 두 문자열의 길이입니다. 이 알고리즘은 다른 문자열 비교 알고리즘과 함께 문자열 비교 및 유사성 검색 문제를 해결하는 데 널리 사용됩니다.

다음은 일반적인 LCS 알고리즘의 구현 과정입니다.
  1. 두 문자열 X와 Y를 입력으로 받습니다.
  2. X와 Y의 길이를 각각 m과 n이라고 합니다.
  3. m x n 크기의 2차원 배열 C를 생성합니다. C[i][j]는 X의 i번째 문자와 Y의 j번째 문자까지의 LCS의 길이를 나타냅니다.
  4. C[0][j]와 C[i][0]을 0으로 초기화합니다.
  5. X[i] == Y[j]인 경우, C[i][j] = C[i-1][j-1] + 1입니다.
  6. X[i] != Y[j]인 경우, C[i][j] = max(C[i-1][j], C[i][j-1])입니다.
  7. 배열 C의 마지막 원소 C[m][n]가 두 문자열 X와 Y의 LCS의 길이입니다.
  8. 배열 C를 역추적하여 LCS를 찾습니다.

public class LCS {
    public static int lcs(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] C = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    C[i][j] = C[i - 1][j - 1] + 1;	//문자가 일치하면 왼쪽 위 대각선 개수+1
                } else {
                    C[i][j] = Math.max(C[i - 1][j], C[i][j - 1]);
                }	//일치하지 않으면 왼쪽이나 윗쪽 개수중 큰 수(넘어가기)
            }
        }
        return C[m][n];
    }

    public static void main(String[] args) {
        String X = "ABCBDAB";
        String Y = "BDCABA";
        int length = lcs(X, Y);
        System.out.println("Length of LCS: " + length);
    }
}

 

LCS(Longest Common Subsequence)의 배열을 찾으려면, LCS의 길이를 저장하고 있는 배열 C를 역추적하여 찾을 수 있습니다.
  1. 배열 C를 역순으로 탐색하면서, C[i][j] 값이 C[i-1][j-1], C[i-1][j], C[i][j-1] 중 어느 값을 가지는지 확인합니다.
  2. C[i][j] 값이 C[i-1][j-1] + 1인 경우, 문자열 X[i-1]과 Y[j-1]의 문자가 LCS의 일부분이므로, 이를 LCS 배열에 추가합니다.
  3. C[i][j] 값이 C[i-1][j]나 C[i][j-1]와 같은 경우, 배열 C의 값이 큰 쪽으로 이동하여 탐색을 계속합니다.
  4. 배열을 찾을 때는 배열 C의 마지막 원소부터 시작하여 LCS 배열을 역순으로 저장합니다.

public class LCS {
    public static String lcs(String X, String Y) {
        int m = X.length();
        int n = Y.length();
        int[][] C = new int[m + 1][n + 1];

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

        // LCS 배열을 역추적하여 찾음
        int len = C[m][n];
        char[] lcs = new char[len];
        int i = m, j = n;
        while (len > 0) {
            if (X.charAt(i - 1) == Y.charAt(j - 1)) {	//문자가 일치하면
                lcs[len - 1] = X.charAt(i - 1);	//배열 마지막자리에 문자 추가
                i--;
                j--;	//문자 인덱스 조정
                len--;	//배열 인덱스 조정
            } else if (C[i - 1][j] >= C[i][j - 1]) {
            	//문자가 일치하지 않고 윗쪽 갯수가 왼쪽 갯수보다 많으면(갯수가 max로 온 뱡항)
                i--;	//위로 한칸
            } else {
                j--;	//왼쪽으로 한칸
            }
        }
        return new String(lcs);	//문자열 배열을 String으로 반환
    }

    public static void main(String[] args) {
        String X = "ABCBDAB";
        String Y = "BDCABA";
        String lcs = lcs(X, Y);
        System.out.println("LCS: " + lcs);
    }
}

 

728x90
반응형