백준9251 LCS

9251번: LCSBaekjoon Online Judge

Solution

• 18444 kb / 152 ms

접근방식

• LCS는 Logest Common Subsequence의 약자로, 서로 다른 두 수열 혹은 문자열이 주어졌을 때, 양쪽 모두가 공통적으로 가지고 있는 가장 긴 요소를 찾아내는 문제이다.

• 이 문제를 접근할 때에는 아래와 같이 두 가지 방법으로 접근을 한다.

  • 우선 구하려는 문자열의 범위를 좀 더 작은 단위로 계속 쪼갠다고 생각한다.

    • 길이가 각각 5, 4인 문자열이라면 5-> 4-> 3-> 2-> 1 으로.

  • 두 문자열의 마지막 요소를 기준점으로

    • 두 값이 서로 같다면, 이전까지 구한 lcs 값 + 1을 해주면 되고

    • 두 값이 서로 다르다면, 둘 중 하나를 포기했을 때의 값을 비교하여 더 큰 값으로 선택해주면 된다.

  • 이 규칙을 식으로 표현하면 다음과 같다. 두 문자 ACAYKP와 CAPCAK를 각각 x, y 라고 하고 각각의 길이를 i, j라고 한다면,

    • if x(i) = y(j), LCS(i, j) = LCS(i-1, j-1) + 1

    • if x(i) != y(j), LCS(i, j) = Math.max(LCS(i-1, j), LCS(i, j-1))

  • 그리고 이 식을 재귀호출할 경우, 비교하는 문자열의 길이가 점차 줄어들어 결국 LCS(1, 1)의 범위까지 오게 된다.

• 각각의 요소를 아래와 같이 이차원 배열을 통해서 하나씩 점검한다. (예시)

  

  https://www.inflearn.com/course/알고리즘-강좌/unit/4129

코드

위의 점화식은 top-down 방식으로 생각을 했고, 아래의 코드는 bottom-up 방식으로 구현하였다.

package practice.algorithm.dp;

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

/**
 * https://www.acmicpc.net/problem/9251
 * LCS
 * 18444 kb / 152 ms
 * */
public class Bj9251 {
    private static int[][] c;

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

        c = new int[s1.length()+1][s2.length()+1];

        System.out.println(lcs(s1, s2));
    }

    private static int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        for (int i = 0; i <= n; i++) {
            c[i][0] = 0;
        }

        for (int j = 0; j <= m; j++) {
            c[0][j] = 0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    c[i][j] = c[i-1][j-1] + 1;
                    continue;
                }

                c[i][j] = Math.max(c[i-1][j], c[i][j-1]);
            }
        }

        return c[n][m];
    }
}