백준 #9251. LCS

백준 #9251. LCS

(정리에 앞서 .. 제가 문제를 풀 때 참고한 Velog 포스트가 있습니다. 'emplam27' 님께서 작성하신 포스트에 LCS에 관련된 설명히 매우 친절하게 자세히 적혀 있어서 저 이외에 이 문제를 푸시는 다른 분들도 해당 글을 참고하시면 좋을 것 같아 아래에 링크를 남깁니다.)

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

정리

최장 공통 부분 수열을 구할 때는, 2차원 배열을 만들어 두고, 2중 for문으로 첫 번째 문자열과 두 번째 문자열의 값을 하나씩 비교하면서 배열에 저장해 나가는 방식으로 답을 구하면 된다.
2차원 배열에 기존의 답(최장 공통 부분 수열의 길이)를 저장해 두고 다음 단계의 답을 구할 때 활용한다는 점에서 이 또한 동적 계획법의 예시라고 할 수 있다.

첫 번째 문자열에서 i번째 문자까지, 두 번째 문자열에서 j번째 문자까지 고려할 때, LCS의 길이를 구하기 위한 점화식은 아래와 같다.

if (i == 0 || j == 0) LCS[i][j] = 0;
else if (str1[i] == str2[j]) LCS[i][j] = LCS[i-1][j-1] + 1;
else LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);

• 어느 쪽이라도 길이가 0인 문자열이 있으면, LCS는 존재할 수 없으므로 default 값인 0을 넣어주면 된다.

• 만약 str1[i]와 str2[j]가 같은 문자라면, LCS의 길이는 기존의 문자열 (str1은 i-1번째 문자열까지, str2는 j-1번째 문자열까지)의 LCS의 길이에 1을 더해주면 된다.

• 만약 str1[i]와 str2[j]가 같지 않다면, LCS에 새로운 문자가 추가될 여지가 없다. 따라서, LCS의 길이는 기존의 값을 그대로 이어받게 된다.
  여기서 ‘기존의 값'은 다음의 두 가지 case 중 더 큰 값을 말한다.

  • str1의 길이가 1 짧고 (i - 1), str2의 길이는 그대로인 (j) 경우
  • str1의 길이는 그대로이고 (i), str2의 길이가 1 짧은 (j - 1) 경우

정답 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(void) {
    string str1;
    string str2;
    int LCS[1001][1001];
    
    cin>>str1;
    cin>>str2;
    str1 = " " + str1;
    str2 = " " + str2;
    
    for(int i=0; i<str1.size(); i++) {
        for(int j=0; j<str2.size(); j++) {
            if (i == 0 || j == 0) LCS[i][j] = 0;
            else if (str1[i] == str2[j]) LCS[i][j] = LCS[i-1][j-1] + 1;
            else LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
        }
    }
    
    
    cout<<LCS[str1.size()-1][str2.size()-1]<<endl;
    return 0;
}