- 문제 링크
백준 9251번 - LCS
해결 전략
백준 9251번 LCS 문제는 Dynamic Programming적 시선을 키우기 아주 좋은 문제 중 하나이다. 과거 학부 알고리즘 수업에서 다룬 바 있는 Edit Distance 문제와 아주 유사한 접근 방식을 취하고 있다. DP 문제의 해결은 항상 다음과 같은 시선으로 출발해야한다.
문제 상황을 가장 적합하고 명확하게 나타낼 수 있는 점화식이 무엇일까?
본 문제는 위와 같은 시각으로 시작하면 상당히 어렵지 않게 해결할 수 있다. 다만, 두 문자열을 동시에 고려한다는 점이 변수인데, 이를 2차원 배열로 처리해보자. (DP와 관련된 대표적인 센스이다)
LCS[i][j] : 문자열 a의 a[i]까지의 부분과 문자열 b의 b[j]까지의 부분의 LCS의 길이
라고 수식을 작성할 수 있다.
이 상황에서 LCS[i][j]는 점화 관점에서 어떻게 표현할 수 있을까? 바로 아래와 같다.
LCS[i][j] = max(LCS[i][j - 1], LCS[i - 1][j], LCS[i - 1][j - 1] + (a[i] == b[j]))
LCS[i][j]는...
1. a[i] != b[j]인 경우, LCS[i - 1][j], LCS[i][j - 1], LCS[i - 1][j - 1] 중 최대인 값을 취할 것이다.
2. a[i] == b[j]인 경우, LCS[i - 1][j], LCS[i][j - 1], LCS[i - 1][j - 1] + 1 중 최대인 값을 취할 것이다.
위와 같은 사고를 통해 2차원 중첩 반복문으로 간단하게 문제를 해결할 수 있다. 본인은 최초에 Edit Distance 센스를 생각치 못하고 일일이 복잡한 수식을 만들어가며 도전했는데, 꼭 한 두 경우의 예외를 통과하지 못했다. DP는 점화식이 결코 복잡하지 않다는 믿음을 가지고 항상 간단한 수식을 떠올리려고 노력하자.
아래는 코드이다.
#include <iostream>
#include <algorithm>
// BOJ - 9251 LCS
using namespace std;
char a[1002], b[1002];
int LCS[1001][1001];
int solve(void) {
int i, j;
for (i = 1; a[i]; i++) {
for (j = 1; b[j]; j++)
LCS[i][j] = max({ LCS[i][j - 1], LCS[i - 1][j],
LCS[i - 1][j - 1] + (a[i] == b[j]) });
}
return LCS[i - 1][j - 1];
}
int main(void) {
cin >> a + 1 >> b + 1;
cout << solve();
return 0;
}(LCS의 디폴트 초기화값이 0이므로 i = 1, j = 1부터 시작하는 반복문에 적합하게(첫 번째 문자부터) 문자열을 다루기 위해 a + 1, b + 1의 주소로 문자열을 입력하고 있음에 주목하자.)
(또한, 문자열 선형 순회에서 for문의 제한 조건을 문자열의 NULL로 두는 센스도 주목하자.)
