DP를 활용하는 대표적인 문제로 LCS(Longest Common Sequence)가 있습니다.시간복잡도 $O(N^{2})$, 공간복잡도 $O(N^{2})$로 해결하는 풀이가 가장 일반적입니다. 그렇다면 다음 문제를 봅시다.https://www.acmicpc.net/problem/18438 18438번: LCS 5LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.www.acmicpc.net문자열의 길이가 7000 이하이니 시간 복잡도는 문제될 게 없습니다만,공간 복잡도가 비정상적으로 줄어버리며 난이도가 확 올라갔습니..
