PS
백준 9252. LCS 2
tose33
2023. 8. 14. 16:42
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
https://tose33.tistory.com/111
백준 9251. LCS
www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAP
tose33.tistory.com
위의 LCS 만드는 문제는 길이만 구하면 됐지만 이번에는 실제 수열도 구해야한다.
실제 수열을 구할때는 역추적하면 된다.
d[i][j] == d[i-1][j] 일때는 i-1,j 로,
d[i][j] == d[i][j-1] 일때는 i,j-1 로,
else : 이때 해당 문자가 LCS 의 원소다. i-1,j-1 로