[백준] 9251번 LCS 자바

문제 (골드5 / dp)

 

9251번: LCS

 

 

문제 풀이

 

사실 LCS는 유명한 문제이기에, 얕보고 백준 LCS3문제를 풀다가 너무 어려워서 LCS 먼저 풀면서 개념을 다지기 위해 LCS를 풀었다.

근데 알고보니 내가 알던 LCS 뜻과 약간의 혼동이 있었다.

 

LCS(Longest Common Subsequence): 최장 공통 부분 수열

 - 부분 수열이므로 공통된 문자들이 연결되어 있지 않아도 된다.

 - ex) ABCDEF, GBCDFE -> BCDF

 

 

LCS(Longest Common Substring) : 최장 공통 문자열

 - 부분 문자열이 아니므로 한 번에 이어져 있는 문자열만 가능하다.

 - ex) ABCDEF, GBCDFE -> BCD

 

나는 LCS가 substring을 말하는 줄 알았는데 주로 subsequence를 말한다고 한다.

 

 

LCS를 구현하는 가장 간단한 방법은 문자열X, 문자열Y이 있을 때 

문자열X의 모든 subsequence에 대해 그것이 y의 subsequence가 되는지 검사한 후 가장 큰 값을 반환하는 것이다.

그렇지만 이 경우 X문자열이 길어질 경우 시간복잡도가 엄청 커지게 된다. 

시간복잡도를 줄이기 위해 조금 더 논리적인 방법을 사용해야 한다.

 

 

- 재귀를 이용한 구현과정

 

문자열X와 문자열Y의 LCS를 Z라고 하자.

그러면 Z의 가장 마지막 문자를 X,Y가 포함하고 있다면  X,Y의 포함한 문자 이후의 문자열은 확인하지 않아도 된다.

왜냐, 이미 LCS를 가정해둔 상태에서 LCS의 마지막 문자가 나왔기 때문에 그 이후는 해당되지 않는 것이기 때문이다.

 

 

그래서 뒤에서부터 서로의 문자열을 비교하며 같은 경우 +1 증가하며 재귀를 호출하고, 같지않다면 X,Y의 문자를 하나씩 줄여가며 큰 경우의(더 많이 누적된=같은 문자가 많은) LCS를 반환한다.

 

1) 같은경우: Xi = Yi 

 

LCS(i, j) = LCS(i-1, j-1) + 1

 

 

2) 다른 경우:  Xi != Yi 

 

LCS(i, j) = Math.max( LCS(i-1, j), LCS(i, j-1) )

 

 

//의사코드
int LCS(char *X, char *Y, m, n)
{
	if(m=0 or n = 0)
    		return 0;
 	else if(X[m-1] = y[n-1])
    		return LCS(X, Y, m-1, n-1) + 1;
    	else
    		return max(LCS(X, Y, m-1, n), LCS(X, Y, m, n-1))
}

 

=> 하지만 이렇게 구현하면 엄청난 중복 호출이 발생하므로 DP를 이용하여 푸는 것이 좋다!

 

 

 

- DP를 이용한 구현과정

 

누적합을 저장할 배열 메모리를 따로 선언한다.

백준 문제에 나온 값을 예시로 풀어보겠다.

 

A = "ACAYKP"

B = "CAPCAK"

 

1) int[][] dp 배열 준비

   문자열 B를 기준으로 비교하며 세로방향으로 dp를 채워나갈 것.

   (어느 문자열을 기준으로 비교해 나갈 것인지에 따라 행/열의 채우는 순서가 달라짐)

 

2) "A"와 "C" 같은지 비교

 

3) "A"와 "CA" 중 공통 부분문자열 있는지 확인 : A와 A

 

4) "A"와 "CAP" 비교 : 그 전의 A만 공통이므로 1 저장

 

5) 이렇게 쭉 채워나가면 1열 완료

 

6) "AC" 와 "C" 비교

 

7) 이렇게 또 "AC" 와 B문자열의 부분수열들을 비교하며 최대 누적값을 구해나감

 

8) 그 다음은 "ACA" 와 "C" , "CA", ... 이런식으로 쭉 비교하며 나감

 

9) 채우다 보면 규칙을 알 수 있음

   : 현재 비교하는 문자열의 마지막 문자가 같으면 (현재 i, j값이 같으면) ->현재 칸의 대각선의 수를 가져온 다음 +1을 해준다. 대각선의 수를 가져오는 이유는 현재 문자를 포함하지 않는 문자열 중에서 가장 큰 누적합이기 때문.

문자가 다를 경우 -> 왼쪽/위쪽 중 큰 수를 가져온다. 이 경우는 어차피 현재 비교하는 문자가 다르기 때문에 여태까지 누적된 합 중 큰 값을 가져오기 되면 되기 때문에 위/왼쪽 중에서 가져옴.

 

 

 

소스 코드

 

public class b_LCS {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String A = sc.next();
		String B = sc.next();
		
		// 처음 행렬의 왼쪽, 위쪽의 값을 가져오는 값을 지정해주기 위해
		int[][] dp = new int[A.length() + 1][B.length() + 1];
		
		// 0으로 패딩 (A:세로/ B:가로)
		for(int i = 0; i <= A.length(); i++)
			dp[i][0] = 0;
		for(int i = 0; i <= B.length(); i++)
			dp[0][i] = 0;
		
		// dp완성
		for(int i = 1; i <= A.length(); i++) {
			for(int j = 1; j <= B.length(); j++) {
				if(A.charAt(i-1) == B.charAt(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.println(dp[A.length()][B.length()]);
		sc.close();
		return;
	}
}