최장 공통 부분 수열이란?최장 공통 부분 수열이란 두 수열이 주어졌을 때, 둘 모두의 부분 수열이 되는 수열 중 가장 긴 것을 의미한다. 예를 들어,MANGOJUICEAGODATRIP위 두 문자열의 LCS는 AGOI이다. LCS 길이 구하기LCS는 DP를 이용해 구할 수 있다.두 수열 $a_n, b_n$이 있을 때, $a_n$의 $i$번째 원소와 $b_n$의 $j$번째 원소까지 봤을 때의 최장 공통 부분 수열의 길이를 $dp[i][j]$라고 하자. 아래와 같은 점화식을 세울 수 있다.$i = 0$ 또는 $j = 0$일 때, $dp[i][j] = 0$$a_i = b_j$일 때, $dp[i][j] = dp[i - 1][j - 1] + 1$$a_i \neq b_j$일 때, $dp[i][j] = MAX(dp[i..
