Longest Common Subsequence

최장 공통 부분 수열, 여러 개의 수열 모두의 부분수열 중 가장 긴 수열을 찾는 문제이다. https://www.acmicpc.net/problem/9251

해법

동적 해결법에서 가장 중요한 포인트는 dp 배열에 의미를 붙이는 작업이다. dp 배열에 의미를 잘 붙이면 점화식이 잘 세워지고, 문제가 쉽게 해결된다. 이 문제에서 dp[n][m]의 의미는

a[0~n]과 b[0~m] 까지의 LCS

로 부여할 수 있다. 이럴 경우 다음과 같은 점화식이 성립한다.

if (a[i-1] == b[j-1])
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

즉 dp[i][j]의 값을 dp[i-1][j-1] + 1,dp[i-1][j], dp[i][j-1] 3개의 값을 통해서 찾는 것이다.

흔한 기법인 sliding window를 통해서 dp 배열의 크기를 줄일 수 있다. dp[i] 행을 계산할때 dp[i-1] 행과 dp[i] 행만 사용된다는 점을 이용해서, dp 배열의 값을 모두 저장하는 대신, 2개의 행만을 번갈아가며 저장한다.

통념으로 메모리 사용양 에서만 이득이 있을 것이라 생각되지만, 캐시 지역성이 높아져서 속도까지 빨라지는 이점이 있다.

if (a[i-1] == b[j-1])
    dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
else
    dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1]);