자바 코딩테스트 강좌, 최장 공통 부분 수열 찾기

본 강좌에서는 코딩 테스트에서 자주 출제되는 문제인 “최장 공통 부분 수열(Longest Common Subsequence, LCS)”에 대해 알아보겠습니다. LCS 문제는 두 개의 시퀀스가 주어졌을 때, 두 시퀀스에서 각각의 요소의 상대적 순서를 유지하면서 만들 수 있는 가장 긴 공통 부분 수열을 찾는 문제입니다.

문제 설명

두 개의 문자열 str1과 str2가 주어질 때, 이 두 문자열의 최장 공통 부분 수열의 길이를 구하세요.

입력

• 문자열 str1 : “AGGTAB”
• 문자열 str2 : “GXTXAYB”

출력

최장 공통 부분 수열의 길이 : 4

문제 풀이 과정

이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming) 접근 방식을 사용할 것입니다. 동적 프로그래밍은 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 효율적으로 문제를 해결하는 방법입니다.

1단계: 이차원 배열 초기화

2단계: 이차원 배열 채우기

3단계: 코드 구현

이제 이 과정을 자바 코드로 구현해 보겠습니다.

public class LongestCommonSubsequence {
    public static int lcs(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];

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

    public static void main(String[] args) {
        String str1 = "AGGTAB";
        String str2 = "GXTXAYB";
        System.out.println("최장 공통 부분 수열의 길이: " + lcs(str1, str2));
    }
}
    

코드 분석

위 코드는 다음과 같은 방식으로 작동합니다.

• 두 개의 문자열을 입력받고, 그 길이에 따라 dp 배열을 생성합니다.
• 이중 반복문을 사용하여 문자열을 비교하고, 동적 프로그래밍 방식으로 값을 업데이트합니다.
• 출력으로는 최장 공통 부분 수열의 길이를 제공하고 있습니다.

실행 결과

결론

이번 강좌에서는 최장 공통 부분 수열을 찾는 방법에 대해 알아보았습니다. 알고리즘 문제를 해결하기 위해 동적 프로그래밍 기법을 활용하는 것이 얼마나 효과적일 수 있는지를 보여주었습니다. 이 문제는 다양한 분야에서 활용될 수 있으며, 알고리즘 문제를 풀 때 기본적으로 알아두어야 할 내용입니다.

더 나아가 본 강좌에서 공유된 코드를 바탕으로 다른 문자열 조합에 대해서도 실험해보며, 이론을 더욱 심화시킬 수 있습니다. 알고리즘 문제 풀이 능력을 키우는 데 큰 도움이 되기를 바랍니다.