문제 링크 : https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
풀이
가장 대표적이고 기본적인 LCS 길이 찾기 문제이다.
LCS 길이 찾기 방법 : https://suhwanc.tistory.com/80
LCS 알고리즘
1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence)이란 어떤 단어에서 연속되지 않는 부분 문자열을 뜻하는데..
suhwanc.tistory.com
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <iostream>
#include <algorithm>
using namespace std;
int d[1001][1001];
int main()
{
string a, b;
string ak, bk;
a = " "; b = " ";
cin >> ak >> bk;
a += ak; b += bk;
int na = a.size();
int nb = b.size();
for (int i = 1; i < na; i++) {
for (int j = 1; j < nb; j++) {
if (a[i] == b[j]) {
d[i][j] = d[i - 1][j - 1] + 1;
}
else {
d[i][j] = max(d[i - 1][j], d[i][j - 1]);
}
}
}
printf("%d\n", d[na - 1][nb - 1]);
return 0;
}
|
cs |
개발환경 : Visual Studio 2019
지적, 조언 언제든지 환영입니다~~
'백준 문제풀이' 카테고리의 다른 글
| 백준 9252번 LCS 2 (0) | 2020.02.12 |
|---|---|
| 백준 5582번 공통 부분 문자열 (0) | 2020.02.12 |
| 백준 10422번 괄호 (2) | 2020.02.12 |
| 백준 5557번 1학년 (0) | 2020.02.12 |
| 백준 13975번 파일 합치기 3 (0) | 2020.02.12 |