LCS

LCS

 

백준 9251번 문제

https://www.acmicpc.net/problem/9251

9251번: LCS

 

 

 

1. 문제

 

 

 

2. 풀이 방법

2.1 dp

이 문제는 dp를 사용해서 풀 수 있다.

다만 주어지는 문자열이 2개이기 때문에 2개의 변수를 사용해서 점화식을 만들어야 한다.

 

d[i][j]를 문자열_1의 i번째와 문자열_2의 j번째까지의 LCS라고 하자.

그러면 d 행렬의 가장 오른쪽 아래있는 값이 이 문제의 답이 될 것이다.

 

예시로 주어진 문자열로 d의 원소 값을 하나씩 채우면서 점화식을 찾아본다.

 

 

2.1.1 마지막 문자가 같지 않을 경우

 

[dp 예시_그 1]

 

코드상에서 점화식 계산을 수월하게 하기 위해서 각 문자열의 앞에 비어있는 값을 추가하였다.

비어있는 문자와 어떤 문자열을 비교해도 LCS는 0이기 때문에 첫 행과 열을 0으로 채워 넣었다.

 

 

[dp 예시_그 2]

 

d[1][1]은 A와 C의 LCS값이다.

일치하는 문자가 하나도 없기 때문에 그 값은 0이 된다.

 

 

[dp 예시_그 3]

 

d[1][2]는 AC와 C의 LCS값이다.

C가 일치하고 이것이 최대이기 때문에 그 값은 1이 된다.

 

 

[dp 예시_그 4]

 

d[1][3]은 ACA와 C의 LCS값이다.

새로 추가된 A와 C는 같지 않다. 그렇기 때문에 새로 추가된 A는 있으나 없으나 d[1][3]의 값에 영향을 주지 않는다.

따라서 이 경우 d[1][3]은 AC와 C의 LCS값(d[1][2])이 된다.

 

 

[dp 예시 _그 5]

 

위와 같은 방식으로 첫 번째 행을 채울 수 있다.

 

 

[dp 예시 그_6]

 

d[2][1]은 A와 CA의 LCS값이다.

A가 하나 일치하고 이것이 최대이기 때문에 d[2][1]은 1이 된다.

 

 

[dp 예시_그_7]

 

d[2][2]는 AC와 CA의 LCS값이다.

각 문자열의 마지막 값인 C와 A는 같지 않다.

따라서 C가 있어도 A와 CA의 LCS값(d[2][1])에서 새롭게 일치하는 문자가 추가되지는 않기 때문에 d[2][2] = d[2][1]이 될 수 있다.

반대로 A가 있어도 AC와 C의 LCS값(d[1][2])에서 새롭게 일치하는 문자가 추가되지는 않기 때문에 d[2][2] = d[1][2]이 될 수도 있다.

 

LCS는 최장 공통부분 수열이기 때문에 이 두 가지 경우의 값 중 가장 큰 값을 선택하면 된다.

 

따라서 비교하는 마지막 문자의 값이 다를 경우

 

d[i][j] = Max(d[i][j - 1], d[i - 1][j]) 가 성립한다.

 

 

2.1.2 마지막 문자가 같을 경우

 

[dp 예시_그 8]

 

d[2][3]은 ACA와 CA의 LCS값이다.

각 문자열의 마지막 문자가 A로 일치하는 상황이다.

때문에 d[2][3]은 마지막 문자 A가 없을 때의 LCS값(d[1][2])에 1을 더해준 값이 된다.

 

즉 비교하는 문자열의 마지막 문자가 같을 경우

 

d[i][j] = d[i - 1][j - 1] + 1 이 성립한다.

 

이 경우 d[i - 1][j]와 d[i][j - 1]는 고려하지 않아도 된다.

d[i - 1][j]와 d[i][j - 1]는 d[i - 1][j - 1]에서 하나의 문자가 추가된 경우인데 d[i - 1][j - 1]에 하나의 문자가 추가된다고 LCS값이 d[i - 1][j - 1] + 1을 초과하는 경우는 없기 때문이다.

 

 

[dp 예시_그 9]

 

위에서 구한 점화식을 사용해서 행렬을 전부 다 채울 수 있다.

그리고 결과적으로 ACAYKP와 CAPCAK의 LCS값 4를 구할 수 있다.

 

 

 

3. 코드

3.1 dp

두 개의 문자열을 받아서 각 문자열의 LCS값을 저장하는 배열 memorization을 채우는 메서드

 

[dp]

public static int dp(int[][] memorization, String firstString, String secondString) {

    for (int i = 1; i < memorization.length; i++) {
        for (int j = 1; j < memorization[0].length; j++) {
            if (firstString.charAt(i - 1) == secondString.charAt(j - 1)) {
            /// 마지막 문자가 같을 때 점화식
                memorization[i][j] = memorization[i - 1][j - 1] + 1;
            } else {
            /// 마지막 문자가 다를 때 점화식
                memorization[i][j] = Math.max(memorization[i - 1][j], memorization[i][j - 1]);
            }
        }
    }

    return memorization[memorization.length - 1][memorization[0].length - 1];
}

 

 

3.2 main

[main]

public static void main(String[] args) throws IOException {
    //*** 입력, memorization 초기화
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    String firstString = st.nextToken();

    st = new StringTokenizer(br.readLine());
    String secondString = st.nextToken();

    int[][] memorization = new int[firstString.length() + 1][secondString.length() + 1];
    //***

    int result = dp(memorization, firstString, secondString);
    System.out.println(result);
}

 

 

 

4. 전체 코드

[전체 코드]

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

public class LCS {

    public static int dp(int[][] memorization, String firstString, String secondString) {

        for (int i = 1; i < memorization.length; i++) {
            for (int j = 1; j < memorization[0].length; j++) {
                if (firstString.charAt(i - 1) == secondString.charAt(j - 1)) {
                    memorization[i][j] = memorization[i - 1][j - 1] + 1;
                } else {
                    memorization[i][j] = Math.max(memorization[i - 1][j], memorization[i][j - 1]);
                }
            }
        }

        return memorization[memorization.length - 1][memorization[0].length - 1];
    }

    public static void main(String[] args) throws IOException {
        //*** 입력, memorization 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String firstString = st.nextToken();

        st = new StringTokenizer(br.readLine());
        String secondString = st.nextToken();

        int[][] memorization = new int[firstString.length() + 1][secondString.length() + 1];
        //***

        int result = dp(memorization, firstString, secondString);
        System.out.println(result);
    }
}