LCS(Longest Common Subsequence) 알고리즘 (A), 백준 9251 LCS(JAVA)

LCS 알고리즘을 공부해보자.

 

이 글은 백준 문제집 "LCS"을 바탕으로 합니다!

 

https://www.acmicpc.net/workbook/view/5080

문제집: LCS (baekjoon)

 

 

 

 

첫번째 문제,

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

9251번: LCS

LCS 문제의 전형이라고 볼 수 있습니다.

 

한번 봅시다.

백준 9251 - "LCS"

첫 번째 문제와 함께 LCS 알고리즘을 설명해보겠습니다.

 

"LCS"란, "Longest Common Subsequence", "최장 공통 부분 수열"의 줄임말입니다.

두 문자열이 공통적으로 가지고 있는 부분문자열 중, 가장 긴 것을 찾아내는 것이 목적인 문제입니다.

 

- 부분문자열이란?

"ABCDEFG" 에서 임의의 문자들을 뽑아, "순서대로" 나열한 것입니다. "ABCD"처럼, 선정된 문자들이 연속될 수도 있지만 "AEFG"처럼 연속되지 않아도 됩니다. (연속된 문자열은 "substring"이라고 부릅니다.)

 

두 문자열 "ACAYKP"와, "CAPCAK"의 "공통 부분 수열"은 "AC", "CK", "ACAK", "CAK"이 있습니다.

여기서, 우리가 원하는 것은 통일, 이 중에서 최장 "공통 부분 수열"인 "ACAK" 가 되겠습니다. (한번 해보세요)

 

 

 

 

Dynamic Programming

 

을 사용할 겁니다.

 

1.

우리가, "ACAYKP"와 "CAPCAK"의 "최장 공통 부분 수열", "ACAK" 을 안다고 할 때, 여기에 문자를 하나씩 더한

"ACAYKPZ"와 "CAPCAKZ" 의 "최장 공통 부분 수열"은 무엇일까요?

 

각각의 문자열에 같은 문자를 더했으니, 당연히(?) "최장 공통 부분 수열, 이하 LCS"은 "ACAKZ" 가 되겠지요?

 

즉, A의 어떤 문자(A[i]) 와 B의 어떤 문자(B[j) 가 서로 같다면, 두 문자를 제외한 문자열

 

 - "ACAYKP", "CAPCAK"

 

이 가진 LCS보다 1만큼 더 커진다는 것을 알 수 있습니다. (경우 1)

 

 

2.

그렇다면, 서로 다른 문자를 더한 "ACAYKPZ" 와 "CAPCAKP"는 어떻게 될까요? 서로 다르니, "ACAK"에서 변함이 없을까요?

 

아닙니다. 자세히 보면 "ACAKP"가 새로운 "LCS"가 될 수 있다는 것을 알 수 있습니다.

그리고 "ACAKP" 는 "ACAYKP"와 "CAPCAKP" 의 "LCS"입니다! 다시 말해서, "ACAYKPZ"에서 'Z' 는 없어도 되는 것이죠.

 

즉, A의 어떤 문자(A[i]) 와 B의 어떤 문자(B[j) 가 서로 다르다면, 두 문자 중 하나를 제외한 문자열 

 

 - "ACAYKP", "CAPCAKP" 또는

 - "ACAYKPZ", "CAPCAK"

 

이 가진 LCS 중 큰 것이 우리가 원하는 LCS가 되게 됩니다. (이 경우에선 후자)

 

 

 

-----------------------------------------------------------------------------------------------------------------------------------

 

이렇게, 우리는 두 문자열 A와 B의 인덱스 i, j를 가지고 DP를 할겁니다. 이렇게요.

 

먼저 (M + 1) * (N + 1) 크기를 가진 2차원 DP 배열을 만들어 줍니다. (M : A의 길이, N : B의 길이)

그리고, 각각의 (i, j) 위치에 "A의 i번째 문자까지, B의 j번째 문자까지 이용하여 만든 LCS의 값"을 저장합니다.

 i번째 인덱스 아닙니다. i번째 문자입니다. (0번째 인덱스는 1번째 문자와 같습니다)

 

 

경우 1) A[i] = B[j]

경우 2) A[i] != B[j]

 

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

1번 경우라면, DP[i][j] = DP[i - 1][j - 1] + 1 인 것을 알 수 있습니다.

위의 "ACAYKPZ"와 "CAPCAKZ"에 해당합니다.

 

2번 경우라면, DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]) 입니다.

위의 "ACAYKPZ" 와 "CAPCAKP"에 해당합니다.

 

끝)

 

코드 - JAVA

import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        
        int[][] dp = new int[str1.length + 1][str2.length + 1];
        for (int i = 1; i <= str1.length; i++) {
            for (int j = 1; j <= str2.length; j++) {
                if (str1[i - 1] == str2[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.print(dp[str1.length][str2.length]);
    }
}

다음글

2020/07/10 - [공부] - LCS(Longest Common Subsequence) 알고리즘 (B), 백준 9252 LCS2(JAVA)

LCS(Longest Common Subsequence) 알고리즘 (B), 백준 9252 LCS2