이번 문제는 백준의 골드 5 문제 LCS 문제이다.
사실 이전에 한 번 풀었던 문제이지만, 기억이 안나 다시 푼다.
LCS?
알고리즘에는 꽤 유명한 수열들이 있다.
LIS, LCS, LPS
그 중 하나인 LCS는 동적 계획법에서 굉장히 유명한 수열이다.
Longest Common Subsequence로, 최장 공통 부분 수열을 의미한다.
두 문자열이나 수열에 대해서, 공통되는 가장 긴 부분 수열을 찾는 알고리즘이다.
문제를 한 번 읽어보도록 하자.
문제 분석
최대 1000 글자로 이루어진 두 문자열이 주어진다.
이 때, 두 문자열에 대해 최장 공통 부분 수열을 구하라.
최대 1000 글자이니, 2차원 배열로 Memoization을 해도 될 것 같다.
DP
어떤 방식으로 Memoization을 진행해야 할 지 한 번 생각해보자.
우선 입력받은 두 문자열을 아래와 같이 표로 표현할 수 있을 것 같다.
DP 배열의 행과 열을 각 문자열로 두는 것이다.
이제 어떤 식으로 배열을 채워 나가야 할까?
우선 가장 신경써야 할 점은 연속하지 않는 부분 수열 이 허용된다는 점이다.
예시로 나온 두 문자열에 대해서 LCS는 ACAK가 된다는 말이다.
우선 현재 행, 열 포인터가 가리키는 문자가 서로 같을 때를 생각해보자.
문자가 서로 같다면, 공통 부분 수열에 포함시킬 수 있으니 +1을 해준다.
그럼 표가 우선 아래와 같은 모습이 될 것이다.
그럼 이후로 만날 AYKP 문자들에 대해서는 어떻게 처리가 되어야 할까?
Memoization의 정의가 뭔지 다시 한 번 생각해보자.
“저장된 이전 단계의 결과를 현재 단계의 풀이에 사용하는 것”
즉, 우리는 C와 ACAYKP의 LCS가 C라는 것을 계산한 것이다.
따라서, 해당 행의 끝까지 LCS의 길이인 1로 채워줄 필요가 있다.
그럼 이제 다음 단계는 CA와 ACAYKP의 LCS를 구하는 단계가 된다.
이번 단계의 관건은 LCS인 CA의 길이를 어떻게 갱신해줄 것인가이다.
결과적으로 길이가 2이기 때문에 아래와 같이 표가 갱신될 것이다.
그럼 어떤 규칙에 의해서 해당 셀의 값이 2로 갱신이 될까?
이전 단계 까지의 LCS 길이 에 의해 결정됨을 우리는 이미 알고있다.
또한 C vs AC가 CA vs ACA의 이전 문자열 비교 단계가 된다.
따라서 우리는 dp[i-1][j-1] + 1이라는 점화식을 얻을 수 있게 된다.
마지막으로, 다음 단계로 넘어갔을 때 포인터의 문자가 다르다면 어떻게 갱신할까?
위와 같이 CAP와 A를 비교하는 단계를 한 번 보자.
CAP의 안에 A라는 문자가 존재하니, LCS는 1이 된다.
우리는 이 사실을 이전에 갱신했던 CA vs A 단계에서 참조할 수 있다.
하나의 예시를 더 살펴보자.
CAP와 ACA의 경우는 LCS가 2임을 알 수 있다.
우리는 이 사실을 이전에 갱신했던 CA vs ACA 단계에서 참조할 수 있다.
이는 사실 또 다른 이전 단계인 CAP vs AC의 LCS가 1이기 때문에 나온 결과이다.
즉, 문자가 다를 때 우리는 이전 단계에서 LCS가 더 긴 단계의 값을 가져온다!
dp[i][j] = max(dp[i-1][j], dp[i][j-1])의 점화식을 얻을 수 있는 것이다.
최종적으로 아래와 같이 구현할 수 있다.
string src = "", dest = "";
int dp[1001][1001];
int main() {
cin >> src;
cin >> dest;
for (int i = 1; i <= dest.size(); i++) {
for(int j = 1; j <= src.size(); j++){
if (dest[i - 1] == src[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j - 1]);
}
}
cout << dp[dest.size()][src.size()];
return 0;
}Appendix : 문자열 저장
추가적으로, 문자열의 길이를 넘어서 문자열을 저장하는건 어떨까?
위에서 LCS를 계산할 때 아래와 같이 모든 표가 채워졌다.
해당 표를 살펴보고 이제 우리는 정답인 ACAK를 만들어야 한다.
가장 먼저 직관적으로 문자가 같을 때가 핵심임을 알 수 있다.
예를 들어, C vs AC 즉 dp[1][2]를 보거나,
CA vs A 즉 dp[2][1]을 보면 값이 증가했음을 알 수 있다.
그렇다. 두 포인터의 문자가 같을 때엔, 값이 증가하게 된다.
그럼 값이 증가하는 부분을 모두 저장하면 그게 답이 될까?
아니다. 예를 들어 CA vs ACA, dp[2][3]의 값과 비교해서,
CAPC vs AC, dp[4][2]의 값을 한 번 보도록 하자.
두 경우 모두 1 -> 2로 값이 증가했음을 알 수 있다.
그럼 우리는 두 경우를 구분해서, LCS에 해당하는 문자열을 찾아야 한다.
어떤 기준으로 두 경우를 구분해낼 수 있을까?
배열을 한 번 가장 뒤에서 부터 훑어보면 어떨까?
가장 긴 LCS 배열의 길이가 가장 마지막 칸에 있으니,
뒤에서 부터 DP 배열을 훑어보는 것은 합리적이라고 생각된다.