Doby's Lab

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 저번에 공부했던 LCS알고리즘을 이해하고 있다면 똑같은 DP의 방식으로 문자열 배열 DP를 돌리면 된다. (LCS 정리 https://draw-code-boy.tistory.com/126) [AC 코드] cache2 == 문자열 메모이제이션 배열 #include #include #include #include #define MAX 1000 + 1 #..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 우선, 글에 들어가기 앞서 포스팅의 제목에서 '수열'이라고 강조한 이유는 '문자열'과 '수열'은 다른 의미이기 때문이다. 저번에 LIS를 포스팅하면서는 수열과 집합의 차이를 느꼈는데 이번 키워드에서는 문자열과 수열의 차이를 알아야 한다. (집합에 관해 적은 포스팅: https://draw-code-boy.tistory.com/85) [문자열 vs 수열]..