LIS, LCS C++코드

 

 

LIS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int LIS(const vector<int>& arr) {
    if (arr.empty()) return 0;

    vector<int> lis;
    
    for (int i = 0; i < arr.size(); ++i) {
        auto it = lower_bound(lis.begin(), lis.end(), arr[i]);
        if (it == lis.end()) {
            lis.push_back(arr[i]);
        } else {
            *it = arr[i];
        }
    }

    return lis.size();
}

int main() {
    vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    cout << "LIS의 길이: " << LIS(arr) << endl;
    return 0;
}

 

 

LCS

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int LCS(const string& X, const string& Y) {
    int m = X.size();
    int k = Y.size();
    vector<vector<int>> lcs(m + 1, vector<int>(k + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
            } else {
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
            }
        }
    }

    return lcs[m][k];
}

int main() {
    string X = "ABCBDAB";
    string Y = "BDCAB";
    cout << "LCS의 길이: " << LCS(X, Y) << endl;
    return 0;
}