BOJ 9252. LCS 2
랭크 : 골드4
문제 풀이
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제로 https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence 에 설명이 잘 되어 있습니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int board[1002][1002];
char str1[1002];
char str2[1002];
int main() {
fastio;
cin >> (str1 + 1) >> (str2 + 1);
for (int i=1; i < 1002; i++) {
if (str1[i] == 0) {
i = 1001; continue;
}
for (int j=1; j < 1002; j++) {
if (str1[i] == str2[j]) {
board[i][j] = board[i - 1][j - 1] + 1;
} else {
board[i][j] = max(board[i-1][j], board[i][j-1]);
}
}
}
std::string answer{};
int x = strlen(str1 + 1);
int y = strlen(str2 + 1);
while (board[x][y] != 0) {
if (str1[x] == str2[y]) {
answer += str1[x]; x--; y--;
} else {
if (board[x-1][y] == board[x][y]) x--;
else y--;
}
}
cout << answer.size() << endl;
if (answer.size()) {
reverse(answer.begin(), answer.end());
cout << answer << endl;
}
}알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| LCS | $O(N^2)$ | $O(N^2)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 10942. 펠린드롬? (0) | 2022.07.11 |
|---|---|
| BOJ 2239. 스도쿠 (0) | 2022.07.11 |
| BOJ 12015. 가장 긴 증가하는 부분 수열 2 (0) | 2022.07.10 |
| BOJ 12852. 1로 만들기 2 (0) | 2022.07.10 |
| BOJ 2166. 다각형의 면적 (0) | 2022.07.10 |