[백준] 9251번 - LCS (DP) - 결과 포함
www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제 역시 혼자 풀지 못하고 다른 분들의 글을 참고했다. 다이나믹 프로그래밍 문제들은 간단해보이지만 다이나믹 프로그래밍을 이용해야겠다는 생각과 어떤 식으로 해결 방법을 구성할 지가 답을 보고도 쉽게 이해되지 않는다. 두 문자열을 비교해서 같은 부분 문자열의 최대 길이를 찾는 문제이다. 이전에 풀었던 증가하는 부분 수열 문제와 비슷하다고 생각해서 문자 하나씩 확인하..
개발 공부 (알고리즘)
2021. 4. 15. 03:45
