목록9251 (1)

코딩성장스토리

백준 9251번 :LCS

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍으로 푸는 것이다. 라고 생각해서 접근했지만 후...모르겠어서 다른 글을 참고했다.. 풀이는 말그대로 다이나믹 프로그래밍으로 푸는 것이다 두 문자열 ACAYKP CAPCAK 가 있다고 하였을 때, 맨 처음 부분 문자열 A,AC,ACA... 와 C,CA,CAP.. 로 비교해가면서 푸는 것이다. 즉 부분 집합에서 최적해를 찾아가..
백준 코딩 2022. 7. 3. 19:05
이전 Prev 1 Next 다음