• 박인서

# 3. 코드 ¶

## 3.1. 15이원준 ¶

```#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
char f[1010] = {0,}, s[1010] = {0,},ans[1010] = {0,};
int len[1010][1010] = { 0, };

int main(){
cin>> f >> s;
int x, y;
x = strlen(f);
y = strlen(s);
for(int i = 1; i<=x; i++){
for(int j = 1; j<=y; j++){
if(f[i-1] == s[j-1]){
len[i][j] = len[i-1][j-1] + 1;
}
else{
len[i][j] = max(len[i-1][j], len[i][j-1]);
}
}
}
int num = len[x][y];
cout<<num<<endl;
ans[num] = '\0';
num--;
int i = x, j = y;
while (i >= 1 && j >= 1 && num >= 0) {
if (f[i-1] == s[j - 1]) {
//cout<< ">";
//cout<< i << " " << j << endl;
ans[num] = f[i - 1];
num--;
i--;
j--;
}
else {
//cout<< i << " " << j << endl;
if (len[i - 1][j] >= len[i][j - 1]) {
i--;
}
else {
j--;
}
}

}
cout << ans << endl;
}
```

## 3.2. 박인서 ¶

```#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

int lcs[1001][1001] = { 0, };
char len1[1001] = { 0, }, len2[1001] = { 0, };

int main()
{
//입력
std::cin >> len1 >> len2;

//lcs 탐색
int n = strlen(len1), m = strlen(len2);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (len1[i - 1] == len2[j - 1])
lcs[i][j] = lcs[i - 1][j - 1] + 1;
else
lcs[i][j] = std::max(lcs[i][j - 1], lcs[i - 1][j]);
}
}

//lcs 길이 출력
std::cout << lcs[n][m] << std::endl;
std::vector<char> res;
int x = n - 1, y = m - 1;

//경로 되추적
while (x >= 0 && y >= 0)
{
if (len1[x] == len2[y]) {
res.push_back(len1[x]);
x--, y--;
}
else lcs[x + 1][y] >= lcs[x][y + 1] ? y-- : x--;
}

//lcs 출력
std::reverse(res.begin(), res.end());
for (int i = 0; i < res.size(); i++) std::cout << res[i];

return 0;
}
```