백준 9252 LCS 2

백준 - LCS 2

아이디어

최대 LCS 수 구하기

• DP[i][j] : 첫번째 문자열 i번째 문자까지 사용했을때 + 두번째 문자열 j번째 문자까지 사용했을 때 최장 공통 부분 수열
  • DP[i][j]는 아래 2가지 경우가 있음
    • case 1 : A[i] == B[j] : DP[i-1][j-1] + 1
    • case 2 : A[i] != B[j] : Max(DP[i][j-1], DP[i-1][j])
      • 두 문자 중 하나만 쓴 경우의 최대
      • 왜냐면 DP[i][j]의 값은 모르나 DP[i-1][j], DP[i][j-1]의 값은 알기에
      • DP[i][j]처럼 두 문자를 동시에 추가한다고 해서 case1처럼 경우의 수가 증가하지 않음
        • 왜냐하면 두 문자는 다르다는 경우의 수이니깐
      • 두 문자 중 하나의 문자를 제거했을 경우들 중 최대값이 DP[i][j]와 동일함
        • 두 문자 다 있나 하나만 있나 최대값은 동일함

LCS 문자 추적하기

• 이전에 LCS 최대 값 구할 때
  • 두 문자열의 i번째, j번째 문자가 같을 때
    • 경우의 수 +1
  • 두 문자열의 i번째, j번째 문자가 다를 때
    • 한 문자만 포함했을 때 최대 경우의 수
• 역순으로 따라감
  • LCS 마지막 위치에서 시작
    • 해당 위치의 문자가 같을 경우
      • 해당 문자 추가
      • 왼쪽 대각선으로 이동 DP[i-1][j-1]
        • DP[i][j] = DP[i-1][j-1] + 1 로 구했었으니 역순으로 왼쪽 대각선으로 이동
    • 해당 위치의 문자가 다를 경우
      • 왼쪽 혹은 위쪽 중 큰 값이 있는 곳으로 이동
        • DP[i][j] = Max(DP[i-1][j], DP[i][j-1)]로 구했었음
        • 다시 역순으로 큰 값으로 이동
  • 계속 반복하다가 0, 0 위치로 이동했을 시 종료

코드

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

public class Main {
    private static long[][] DP;
    private static ArrayList<Character> Path;
    private static char[] A;
    private static char[] B;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 두 문자열 입력받기
        A = br.readLine().toCharArray();
        B = br.readLine().toCharArray();
        DP = new long[A.length + 1][B.length + 1];
        Path = new ArrayList<Character>();
        // 2. DP 점화식 도입
        for(int i = 1; i <= A.length; i++) {
            for(int j = 1; j <= B.length; j++) {
                // 문자열이 같다면 이전 기록 + 1
                if(A[i - 1] == B[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]); 
                }
            }
        }
        // 3. 최대 LCS 출력
        System.out.println(DP[A.length][B.length]);
        // 4. LCS 문자 생성
        getText(A.length, B.length);
        // 5. LCS 문자 출력
        for(int i = Path.size() - 1; i >= 0; i--) {
            System.out.print(Path.get(i));
        }
    }
    private static void getText(int r, int c) {
        if(r == 0 || c == 0) return ;
        // 문자 같은 경우 -> 정답에 추가하고 왼쪽 대각선 위로 이동
        if(A[r - 1] == B[c - 1]){
            Path.add(A[r-1]);
            getText(r - 1, c - 1);
        }
        // 다르면 왼쪽과 위쪽 중 큰 수로 이동
        else {
            if(DP[r - 1][c] > DP[r][c - 1]) {
                getText(r - 1, c);
            }
            else {
                getText(r, c-1);
            }
        }
    }
}

• 입력받은 A와 B문자열은 toCharArray() 메서드로 배열화 시켜서 index가 0부터 시작
  • 같은 문자인지 검사할 때 A[i-1] == B[j-1]로 검사

출처

• #6-7 DP, 동적계획법(String Matching)(최장 공통 부분 수열 해설) I CODE TREE I Intermediate Low I 코드트리
• 알고리즘 코딩테스트 문제풀이 강의 - 90 최장 공통 부분 수열 구하기 (백준 9252)