9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
9251번 : LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

생각해 볼 점
LCS는 매우 유명한 문제입니다.
최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)
최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전
최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에
ko.wikipedia.org
위의 내용을 참고하여 풀었습니다.
코드
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string A, B;
cin >> A;
cin >> B;
int len_A = A.length();
int len_B = B.length();
int **dp = new int*[len_A + 1]; //동적 프로그래밍
dp[0] = new int[len_B + 1];
fill_n(dp[0], len_B, 0);
for(int i = 1; i < len_A + 1; i++)
{
dp[i] = new int[len_B + 1];
fill_n(dp[i], len_B + 1, 0);
for(int j = 1; j < len_B + 1; j++)
{
if(A[i - 1] == B[j - 1]) //더 긴 수열 발견 시 + 1
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
cout << dp[len_A][len_B];
for(int i = 0; i < len_A + 1; i++) delete[] dp[i];
delete[] dp;
return 0;
}
그 외
'공부 및 정리 > 백준 코드' 카테고리의 다른 글
[C++]백준 - 1912번 문제 (0) | 2021.08.05 |
---|---|
[C++]백준 - 11049번 문제 (0) | 2021.08.01 |
[C++]백준 - 7569번 문제 (0) | 2021.08.01 |
[C++]백준 - 1929번 문제 (0) | 2021.08.01 |
[C++]백준 - 7576번 문제 (0) | 2021.08.01 |