[백준 알고리즘] Q9521 LCS - 동적계획법

1. Java 구현

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

public class Main {

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

        String first = br.readLine();
        String second = br.readLine();
        boolean[][] visited = new boolean[1000][1000];
        int[][] values = new int[1000][1000];
        bw.write(LCS(visited, values, first, second, first.length() - 1, second.length() - 1) + "\n");
        bw.close();
    }

    public static int LCS(boolean[][] visited, int[][] values, String first, String second, int firstIndex, int secondIndex) {
        if(firstIndex < 0 || secondIndex < 0) {
            return 0;
        }
        if(visited[firstIndex][secondIndex]) {
            return values[firstIndex][secondIndex];
        }
        visited[firstIndex][secondIndex] = true;
        if(first.charAt(firstIndex) == second.charAt(secondIndex)) {
            values[firstIndex][secondIndex] = 1 + LCS(visited, values, first, second, firstIndex - 1, secondIndex - 1);
            return values[firstIndex][secondIndex];
        } else {
            values[firstIndex][secondIndex] = Math.max(LCS(visited, values, first, second, firstIndex - 1, secondIndex)
                    , LCS(visited, values, first, second, firstIndex, secondIndex - 1));
            return values[firstIndex][secondIndex];
        }
    }
}

2. 코드설명

 이 문제는 입력받은 문자열의 크기는 달라도 되는 문제였다. 그러나 그 부분은 중요하지 않다. 이 문제는 연속적인 문자열을 찾는 것이 아닌 부문 문자열을

 찾는 문제이다. ABC, ABDECF는 ABC라는 공통적인 부분 문자열 가진 셈이다. 이 문제를 풀기 위해서는 메모리제이션을 사용해야 한다. 

 사용하지 않으면 시간초과 및 StackOverflow 발생한다. 이 문제는 문자열을 첫자리부터 비교하는 것이 아닌, 끝자리부터 비교해서 확인해야 한다.

3. Pain Point

 처음에 구현했을 때, Memorization을 사용하지 않았기 때문에 StackOverflow 및 시간초과로 인해 문제가 풀리지 않았다.

 방문유무와 방문한 결과를 기억한 덕분에, 이미 처리한 내용에 대해서는 재귀를 하지 않아서 StackOverflow 및 시간초과 문제를 해결할 수 있었다.

 쉬운 문제가 아니였다. 어려웠다. 점화식을 발견하는 것이 어려웠다.