백준 9251번 : LCS [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

LCS 골드 5

 

📖 문제

 

최장 공통 부분 수열로 

알고리즘 시간에 배웠었다. 

근데 배운거랑 직접 구현해본거랑 차이가 심한 것을 느꼈다.

 

이 문제를 못푸니 배낭문제도 못푼다. 

LCS에 대한 이해가 있었다면 배낭 문제를 쉽게 풀 수 있을 것이다. 

 

현재 비교하는 두 문자가 같다면 

이전 최장 공통 부분 수열 길이에 + 1을 하여 LCS를 갱신한다.

 

두 문자열의 길이를 각각 n과 m이라 할 때,
DP 테이블 dp는 인덱스 i∈[0,n]  j∈[0,m] 범위를 기반으로 구성된다.

 

i-1, j-1까지 진행 했을때 LCS 길이 + 현재 공통 문자가 나왔으므로 길이가 1 증가

때문에 dp[i-1][j-1] + 1이 된다. 

 

같지 않다면 dp[i-1][j], dp[i][j-1] 중 큰 값을 유지한다. 

이유는 두 문자가 다르면 LCS에 포함할 수 없기 때문에 

i-1,j 번째 까지 공통부분 수열 과 i, j-1 번째 공통 부분 수열 중 최대 길이를 유지하여

i,j까지 LCS를 나타내는 것이다.

 

 

 

 

 

---

🔅 문제 풀이

import java.io.*;


public class Main {

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

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

        int[][] dp = new int[str1.length + 1][str2.length + 1];

        for (int i = 1; i <= str1.length; i++) {
            for (int j = 1; j <= str2.length; j++) {
                if (str1[i-1] == str2[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]); // 다르다면 이전 최장 공통 부분 수열의 길이가 가장 긴 것을 유지
                }
            }
        }


        bw.write(dp[str1.length][str2.length] + "");
        bw.flush();
        bw.close();

    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  정말 설명하기 어려운 알고리즘 인 것 같다. 좀 더 쉽게 이해하자면 이전의 LCS값은 사실상 LCS 바구니에 담은 개수라고 본다. i-1,j-1에 +1을 하는 이유는 이전까지의 LCS에 현재 i,j도 같으므로 +1을 하는 것이기때문이다