[백준][DP] 9251번 LCS, 9252번 LCS2

문제

두 문자열이 주어질 때 부분 수열 중 가장 긴 부분 수열의 길이를 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/9251)

풀이

처음에 이 문제를 보고 잘 못풀 것 같다는 생각이 들어서 넘겨버렸었는데 다시 풀어보았습니다! 생각보다 쉬운 문제였는데 LCS알고리즘이란 말이 붇어있으니 어려워 보여서 못 풀었던 것 같기도..합니다. 이전에 풀었던 문제는 숫자의 배열이 주어지면 그것을 통해 가장 긴 증가 수열의 길이를 구하는 것이었는데 문자열을 통해서 공통된 부분을 찾는다고 접근하려니 어렵게 느껴졌습니다. 두 문자열을 쪼개어서 차례차례 생각을 하면 풀어나갈 수 있습니다. 만약 두 문자열이 'ABC'와 'ADB'라고 하겠습니다. 문자열을 첫번째문자부터 잘라서 보면 'A'와 'A' 이므로 공통 부분 수열이 1입니다. 그렇다면 한칸씩 늘려갑니다. 'A'와 'AD'를 보면 공통된 부분을 찾을 수 없기 때문에 'A'와 'A'일 때의 값과 같은 1입니다. 한칸씩 늘려가다가 'AB'와 'ADB'가 되면 'AB'라는 공통 부분 수열이 존재하므로 'A'와 'AD'일 때의 값에 +1을 해주어서 2가 됩니다. 이렇게 문자를 쪼개어서 차례대로 보면되는데 표를 그려서 풀며 더 쉽게 이해할 수 있습니다.

	0	A	B	C
0	0	0	0	0
A	0	1	1	1
D	0	1	1	1
B	0	1	2	2

표에서 각 칸은 해당 칸에 위치하는 문자열까지 비교를 할 때에 가장 큰 부분 수열을 의미합니다. 이렇게 되면 최종적으로 표의 가장 오른쪽 아래 값이 정답이 됩니다. 

LCS[i][j] = 첫번째 문자열의 i번째까지, 두번째 문자열의 j번째까지 비교했을 때 가장 큰 부분 수열입니다. 따라서 str1[i] == str2[j] 이 될 경우에는 LCS[i-1][j-1]+1이 되고 같지 않은 경우는 LCS[i-1][j] 또는 LCS[i][j-1] 중 큰 값이 됩니다. i-1, j-1을 사용하게 되므로 LCS 배열은 0이 아닌 1부터 첫번째 문자열칸으로 사용하면 예외처리할 필요 없이 깔끔하게 코드를 짤 수 있습니다.

+ 추가 LCS2

LCS2는 최장 부분 수열의 길이와 해당 문자열을 출력하는 문제입니다. 저는 LCS 배열을 만들어 나갈 때 위쪽에서 오는지 왼쪽에서 오는지 대각선에서 오는지를 parent 배열로 만들어서 해결하긴 했는데 LCS 배열값만으로도 해줄 수 있어서 새로 수정하였습니다. LCS[i][j] == LCS[i-1][j]이라면 왼쪽에서 왔다는 것을 알 수 있고 LCS[i][j-1]과 같다면 위쪽에서 왔다는 것을 알 수 있습니다. 그리고 둘 다 아닌 경우는 대각선에서 왔을 경우입니다. 대각선에서 올 때만 +1이 되므로 대각선이 되는 경우에 부분 수열이 만들어짐을 알 수 있고 이 때의 문자를 vector에 넣어준 다음 최종 결과를 거꾸로 출력해주면 문자열까지 찾아낼 수 있습니다.

코드

9251번 LCS: https://github.com/kswim/Algorithm/blob/master/DP/9251.cpp

9252번 LCS2: https://github.com/kswim/Algorithm/blob/master/DP/9252.cpp