[백준] 9251번 : LCS

9251번: LCS

# 문제

 

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

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

 

# 입력

 

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

 

# 출력

 

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

 

# 예시 입력

ACAYKP
CAPCAK

# 예시 출력

4

---

이 문제는 다양한 알고리즘으로 풀 수 있다고 한다. 대표적으로 동적 프로그래밍과 백트래킹이 사용되는 것 같다. LCS는 처음 접할 뿐더러 어떻게 접근해야하는지 조차 모르겠어서 나무위키에 쓰여진 알고리즘을 보고 풀었다. 알고리즘 자체는 여느 동적 프로그래밍 방법과 다르지 않았다. 각 칸마다 숫자가 쓰여져 있는 n X m 테이블(table[][])에서 table[n][m]까지 가는데 갖을 수 있는 MAX 값, 최적해를 찾아 나가는 문제와 유사했다.

ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

 

위의 예시 입력을 갖고 LCS 알고리즘을 알아보자.

 

String a = "ACAYKP";
String b = "CAPCAK";

일 때 LCS를 구하기 위해선 맨 앞에 공백같은 의미없는 문자를 넣어주어야 한다.

 

String a = " " + a;

String b = " " + b;

 

이제 a의 길이(m), b의 길이(n)를 가지고 m X n 행렬을 준비한다.

 

int[][] dp = new int[m][n];

 

dp[0~m][0], dp[0][0~n]에 0을 대입한다. (배열 생성 시 초기값이 0이므로 굳이 안해줘도 된다.)

 

IntStream.range(0, m).forEach(i->dp[i][0] = 0;);

IntStream.range(0, n).forEach(j->dp[0][j] = 0;);

 

그럼 다음과 같은 표가 만들어질 것 이다. 이 표는 연산의 각 단계에서 LCS 수열을 저장하는데 이용된다. 두 번째 행과 두 번째 열은 Ø로 채워지는데, 빈 수열이 비어있지 않은 수열과 비교될때 가장 긴 공통 부분 수열이 항상 빈 수열이 되기 때문이다.

LCS(R1, C1)는 각 수열의 첫 원소를 비교함으로써 결정된다.

 

	Ø	A	C	A	Y	K	P
Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
C	Ø	↑Ø	↖C	←C	←C	←C	←C
A	Ø
P	Ø
C	Ø
A	Ø
K	Ø

* Row 1

1) A != C 이므로 LCS(R1, C1)은 LCS(R0, C1)과 LCS(R1, C0) 중 긴 것을 가지게 된다. 그러나 둘다 Ø 이므로 상관없다.

2) C == C 이므로 LCS(R1, C2)는 LCS(R0, C1)에 'C'를 붙인다. (이 문제에선 1을 더하는 것이 맞다.)

3) A != C 이므로 LCS(R1, C3)은 LCS(R0, C3)과 LCS(R1, C2) 중 긴 것을 가지게 된다. LCS(R1, C2)가 더 길다.

4) Y != C 이므로 LCS(R1, C4)는 위와 왼쪽 것 중에 긴 것을 가지게 되는데 왼쪽 것이 더 길다.

5) K != C이고 P != C 이므로 4)와 동일한 값을 가진다.

---

	Ø	A	C	A	Y	K	P
Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
C	Ø	↑Ø	↖C	←C	←C	←C	←C
A	Ø	↖A	←A & ↑C	↖CA	←CA	←CA	←CA
P	Ø
C	Ø
A	Ø
K	Ø

* Row 2

1) A == A 이므로 LCS(R2, C1)는 LCS(R1, C0)에 'A'를 붙인다. (혹은 1을 더한다.)

2) C != A 이므로 LCS(R2, C2)은 왼쪽과 위 값중에 더 긴 것을 가진다. 둘 다 1의 길이를 가지므로 둘 다 가질 수 있다. (숫자로 표현하면 그냥 1만 쓰면 된다.)

3) A == A 이므로 LCS(R2, C3)는 LCS(R1, C2)에 A를 붙인다.

4) Y != A 이므로 LCS(R2, C4)는 왼쪽, 위쪽 중 긴 것인 왼쪽 것을 가진다.

5) K != A, P != A 이므로 4)와 동일하다.

---

	Ø	A	C	A	Y	K	P
Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
C	Ø	↑Ø	↖C	←C	←C	←C	←C
A	Ø	↖A	←A & ↑C	↖CA	←CA	←CA	←CA
P	Ø	↑A	↑A & ↑C	↑CA	←CA	←CA	↖CAP
C	Ø
A	Ø
K	Ø

* Row 3

1) A != P 이므로 왼쪽과 위쪽 중 긴 위쪽 값을 가져온다.

2) C != P 이므로 왼쪽과 위쪽 중 긴 쪽을 가져오는데 어짜피 상관 없으므로 위쪽 것을 가져오자.

3) A != P 이므로 위쪽게 더 기니까 위쪽 것을 가져온다.

4) Y != P 이므로 LCS(R3, C4)는 LCS(R2, C4)와 LCS(R3, C3)의 값 중 큰 것을 가져오는데 둘 다 동일하다.

5) K != P ...

6) P == P 이므로 LCS(R3, C6)은 LCS(R2, C5)에 'P'를 붙인다.

---

	Ø	A	C	A	Y	K	P
Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
C	Ø	↑Ø	↖C	←C	←C	←C	←C
A	Ø	↖A	←A & ↑C	↖CA	←CA	←CA	←CA
P	Ø	↑A	↑A & ↑C	↑CA	←CA	←CA	↖CAP
C	Ø	↑A	↖AC	←AC	←AC	←AC	↑CAP
A	Ø	↖A	↑AC	↖ACA	←ACA	←ACA	←ACA
K	Ø	↑A	↑AC	↑ACA	←ACA	↖ACAK	←ACAK

위와 같은 방법으로 Row 7 까지 진행하면 표를 완성할 수 있다. 구하고자 하는 값은 table[m-1][n-1]이므로 'ACAK'가 답이다. LCS 길이를 구한다면 4가 답이 된다.

 

# 알고리즘

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

# Whole Code </> - Java 11

public class Main {

    static int getAnswer(String A, String B){

        int m = A.length(), n = B.length();
        int[][] dp = new int[m][n];

        IntStream.range(0, m).forEach(i->dp[i][0] = 0);
        IntStream.range(0, n).forEach(j->dp[0][j] = 0);

        for(int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if(A.charAt(i) == B.charAt(j))
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String A = sc.nextLine();
        String B = sc.nextLine();
        if(A.length() > 1000 || B.length() > 1000) System.exit(0);

        A = " " + A.toUpperCase();
        B = " " + B.toUpperCase();

        System.out.printf("%d\n", getAnswer(A, B));
    }
}