[백준/Java] 9251번 : LCS

문제

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

두 문자열의 LCS(Longest Common Subsequence, 최장 공통 부분 수열)을 구하는 문제

풀이 1 - 재귀 + dp

• a와 b는 배열 형식으로 주어졌다고 가정
• l(i, j)는 a(0..i), b(0..j) 사이의 lcs 길이로 정의
• l(i, j)의 재귀적인 구조를 찾기
• 두 문자열을 탐색하다가 다른 문자가 나오면
  • a[k]값을 무시하고 a[k+1], b[k]부터 다시 lcs 탐색하거나
  • b[k]값을 무시하고 a[k], b[k+1]부터 다시 lcs 탐색하기
  • -> 두 분기 중 매칭 수가 더 많은 부분을 리턴
• 같은 문자가 나오면 
  • a[k], b[k]값이 같으므로 a[k+1], b[k+1]부터 계속 lcs 탐색하고 그 결과에 1을 더해준 후 리턴
• base case : i 또는 j가 0일 때 (배열 a 또는 b가 공집합인 경우) lcs가 0개이므로 0을 리턴

# 점화식
if a[i] == b[j]:
	l(i, j) = l(i-1, j-1) + 1 # i와 j 모두 채택한 경우의 lcs
if a[i] != b[j]:
	l(i, j) = max(l(i-1, j), l(i, j-1)) # j를 채택한 경우, i를 채택한 경우 중 lcs가 더 큰 값
if a[i] == 0 or b[j] == 0: 
	l(i, j) = 0 # a와 b가 모두 공집합일 때 lcs는 0

 

코드 1

import java.io.*;
import java.util.*;

public class Main {
    static char[] a, b;
    static int len1, len2;
    static int[][] d;

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

        String s1 = br.readLine();
        String s2 = br.readLine();

        len1 = s1.length();
        len2 = s2.length();

        // 인덱스 1부터 사용하기 위해 크기를 len+1로 설정
        a = new char[len1 + 1];
        b = new char[len2 + 1];

        for (int i = 1; i <= len1; i++) {
            a[i] = s1.charAt(i - 1); // 1부터 시작하도록 저장
        }
        for (int i = 1; i <= len2; i++) {
            b[i] = s2.charAt(i - 1); // 1부터 시작하도록 저장
        }

        d = new int[len1 + 1][len2 + 1];

        // 메모이제이션 배열을 -1로 초기화
        for (int[] row : d) {
            Arrays.fill(row, -1);
        }

        System.out.println(lcs(len1, len2)); // 전체 문자열을 비교
    }

    static int lcs(int i, int j) { // a[1..i], b[1..j]에서의 LCS 길이
        if(a[i]==0 || b[j]==0)
            return 0;
        if(d[i][j] != -1){
            return d[i][j];
        }
        if(a[i] == b[j]){
            return d[i][j] = lcs(i-1, j-1) + 1;
        }else{
            return d[i][j] = Math.max(lcs(i-1, j), lcs(i, j-1));
        }
    }
}

 

풀이 2 - dp

코드 2

import java.io.*;
import java.util.*;

public class Main {
    static char[] a, b;
    static int len1, len2;
    static int[][] d;

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

        String s1 = br.readLine();
        String s2 = br.readLine();

        len1 = s1.length();
        len2 = s2.length();

        a = new char[len1 + 1];
        b = new char[len2 + 1];

        for (int i = 1; i <= len1; i++) {
            a[i] = s1.charAt(i - 1); // 1부터 시작하도록 저장
        }
        for (int i = 1; i <= len2; i++) {
            b[i] = s2.charAt(i - 1); // 1부터 시작하도록 저장
        }

        d = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (a[i] == b[j])
                    d[i][j] = d[i - 1][j - 1] + 1;
                else
                    d[i][j] = Math.max(d[i - 1][j], d[i][j - 1]);
            }
        }

        System.out.println(d[len1][len2]);
    }
}