Longest Common Subsequence
최장 공통 부분 수열, 여러 개의 수열 모두의 부분수열 중 가장 긴 수열을 찾는 문제이다. https://www.acmicpc.net/problem/9251
해법
동적 해결법에서 가장 중요한 포인트는 dp 배열에 의미를 붙이는 작업이다.
dp 배열에 의미를 잘 붙이면 점화식이 잘 세워지고, 문제가 쉽게 해결된다.
이 문제에서 dp[n][m]
의 의미는
a[0~n]과 b[0~m] 까지의 LCS
로 부여할 수 있다. 이럴 경우 다음과 같은 점화식이 성립한다.
1 |
|
즉 dp[i][j]
의 값을 dp[i-1][j-1] + 1
,dp[i-1][j]
, dp[i][j-1]
3개의 값을 통해서 찾는 것이다.
Sliding window
흔한 기법인 sliding window를 통해서 dp 배열의 크기를 줄일 수 있다.
dp[i]
행을 계산할때 dp[i-1]
행과 dp[i]
행만 사용된다는 점을 이용해서,
dp 배열의 값을 모두 저장하는 대신, 2개의 행만을 번갈아가며 저장한다.
통념으로 메모리 사용양 에서만 이득이 있을 것이라 생각되지만, 캐시 지역성이 높아져서 속도까지 빨라지는 이점이 있다.
1 |
|