[백준알고리즘-JAVA]9251번 풀이(LCS) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 9251번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 9251 (LCS)

문제

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

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

입력

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

출력

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

 

입력 예제

ACAYKP
CAPCAK

출력 예제

4

성공코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	static char[] str1;
	static char[] str2;
	static Integer[][] dp;
	static int max = Integer.MIN_VALUE;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		str1 = br.readLine().toCharArray();
		str2 = br.readLine().toCharArray();
		
		dp = new Integer[str1.length][str2.length];


		System.out.println(lcs(str1.length-1, str2.length-1));
}
	public static int lcs(int a, int b) {
		
		if(a<0||b<0)
			return 0;
		
		if(dp[a][b]==null) {
			dp[a][b]=0;
			if(str1[a] == str2[b])
				dp[a][b] = lcs(a-1, b-1)+1;
			else
				dp[a][b] = Math.max(lcs(a-1,b), lcs(a,b-1));
		}
		
		return dp[a][b];
	}

}

LCS문제는 DP문제에 있어서 가끔 나오는 문제 중 하나입니다. 바로 가장 긴 공통된 부분 수열 문제로 이러한 문제를 풀 때 규칙을 잘 발견해야 합니다. 기본적으로 첫 시도는 표로 만들어 보는 것이 가장 규칙이 잘 보이는 방법입니다. 해당 문제는 규칙만 찾는다면 쉽게 풀이할 수 있음으로 STEP을 따라가며 이해해 봅시다.

---

알고리즘 흐름도

입력 받기 -> 데이터 변환하기 -> 재귀 하기 (규칙 찾기) -> 출력하기

---

STEP1 규칙 찾아보기

 이것만 기억하시면 쉽게 찾아볼 수 있습니다. LCS는 규칙을 찾을 때 표로 확인해 보자. 기본적으로 공통된 부분 수열을 찾기 위해서는 2개의 비교대상이 필요합니다. 그렇다면 행/열로 각 아이템들을 나열해서 확인해 볼 수 있죠.

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

자 첫 시작부터 하나씩 따라가 보도록 하죠. 2열의 A부터 가보도록 하죠

 

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

A하나로 중복되는 부분 수열을 수한다면 이와 같이 표현할 수 있죠.

C

CA

CAP

CAPC

CAPCA

CAPCAK

이렇게 부분 수열이 있다면, A 하나가 들어있는 부분 수열의 길이의 최대는 1개가 되죠.

(왜 A가 2개인데 그렇지 않나요? 여기서 저희가 구하는 것은 개수가 아니라 길이의 최대입니다. 

즉, 첫 번째 A이든 두 번째 A이든 길이가 1 임으로 변동이 없는 것입니다.)

 

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

두 번 째는 단지 C가 아니라 {A, C}라고 생각해야 합니다. 그렇다면 이 수열의 부분 수열은 생각해 보면 A, C, {A, C}가 되죠 그러면 이제 차차 확인해봅시다.

C : C가 들어있다. (최대 길이 1)

CA : C나 A가 들어있다. (최대 길이 1)

CAP : C나 A가 들어있다. (최대 길이 1)

CAPC : C, A, {A, C}가 들어있다. (최대 길이 2)

CAPCA : C, A, {A, C}가 들어있다. (최대 길이 2)

CAPCAK :  C, A, {A, C}가 들어있다. (최대 길이 2)

이런 식으로 사고해야 한다. 이때 {A, C}의 경우 순서도 고려해 줘야 합니다. 애초에 문제가 순서를 바꾸면 안 되기 때문이죠. 따라서 {C, A}는 해당 수열의 부분 수열이 아니게 되죠

	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 그렇지 않을 경우 열-1의 값과 행 -1 값 중 높은 값을 가져오죠

 

그런데!! 여기서 한 가지 또 함정이 있습니다. 같은 문자가 있을 경우 어떤 수를 +1 해야 하냐는 말입니다. 이를 위해서는 간략한 생각을 하나 해야 합니다.

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

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

 

즉, 모든 수열에 A가 추가된 상황이 된 것이죠. 그 의미는 즉 대각선에 있는 값에 +1을 해줘야 한다는 의미입니다. 행과 또는 열에서만 +1을 할 경우 입력 예제와는 다른 값들이 들어오게 된다면, 오류가 나기 때문이죠

 

이런 규칙을 기억하시고 다음 STEP으로 넘어가 보도록 하죠

---

STEP2 재귀 구현하기

 규칙을 이해하셨다면 굉장히 쉽습니다.

public static int lcs(int a, int b) {
		
		if(a<0||b<0)
			return 0;
		
		if(dp[a][b]==null) {
			dp[a][b]=0;
			if(str1[a] == str2[b])
				dp[a][b] = lcs(a-1, b-1)+1;
			else
				dp[a][b] = Math.max(lcs(a-1,b), lcs(a,b-1));
		}
		
		return dp[a][b];
	}

if(a <0||b <0)

해당 조건문은 A, B과 음의 값이라면 0을 반환해 줍니다. 이런 조건을 넣어준 이유는 바로 제가 구현한 방식이 TOP-DOWN 방식이기 때문입니다. 해당 조건이 없다면 끝없이 A, B가 내려가기 때문에 인덱스 오류가 나게 되죠.

 

if(dp [a][b]==null)

해당 조건문은 누구나 쉽게 알 수 있는 메모 이제이 션 기법을 사용하기 위한 조건문입니다. NULL값이라면 재귀를 실행하라는 의미입니다.

 

dp [a][b]=0;

기본적으로 0으로 초기화를 해줍니다. (밖에서 초기화하지 않은 이유는 메모 이제이 션 NULL을 이용하기 위해서)

맨 처음 C와 A와 같은 상황을 조정해주기 위해서죠

 

if(str1 [a] == str2 [b])

dp [a][b] = lcs(a-1, b-1)+1;

else

dp [a][b] = Math.max(lcs(a-1, b), lcs(a, b-1));

 

이문제의 핵심이죠 간단해요 각 문자열이 같다면  왼쪽 대각선 위에서 1을 더합니다. 아니라면 행-1 / 열 -1 중에서 높은 값을 넣어줍니다. 이런 식으로 최상위에서 최하위로 가면서 재귀를 돌며 값을 도출합니다.

 

그 후

System.out.println(lcs(str1.length-1, str2.length-1));

이런 식으로 호출해 준다면 끝~!

---

 * 여담으로 toCharArray()는 string을 char []로 변환해주는 메서드입니다.