지식과 경험, 기록을 위한 노트들

Longest Common Substring와 Longest Common Subsequence 의 차이점 쉽게 알기 (LCS 알고리즘)

by · 2023-08-12

알고리즘 분야에서 가장 많이 사용되는 것 중 하나는 두 문자열 사이의 공통 부분을 찾는 것입니다. Longest Common Substring(LCS)와 Longest Common Subsequence(LCS)은 두 문자열 사이의 공통 부분을 찾기 위해 사용되는 두 가지 여러 알고리즘 중 두 가지입니다. 이들 알고리즘은 서로 유사하지만, 목적과 동작 방식에 차이가 있습니다. 이번 기사에서는 두 알고리즘의 차이점을 자세히 알아보고, Java 예제 코드를 통해 이해해보도록 하겠습니다.



Longest Common Substring

Longest Common Substring은 두 문자열 사이에서 가장 긴 공통 부분 문자열을 찾는 알고리즘입니다. 즉, 두 문자열에서 연속된 부분 문자열 중 가장 긴 것을 찾아냅니다. 이 알고리즘은 동적 프로그래밍(Dynamic Programming) 기법을 사용하여 구현될 수 있으며, 다음과 같은 과정으로 동작합니다.

  1. 두 문자열의 각 문자 위치를 비교하여, 같은 문자일 경우에는 이전까지의 공통 부분 문자열 길이에 1을 더한 값을 기록합니다.
  2. 최대 길이 값을 갱신하면서 공통 부분 문자열의 끝 위치를 기록합니다.
  3. 최대 길이 값을 기준으로 공통 부분 문자열을 출력합니다.

예제 코드:

public class LongestCommonSubstring {
    public static String getLongestCommonSubstring(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];
        int maxLength = 0;
        int endIndex = -1;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        endIndex = i;
                    }
                }
            }
        }

        return s1.substring(endIndex-maxLength, endIndex);
    }

    public static void main(String[] args) {
        String s1 = "ABAB";
        String s2 = "BABA";
        String longestCommonSubstring = getLongestCommonSubstring(s1, s2);
        System.out.println("Longest Common Substring: " + longestCommonSubstring);
    }
}

위의 예제 코드에서 getLongestCommonSubstring 메서드는 두 개의 문자열(s1과 s2)을 인자로 받아, 가장 긴 공통 부분 문자열을 반환합니다. 예시로 주어진 s1과 s2가 각각 “ABAB”와 “BABA”인 경우, AB가 가장 긴 공통 부분 문자열이므로 결과로 “AB”가 출력됩니다.



Longest Common Subsequence

Longest Common Subsequence는 두 문자열 사이에서 가장 긴 공통 부분 서열을 찾는 알고리즘입니다. 즉, 두 문자열에서 연속되지 않은 부분 문자열 중 가장 긴 것을 찾아냅니다. Longest Common Subsequence 알고리즘은 Longest Common Substring 알고리즘과 동일한 동적 프로그래밍 기법을 사용하여 구현될 수 있습니다. 다음은 알고리즘의 동작 방식입니다.

  1. 두 문자열의 각 문자 위치를 비교하여, 같은 문자일 경우에는 이전까지의 공통 부분 서열 길이에 1을 더한 값을 기록합니다.
  2. 수직 또는 수평 방향으로 값을 갱신하면서 공통 부분 서열의 끝 위치를 기록합니다.
  3. 최대 길이 값을 기준으로 역추적하여 공통 부분 서열을 출력합니다.

예제 코드:

public class LongestCommonSubsequence {
    public static String getLongestCommonSubsequence(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.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]);
                }
            }
        }

        StringBuilder lcs = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                lcs.append(s1.charAt(i-1));
                i--;
                j--;
            } else if (dp[i-1][j] > dp[i][j-1]) {
                i--;
            } else {
                j--;
            }
        }

        return lcs.reverse().toString();
    }

    public static void main(String[] args) {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";
        String longestCommonSubsequence = getLongestCommonSubsequence(s1, s2);
        System.out.println("Longest Common Subsequence: " + longestCommonSubsequence);
    }
}

위의 예제 코드에서 getLongestCommonSubsequence 메서드는 두 개의 문자열(s1과 s2)을 인자로 받아, 가장 긴 공통 부분 서열을 반환합니다. 예시로 주어진 s1과 s2가 각각 “AGGTAB”와 “GXTXAYB”인 경우, GTAB가 가장 긴 공통 부분 서열이므로 결과로 “GTAB”가 출력됩니다.



LCS 알고리즘 비교

Longest Common Substring와 Longest Common Subsequence는 공통 부분을 찾는 데에 사용되지만, 목적과 동작 방식에 차이가 있습니다.

  • 목적: Longest Common Substring은 연속된 부분 문자열을 찾는 것에 초점을 맞추고 있습니다. 반면에 Longest Common Subsequence는 연속되지 않은 부분 서열을 찾는 것에 초점을 맞추고 있습니다.
  • 동작 방식: Longest Common Substring은 동적 프로그래밍을 사용하여 구현되며, 두 문자열을 비교하면서 최대 길이 값을 갱신하여 공통 부분 문자열을 찾아냅니다. Longest Common Subsequence 또한 동적 프로그래밍을 사용하여 구현되며, 두 문자열을 비교하면서 최대 길이 값을 갱신하고 공통 부분 서열을 역추적합니다.

두 알고리즘은 각각의 목적과 동작 방식에 따라 사용되며, 특정 상황에 맞게 선택하여 사용할 수 있습니다. 두 알고리즘 모두 메모리 사용량을 최소화하고 시간 복잡도를 낮출 수 있도록 구현되어 있습니다. 이를 통해 효율적으로 문자열의 공통 부분을 찾을 수 있습니다. 이번 기사를 통해 Longest Common Substring와 Longest Common Subsequence의 차이점을 잘 이해하고, 각각의 알고리즘이 어떻게 동작하는지 알아보았습니다.

You may also like...