[JAVA 알고리즘]BAEKJOON 9251번 LCS

LCS

---

문제 설명

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

제한사항

• 시간 제한 0.4초

입출력 예

input	return
ACAYKP CAPCAK	4

---

문제 분석

문자열 2개가 주어지고 두 문자열을 비교를 하면서 순서가 섞이지 않게 연속된 같은 문자의 길이를 구해야 한다.

문자열은 최대 1000글자로 이루어져 단순하게 비교할 경우 n^2의 시간복잡도를 가지는데 시간제한 0.4초에는 브루트포스 알고리즘으로는 시간초과가 날듯하다.

반복적으로 비교를 하기 때문에 다이나믹 프로그래밍으로 예상하고 문제를 파악해야 한다.

아직 규칙을 한눈에 파악하기 힘들어 먼저 표를 그려 규칙을 확인을 해본다.

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

문자열을 끊어서 연속되는 문자의 수를 구해보면 비교를 하기 쉬워진다.

문자가 같을 경우에 수가 증가를 하는데, 한 글자가 계속 포함되면 안 되기 때문에 두문자열의 이전 값에서 1이 증가하는 걸 볼 수 있다.

문자가 다를 경우에는 두문자의 이전 값 중에서 큰 값이 따라오는 걸 알 수 있다.

이제 규칙을 찾았으니 2차 배열로 치환해서 풀어보면 된다.

손으로 풀기

1. 두 문자열을 문자열 배열로 각각 입력받는다.
2. 다이나믹 프로그래밍에서 타뷸레이션방식을 사용하기 위해 dp를 2차 배열로 생성한다.
3. 문자가 같을 경우 두 문자열의 이전 값을 기준으로 수를 상승시키기 위해서는 dp배열을 문자열보다 1 크게 초기화해 준다.
4. 두 문자열을 반복하도록 이중 for문을 반복하는데, dp배열을 기준으로 하기 위해 1부터 문자열의 크기만큼 반복을 해준다.
5. 반복을 하면서 두 문자열을 비교하고 같을 경우, 행과 열에 -1을 한 위치에 + 1을 해준다.
6. 두 문자열이 다를 경우, 행을 -1 한 위치와 열을 -1 한 위치 중 큰 값을 가져온다.
7. dp에서 두 문자열의 크기에 위치의 값을 출력한다.

나의 문제풀이

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        // 문자열 입력
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] firstStr = bufferedReader.readLine().split("");
        String[] secondStr = bufferedReader.readLine().split("");
        
        int[][] dp = new int[firstStr.length + 1][secondStr.length + 1];
        for (int i = 1; i <= firstStr.length; i++) {
            for (int j = 1; j <= secondStr.length; j++) {
                if (firstStr[i - 1].equals(secondStr[j - 1])) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[firstStr.length][secondStr.length]);
    }
}

다이나믹 프로그래밍은 엄청 여러가지 유형으로 나오는데, 아직까지도 적응이 안된다. 점화식으로 파악하기가 힘들어 일단 표를 만들어 규칙을 파악하는 중인데, 간혹 표를 만들어서 파악이 안될 경우도 있고, 표를 만들어서 풀지 못하는 문제도 있어 여러 유형을 접하면서 정리를 해 동일한 유형이 나왔을 경우 활용을 할 수 있도록 해야겠다.

---

알고리즘 분류

• 문자열
• 다이나믹 프로그래밍

문제 출처 - https://www.acmicpc.net/problem/9251

9251번: LCS