1. DP 알고리즘
2. 공통 부분 문자열 중 가장 길이가 긴 문자열
[예] ABCDEF 와 ACDGHI 와의 공통 Subsequence 중 가장 길이가 긴 것은
ABCDEF / AZGCDGHI 에서 ACD 이다.
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
https://www.acmicpc.net/problem/1958
1958번: LCS 3
첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.
www.acmicpc.net
https://www.acmicpc.net/problem/13711
13711번: LCS 4
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3]
www.acmicpc.net
'자료구조 + 알고리즘' 카테고리의 다른 글
| 해시(Hash) (0) | 2021.09.14 |
|---|---|
| 위상정렬 (Topological Sorting) (0) | 2021.09.14 |
| LIS (Longest Increasing Subsequence, 최장 증가 부분수열) (0) | 2021.09.14 |
| LCA (Lowest Common Ancestor, 최소공통조상) (0) | 2021.09.14 |
| 문자열 매칭 알고리즘 (0) | 2021.09.14 |