[BOJ/C++] 백준 9251번: LCS

 

🔗 문제 링크 : https://www.acmicpc.net/problem/9251

 

---

 

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

 

 

 

 

입출력 예시

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

 

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

 

 

입출력 예시

 

 

 

---

 

풀이 

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 알고리즘을 공부하고 첫 번째로 풀기 좋은 문제다!

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    string S0, S1;
    cin >> S0 >> S1;
    
    /* S0 x S1 크기의 이차원 dp 배열 선언 */
    vector<vector<int>> dp(S0.size() + 1, vector<int>(S1.size() + 1, 0));
    for (int i = 1; i <= S0.size(); i++) {
        for (int j = 1; j <= S1.size(); j++) {
            if (S0[i-1] == S1[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }
    cout << dp[S0.size()][S1.size()] << endl;
}

 

dp 배열의 최종 상태는 이렇다.

0 0 0 0 0 0 0
0 0 1 1 1 1 1
0 1 1 1 2 2 2
0 1 2 2 2 3 3
0 1 2 2 2 3 3
0 1 2 2 2 3 4
0 1 2 3 3 3 4

 

 

 

---

 

LCS 알고리즘 알아보기

 

[Algorithm] Longest Common Subsequence(LCS) 알고리즘 : 두 문자열 간 최장 공통 부분 수열 찾기

[Algorithm] Longest Common Subsequence(LCS) 알고리즘 : 두 문자열 간 최장 공통 부분 수열 찾기

 

---