BOJ_G5_9251

📁 [G5_9251] LCS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();

        int length_1 = str1.length;
        int length_2 = str2.length;


        // 메모리제이션 할 배열, 공집합 표현을 위해 1개씩 추가
        int[][] dp = new int[length_1+1][length_2+1];

        for(int i=1; i<=length_1; i++){
            for(int j=1; j<=length_2; j++){

                // i-1 과 j-1 의 문자가 같다면
                if(str1[i-1] == str2[j-1]){
                    // 대각선 위 (i-1, j-1)의 dp 에 +1 해준다.
                    dp[i][j] = dp[i-1][j-1]+1;
                }

                // 같지 않다면
                else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        System.out.println(dp[length_1][length_2]);
    }
}

🤔 나의 생각

DP의 LCS 문제이다.
LCS 알고리즘도 처음 접해봐서 고민하다가 결국 블로그를 봤다.
설명을 너무 깔끔하게 해두셔서 이해가 잘 되었다. 이해가 잘 안된다면 한 번 읽어보는 것도 좋을 것 같다.
내가 이해한 바로는 먼저 두 배열의 표를 만들어 겹치면 수를 더해 표 ( dp 배열에 ) 를 채워나가는 것이다.
여기서 이제 백트래킹 형식으로 하면 문자가 같은 경우에는 왼쪽 대각선에 있는 값에 +1을 해주고, 수가 다른 경우에는 왼쪽값과 오른쪽 값중 큰 값을 가져가는 규칙을 발견할 수 있다.
이것은 bottom-up 방법이다. top-bottom은 재귀를 사용하고 bottom-up은 for문을 사용하기 때문에 시간복잡도나 메모리 사용부분에서 bottom-up의 성능이 더 좋다.
해답을 보고 이해하면 쉽기 때문에 다른 문제들도 많이 풀어봐야 겠다.

👏 참조
https://st-lab.tistory.com/139