#9251 : LCS

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

 

2022.03.30

"ACAYKP"와 "CAPCAK"를 예로 들어 설명하겠다.

 

다음의 표를 보자.

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

 

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

(1, 1)은 "ACAYKP"의 첫 번째 글자까지와 "CAPCAK"의 첫 번째 글자까지,

즉 "C"와 "A"를 비교하였을 때 가장 긴 공통 부분수열의 길이이다.

"C"와 "A"는 서로 공통된 글자가 하나도 없으므로 (1, 1)에는 0이 들어간다.

 

(3, 2)는 "ACAYKP"의 세 번째 글자까지와 "CAPCAK"의 두 번째 글짜까지,

즉 "CA"와 "ACA"를 비교하였을 때 가장 긴 공통 부분수열의 길이이다.

"CA"와 "ACA"에서는 "CA"가 가장 긴 공통 부분수열이므로 (3, 2)에는 2가 들어간다.

 

이러한 방식으로 모든 칸을 채운 것이 바로 위의 표이다.

"ACAYKP"와 "CAPCAK"의 가장 긴 공통 부분 수열의 길이는 바로 (6, 6)에 쓰인 값이다! 따라서 정답은 4이다.

 

그럼 이제 이 표를 만들어내는 프로그램을 짜면 된다.

인간인 우리는 ACAYKP와 CAPCAK를 종이에 적어놓고 동그라미를 쳐서 글자를 일일이 세면 위의 표를 완성할 수 있다.

그러나 컴퓨터는 우리가 시킨 것만 하는 기계다... 절대 그렇게 알잘딱깔센으로 세어주지 않는다.

컴퓨터가 위의 표를 빠르게 만들어내게 하려면 어떤 알고리즘을 짜야 할까?

 

컴퓨터를 효율적으로 일하게 하려면, 데이터의 규칙성을 찾아야 한다.

표를 다시 한 번 살펴보자. 언제 숫자가 증가하는가?

왼쪽 위에서 오른쪽 아래로 훑으면서, 숫자가 증가한 시점에 모두 표시를 해보자.

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

규칙이 보인다.

 

동일한 알파벳이 만나는 지점에서 숫자가 증가하였다.

그리고 이 숫자들은 정확히 자신의 왼쪽 위 대각선에 있는 숫자보다 1만큼 증가하였다.

 

동일한 알파벳이 만나는 지점을 제외한 모든 칸에서는

자신의 윗칸과 자신의 왼쪽 칸에 있는 수 중 더 큰 쪽과 값이 같다.

 

이를 이용하면 아래의 코드와 같이 간단하게 표를 완성할 수 있다.

각 수는 자신보다 인덱스가 적은 숫자에 차곡차곡 덧셈을 해와서 도출되므로 DP 알고리즘이 적용된다.

표를 완성한 뒤, (6, 6)에 있는 값을 화면에 출력하면 문제가 해결된다.

 

2차원 정수 배열 dp를 완성한 모습. ArrayIndexOutOfBounds 오류를 막기 위해, 0으로 채워진 여유분을 배열의 왼쪽과 위에 남겨두었다.

 

코드

Java(2022.03.30)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//문자열 두 개 읽어오기
		char[] a = br.readLine().toCharArray();
		char[] b = br.readLine().toCharArray();
		//각 문자열의 길이 알아내기
		int len1 = a.length;
		int len2 = b.length;
		//두 문자열의 길이에 맞는 크기의 2차원 정수 배열 만들기
		int[][] dp = new int[len1+1][len2+1];
		//2차원 정수배열의 내용물 채우기
		for(int i = 1; i<len1+1; i++) {
			for(int j = 1; j<len2+1; j++) {
				if(a[i-1] == b[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[len1][len2]);	//가장 오른쪽 아래의 데이터 출력
	}

}