dp를 열심히 해야겠다는 어제의 교훈에서 영감을 받아 오늘은 전부터 풀려고 열심히 꿍쳐놨던 기초 dp 문제 LCS(Longest Common Subsequence)를 풀었다…
조금만 생각하면 사실 LIS랑 거의 같은 문제이긴 한데 나는 아직 그걸 한 번에 깨우칠 정도로 dp를 제대로 이해하고 있지는 못해서 이 링크의 풀이를 참조했다. 링크
이게 LIS랑 왜 똑같냐면… 얘도 사실상 문자열을 구간구간으로 나눈 뒤 각 구간에서 겹치는 문자열이 몇 개 있는지를 저장한 뒤에, 그걸 한 문자씩 늘리고 늘리는데 이 때 부분 문자열의 공통 문자열 개수를 이용하기 때문
그래서 탐색하는 과정은 각 문자열의 인덱스에 해당하는 2차원 벡터를 하나 할당한 다음에, 한 문자열을 기준으로 해서 한 칸 씩 쭉쭉 늘려가면서 개수를 게속 세주면 됨.
예를 들어서 백준 문제 예시에서 주어진 문자열은 ACAYKP, CAPCAK이다.
그럼 앞 문자열을 기준으로 잡는다고 치면, A일 때 C, CA, CAP, … CAPCAK일 때 공통 문자열이 몇 개가 나오는지를 계산을 하고
여기다가 그 다음은 AC를 가지고 또 같은 계산을 쭉죽 해주는 거다.
이 때 우리는 두 문자열에서 맨 뒤 문자만을 비교할 건데 (당연함. 앞 문자열은 이미 전 subsequence에서 확인 완료함)
그러면 두 문자가 같은 경우가 존재할 수가 있고 다른 경우가 존재할 수가 있다.
그러면 만약 같다고 쳤으면, 공통 문자의 개수는? 두 문자열 다 한 개 전 문자열의 개수에서 +1한 게 된다.
예를 들어서 AC랑 CAPC가 겹치는 개수를 보고 싶으면, 이 바로 전의 탐색은 A랑 CAP의 탐색이었겠지? 그러니까 여기에 +1을 한 게 해당 케이스의 공통 문자열 개수가 됨.
만약 다르면, 그러면 그냥 첫번째든 두번째든 한 인덱스 작은 케이스에서 더 큰 값을 가져오면 된다. (여기서 큰 값을 가져와야만 해당 케이스에서 항상 큰 값을 계속 사용할 수 있게 되어서, LONGEST라는 조건이 충족이 된다.)
이 때 첫 번째 문자열에서 끌고온 거면 이번 탐색의 결과에서 큰 값이 갱신이 돼서 그걸 쓴다는 거고, 반대는 옛날에 더 큰 값으로 갱신된 게 있어서 그걸 쓴다는 의미이다. (조금 생각해보면 이해 가능)
이걸 그림으로 그린 게 아래의 사진이다. 화살표가 가르키는 원소가 화살표가 뻗어 나오는 원소의 영향을 받았음을 의미한다.
아무튼 그렇다… 부분부분으로 문제를 잘게 쪼갠 다음에 그 문제를 하나하나씩 차곡차곡 쌓아올려서 해결하는 것으로 전체 문제를 해결한다는 dp의 정의와 완전히 일치하는 아주 기본적이고 좋은 문제이다.
아직도 문제를 부분 문제로 쪼개는 게 잘 안 되는 거 같다… 더 문제 풀면서 노력해야겠다.
코드는 다음과 같다.
//LCS - 골드 5
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> len;
string s1, s2;
void solve() {
for (int i = 1; i <= s1.size(); i++) {
for (int j = 1; j <= s2.size(); j++) {
if (s1[i-1] == s2[j-1]) {
len[i][j] = len[i-1][j-1] + 1;
} else len[i][j] = max(len[i-1][j], len[i][j-1]);
}
}
}
int main() {
cin >> s1 >> s2;
len.assign(s1.size()+1, vector<int> (s2.size()+1, 0));
solve();
cout << len[s1.size()][s2.size()];
}