백준_9251_LCS[C++]

[문제링크]

문제 접근

Dyanamic Programming으로 접근하였다.

참고한 슈도 코드는 다음과 같다.

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

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

나는 각 인덱스가 의미하는 것을 파악하려고 노력했다. 즉, i와 j가 각각 의미하는 것은 뭘까? 예를 들어 입력으로 BDCAB와 ABCBDAB이 입력으로 들어왔다고 하자. 초기 테이블의 값은 다음과 같다.

	””	B	D	C	A	B
””	0	0	0	0	0	0
A	0
B	0
C	0
B	0
D	0
A	0
B	0

i=0 && j=0일때, 즉, 최초에 비교를 진행할때 의미하는 것은 B와 A의 LCS를 구하는 것이다. 두 문자는 일치하는 문자 없으므로 0이 된다.

	””	B	D	C	A	B
””	0	0	0	0	0	0
A	0	0
B	0
C	0
B	0
D	0
A	0
B	0

여기까지만 봐서는 이해가 안된다. 좀 더 봐보자

string1[i] != string2[j] 인 경우

i = 3 && j = 3 일때는 어떨까? 즉 테이블은 다음과 같다.

	””	B	D	C	A	B
””	0	0	0	0	0	0
A	0	0	0	0	1	1
B	0	1	1	1	1	2
C	0	1	1	2	2	2
B	0	1	1	2	?
D	0
A	0
B	0

? 인 부분을 계산하고자 한다. 즉 BDCA와 ABCB의 LCS를 구하고자 한다. 지금 A와 B는 일치하지 않는다. 그렇기에 BDC와 ABC의 LCS에수 중 긴 것을 선택하면 된다. 주목해야 할 것은 i와 j에 값에 따라서 비교하는 substring이 결정된다.

i=3 && j=3 일때,

1. BDCA와 ABCB의 LCS = table[i][j]
2. BDC의 LCS = table[i-1][j]
3. ABC의 LCS= table[i][j-1]

따라서 table[i][j] = max(table[i-1][j],table[i][j-1])가 된다. 예시의 경우에는 2가 된다.

string1[i] == string2[j]인 경우

위에서 계산한 case는 현재 비교하고자 하는 두개의 문자가 일치하지 않을 경우다. 일치한다면 어떻게 될까?

i=3 && j=4일때를 생각해보자. 테이블은 다음과 같다.

	””	B	D	C	A	B
””	0	0	0	0	0	0
A	0	0	0	0	1	1
B	0	1	1	1	1	2
C	0	1	1	2	2	2
B	0	1	1	2	2	?
D	0
A	0
B	0

?가 현재 구하고자 하는 것이다. 현재 BDCAB의 마지막 B와 ABCB의 마지막 B가 일치한다. 이런 경우는 BDCA와 ABC의 LCS 값에서 +1한 값을 저장하면 된다.

i=3 && j=4 인 경우

1. BDCA와 ABC의 LCS = table[i-1][j-1]
2. BDCAB 와 ABCB의 LCS = 위의 식 +1

코드

#include<iostream>
#include<vector>

using namespace std;

int lcs(string str1, string str2) {
    //0으로 초기화
    vector<vector<int>> dict(str1.size() + 1, vector<int>(str2.size() + 1, 0));
    //정답 
    int ans = 0;
    for (int i = 1; i < dict.size(); i++) {
        for (int j = 1; j < dict[i].size(); j++) {
            if (str1[i - 1] == str2[j - 1]) { //일치하는 경우
                dict[i][j] = dict[i - 1][j - 1] + 1;
            } else {//일치하지 않는 경우
                dict[i][j] = max(dict[i - 1][j], dict[i][j - 1]);
            }
            ans = max(dict[i][j], ans);
        }
    }
    return ans;
}

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    cout << lcs(str1, str2) << "\n";
    return 0;
}

후기

나는 특히 DP약한 것같다. 아이디어가 뽑아내는 것이 어렵다.