백준 9251 LCS 문제풀이

LCS 설명

• LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열을 뜻한다.

LCS는 Dynamic Programming에서 흔히 나오는 문제 중 하나이다.
DP 문제는 항상 최대, 최소, 가장 긴, 가장 짧은 값 등을 구하라는 문구가 많다.

Subsequence란 무엇인가?

• Subsequence 를 우리가 흔히 쓰는 Substring과 비교하며 이해해보자.
  • Substring은 Subsequence의 슈퍼셋이다.
    • 즉, Substring인 문자열은 Subsequence이기도 하다.
    • 단, Subsequence인 문자열은 Substring이 아닐 수도 있다.
  • Substring: 반드시 연속되는 형태로 이루어진 부분 문자열이다.
    • ex) abcdefg라는 문자열이 존재할 때, defg는 abcdefg의 Substring이다.
  • Subsequence: 연속되지는 않을 수도 있는 부분 문자열이다. 단, 순서는 지켜져야 한다.
    • ex) abcdefg라는 문자열이 존재할 때, acefg는 abcdefg의 Subsequence이다.
  • 결국, 연속되는지, 연속되지 않을 수 있는지가 Substring과 Subsequence를 구분하는 핵심이다.
• 위키 참조: https://en.wikipedia.org/wiki/Subsequence

LCS가 쓰이는 곳

• GIT에서 관리되는 소스코드를 변경하면, 변경된 부분만 보여주는 DIFF라는 기능을 제공한다. 이 DIFF라는 기능에서도 LCS의 개념을 사용한다.

문제를 기준으로 손으로 풀어보기

ACAYKP
CAPCAK

1. 위에서 계산했던 DP에 플러스하기
2. 행렬에 동일한 알파벳 존재하면 왼쪽 위엣값 +1 (왜냐면 거기서 연결이 가능한 것을 찾았기 때문, 왼쪽 위가 여태까지 연결해보았던 최대 값이라고 보면 됨)
3. 행렬에 동일한 알파벳 존재하지 않으면, 위엣 값 내려오기
4. 이후에 최대 값 유지하기

0 [0, A, C, A, Y, K, P]
C [0, 0, 1, 1, 1, 1, 1]
A [0, 1, 1, 2, 2, 2, 2]
P [0, 1, 1, 2, 2, 2, 3]
C [0, 1, 2, 2, 2, 2, 3]
A [0, 1, 2, 3, 3, 3, 3]
K [0, 1, 2, 3, 3, 4, 4]

 

코드로 살펴보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

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

        for (int i = 0; i < 2; i++) {
            String[] split = br.readLine().split("");
            inputString[i] = new ArrayList<>();

            for (String s : split) {
                inputString[i].add(s);
            }
        }

        int n = inputString[0].size();
        int m = inputString[1].size();

        int[][] dp = new int[n+1][m+1];


        for (int i = 1; i <= n; i++) {
            String s1 = inputString[0].get(i - 1);
            for (int j = 1; j <= m; j++) {
                String s2 = inputString[1].get(j - 1);
                int max;

                if(s1.equals(s2)) {
                    max = Math.max(dp[i][j-1], dp[i-1][j-1] + 1);
                } else {
                    max = Math.max(dp[i][j-1], dp[i-1][j]);
                }

                dp[i][j] = max;
            }
        }

        System.out.println(dp[n][m]);
    }
}