백준 9251번
문제 해설이 아닌 풀이하며 거쳐간 생각들을 기록해둔 글입니다.
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
접근 과정
- 재귀를 통해 n개의 문자 중 m개를 고르는 부분 수열 문제는 백준 사이트에서 알고리즘 문제를 많이 숙달된 상태였다. 본 문제에선 두 문자열의 부분수열을 구하고 이 둘이 같은 수열인지 비교하여 해결할 수도 있으나 문자열이 최대 1000자나 되기에 두 문자열의 모든 부분수열을 비교하기엔 너무 많은 연산이 있을 것 같았다.
- 수열을 구하는 연산은 한 문자열에 대해서만 수행하고 새로운 문자를 추가할 떄 다른 문자열의 수열로 포함되는지 여부만 판단하는 식으로 최적화를 해주기로 하였다. 결과적으로 가장 긴 부분 수열의 길이를 구하는 함수가 완성되었다.
문제는 시간초과!! - 이유는 수열을 구하는 방법 자체에 여전히 중복된 연산이 많이 때문이다. 완전탐색으로 구현할 수 있고 중복된 연산이 많은 경우… 아 DP 문제이다. 함수 매개변수 중 캐시배열 인덱스로 사용할 수 있는 것들을 골라 메모이제이션을 적용하였다. 최적화의 결과는 아래와 같다. 문자열의 길이가 1000자까지 간다면 줄어드는 연산의 수가 훨씬 많을 것이다.
입력
SMALLYJELLY LLYJMYSMA
출력 (최적화 전 / 후)
S S SM SM SMA SMA SA SA M M MA MA MY MY MY MY A A L L LL LL LLY LLY LLYJ LLYJ LLYJY LLYJY LLYY LLYY LLJ LLJ LLJY LLY LLY LY LY LJ LYJ LL LYJY LL LYY L LJ Y LJY J LL L LLY L LL Y LLY LY L LY LYJ LYJY LYY LJ LJY LL LLY LL LLY LY Y YJ YJY YY J JY L LL LLY LY L LY Y
소스 코드
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
string strA;
string strB;
string commonSubsequence;
int cache[1000][1000];
int makeSubSeq(unsigned int cursorA, unsigned int cursorB) {
if (cursorB == strB.length() || cursorA == strA.length()) {
return 0;
}
int& ret = cache[cursorA][cursorB];
if (ret != -1) {
return ret;
}
// A문자열에서 확인하지 않은 문자 중 cursorB 위치의 문자와 동일한 문자가 있는지 확인
unsigned int nextCursorA;
for (nextCursorA = cursorA; nextCursorA < strA.length(); ++nextCursorA) {
if (strB[cursorB] == strA[nextCursorA]) {
// 동일한 문자가 있다면 공통 부분 수열을 만들 수 있음
ret = makeSubSeq(nextCursorA + 1, cursorB + 1) + 1;
break;
}
}
// cursorB를 이동시킨 후 탐색
ret = max(ret, makeSubSeq(cursorA, cursorB + 1));
return ret;
}
int main() {
memset(cache, -1, sizeof(cache));
cin >> strA;
cin >> strB;
cout << makeSubSeq(0, 0);
return 0;
}