[Boj_9251] LCS

📎 문제 링크

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

9251번: LCS

 

▸ 문제

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

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

 

▸ 입력

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

 

▸ 출력

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

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 1
• 🔔  문제 유형 : 다이나믹 프로그래밍, 문자열
• 💬  풀이 언어 : JAVA

 

🔍 동적 계획법(Dynamic Programing, DP )이란 ?

• 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다.
• DP에서는 작은 부분의 문제들이 반복되기 때문에 분할 정복과는 다르다.
  • 분할 정복에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

 

🔸 Dynamic Programing 방법

• 모든 작은 문제들은 한 번만 풀어야 한다.
• 따라서 정답을 구한 작은 문제를 메모해 놓고,
• 그보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 메모해 두었던 작은 문제의 결괏값을 이용한다.

 

🔸  Dynamic Programing 조건

• 최적 부분 구조 (Optimal Substructure)
  • 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 말한다.
  • 그렇기 때문에, 특정 문제의 정답은 문제의 크기와 상관없이 동일하다.
• 중복되는 부분 문제 (Overlapping Subproblem)
  • 동일한 작은 문제를 반복적으로 해결해야 하는 경우를 말한다.
  • 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하므로 부분 문제가 중복되지 않는 경우 사용할 수 없다.

 

🔍 Memoization?

• DP를 구현하는 방법 중 한 종류로,
• 한 번 구현한 결과를 메모리 공간에 메모해 두고, 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

 

🔍 최장 공통 부분 수열(Longest Common Subsequence, LCS)이란 ?

• LCS는 Longest Common Subsequence의 약자로 최장 공통 부분 문자열을 말한다.
• Subsequence는 부분 수열이라는 뜻으로 연속적이지 않아도 되는 문자열이다.
• 한마디로, 두 문자열을 비교할 때 공통적으로 나타나는 부분 순서들 중 가장 긴 것이다.
• LCS는 최적화를 해야 하는 문제이기 때문에 동적계획법(DP)을 사용해야 가장 효율적으로 구할 수 있다.

 

🤔 문제 풀이

LCS 문제의 경우, 부분 수열에서 '순서'가 지켜지기 때문에 각 문자열들의 문자들을 서로 비교하며

문자가 서로 같을 때 값을 1씩 증가시키면서 누적합을 구했다.

 

문제의 예시대로 테이블을 만들어 규칙을 찾아보자

• str1 = ACAYKP
• str2 = CAPCAK 

		A	C	A	Y	K	P
C
A
P
C
A
K

 

str1의 첫 번째 문자인 'A'를 기준으로 str2의 문자들을 비교해 보면 다음과 같다.

		A	C	A	Y	K	P
	0	0	0	0	0	0	0
C	0	0
A	0	1
P	0	1
C	0	1
A	0	1
K	0	1

여기서 잘 고민해야 하는 것이 'A'와 'CAPCA'를 비교할 때,

두 번째 'A'가 오더라도 1을 더하는 것이 아니라  {C, A, P, C, A}와 {A}의 최장 부분 수열은 {A} 하나뿐이므로 1이 된다.

 

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

{C}와 {A, C}의 부분 수열은 {C}이고,

{C, A, P, C}와 {A, C}의 부분 수열은 {A, C}로 +1이 증가한다.

이때, {A, C}의 순서도 고려해주어야 한다. 그러므로 {C, A}는 해당 부분의 수열이 될 수 없다.

 

이러한 규칙을 통해, 표를 모두 채우면 아래와 같다.

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

표를 채우다 보면 규칙을 찾을 수 있다.

 

각 열을 채워나갈 때, 자신과 같은 문자가 있다면 +1, 그렇지 않다면 이전 행의 원소 또는 열의 원소 중 큰 값을 기준으로 채우면 된다.

 

그런데, 같은 문자가 있을 경우 어떤 수를 +1해야 할까

 

아래 예시를 들어보자

(0, 1)을 본다면 {C}와 {A, C}의 공통분모인 'C'를 의미하며 1의 값이 들어온다.

(1, 2)를 본다면 {C, A}와 {A, C, A}의 공통 수열인 {C, A}가 되어 2의 값이 들어온다.

 

즉, {C}와 {A, C}에서 'A'라는 공통 원소가 추가된 것이다.

정리하면 i번째 원소와 j번째 원소가 같다면 (i-1, j-1)의 LCS 길이의 +1이 된다.

 

이를 활용하여 코드를 작성해 보면 아래와 같다.

 

✔ 최종 코드

 메모리 : 15828KB 
 시간 : 96ms

import java.io.*;

public class Main {
    static char[] str1, str2;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 두 문자열 입력
        str1 = br.readLine().toCharArray();
        str2 = br.readLine().toCharArray();

        bw.append(lcs(str1.length, str2.length) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static int lcs(int a, int b) {
        dp = new int[a+1][b+1];
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= b; j++) {
                // 같은 문자가 들어온다면
                // 모든 수열에 같은 문자가 추가되는 경우
                // 그러므로 대각선에 있는 값에 +1
                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]);
            }
        }
        return dp[a][b];
    }
}

 

 

 

 

 

📃 reference

• https://st-lab.tistory.com/139
• https://infodon.tistory.com/78