[BOJ] 9251번 LCS

개요

다이나믹 프로그래밍으로 풀이할 수 있는 문제 두 문자열의 LCS(Longest Common Subsequence)를 구해야 한다. 문제링크

코드

import java.io.*;

public class Baekjoon9251 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String str1, str2;
        str1 = br.readLine();
        str2 = br.readLine();

        int[][] dp = new int[str1.length()+1][str2.length()+1];
        int max = 0;

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1))   //문자가 같으면
                    dp[i][j] = dp[i-1][j-1]+1;  //대각선 왼쪽 윗칸값에 1을 더함
                else    //문자가 다르면
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); //왼쪽과 위쪽값중에 큰 값
                max = Math.max(max, dp[i][j]);
            }
        }

        bw.write(max+"");
        bw.flush();
    }
}

해결 과정

문제의 예시를 하나하나 비교해서 표로 보여주면 다음과 같다.

노란색 칸은 같은 문자를 만났을 경우이다.

그리고 LCS의 점화식은 다음과 같다

저 점화식과 표를 보고 코드로 작성한 것이 위의 소스코드인데 문제에선 LCS의 길이만 요구하기 때문에 모든 경우의 수를 dp배열에 저장하고 있을 필요가 없다. (LCS가 어떤 문자열인지 알려면 모두 저장하고 봐야한다.)

그래서 dp배열은 2줄만 사용해 계속 새로운 값을 덮어쓰는 방식을 사용하면 메모리사용량을 개선할 수 있다.

아래는 개선한 소스코드이다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String str1, str2;
        str1 = br.readLine();
        str2 = br.readLine();

        int[][] dp = new int[2][str2.length()+1];   //2행만 사용함
        int max = 0;
        for (int i = 1, idx = 0; i < str1.length() + 1; i++, idx = ++idx % 2) {
            for (int j = 1; j < str2.length() + 1; j++) {
                if (str1.charAt(i-1) == str2.charAt(j-1))   //문자가 같으면
                    dp[idx][j] = dp[(idx+1)%2][j-1]+1;  //대각선 왼쪽 윗칸값에 1을 더함
                else    //문자가 다르면
                    dp[idx][j] = Math.max(dp[(idx+1)%2][j],dp[idx][j-1]); //왼쪽과 위쪽값중에 큰 값
                max = Math.max(max, dp[idx][j]);
            }
        }

        bw.write(max+"");
        bw.flush();
    }

결과

아래는 기존코드 결과이고 위는 개선한 코드 결과이다.

메모리 사용량이 줄어든 것을 확인 할 수 있다.