문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
더 쉬운 비슷한 유형의 DP 문제
문제 풀이
개인적으로 다이나믹 프로그램은 난이도가 높다고 생각한다. 그 이유는 DP 테이블 설계하는 게 생각보다 쉽지 않다. 시간복잡도에 따른 적절한 접근 방법을 고르는 게 익숙하지 않기 때문인 것 같다. 이전에는 항상 브루트포스 관점으로만 접근했었기 때문이다. 이번 기회에 시간 복잡도 관점에서 다른 풀이들이 왜 적절하지 않은지와 DP 테이블 설계에 대한 관점?을 정리해보고자 한다.
1. 브루트포스
1≤N≤1000 이므로 브루트포스로는 시간복잡도가 굉장히 커진다.
각각의 문자를 선택하는 경우는 2가지이므로
•
2. 그리디
그리디로는 적합하지 않다. 최선의 선택이 최적의 해를 만족하지 않는 경우가 있기 때문이다.
3. DP
나는 이것이 다이나믹 프로그래밍 문제라는 것을 알고 있었다. 기존의 LCS(11053) 문제 풀이를 활용할 수 있지 않을까 생각했지만, 실제로는 그렇게 간단하지 않았다. 가장 어려웠던 부분은 DP 배열에 어떤 값을 저장해야 하는지였다. 점화식을 중심으로 접근하려다 보니 문제를 너무 복잡하게 생각했던 것 같다. 단순히 필요한 값부터 저장하는 접근법으로 시작했어야 했는데, 이런 단순한 접근이 떠올리기 어려웠다.
일단 DP를 사용한다면 시간복잡도는 N 배열과 M 배열을 한번씩만 보면 되므로 다음과 같을 것이다.
•
DP 배열에 저장할 정보
•
DP[N][M] : S1의 n번째 문자까지, S2의 m번째 문자까지 살펴봤을 때의 LCS의 길이.
DP 관계식
•
초기값을 정의하기 쉽도록 1번 인덱스부터 시작해준다.
•
문자가 일치한다면 바로 직전의 dp 테이블 값에 +1을 해주면 LCS가 된다.
•
문자가 일치하지 않는다면, 두 문자열의 이전 LCS의 최대값을 입력해준다.
if (s1[n] === s2[m]){
dp[n][m] = dp[n-1][m-1] + 1
} else {
dp[n][m] = Math.max(dp[n][m-1], dp[n-1][m])
}
JavaScript
복사
코드
•
문자가 같을 경우 혹은 같지 않을 경우의 관계식을 설정이 굉장히 어려웠다.
function solution(input) {
const [N, M] = [input[0].length, input[1].length];
const [s1, s2] = input.map((s) => ' ' + s);
const dp = Array(N + 1)
.fill(0)
.map((item) => Array(M + 1).fill(0));
for (let n = 1; n < N + 1; n += 1) {
for (let m = 1; m < M + 1; m += 1) {
if (n === 1 && m >= 5) {
console.log(n, m, s1[n], s2[m]);
}
if (s1[n] === s2[m]) {
dp[n][m] = dp[n - 1][m - 1] + 1;
} else {
dp[n][m] = Math.max(dp[n][m - 1], dp[n - 1][m]);
}
}
}
return dp[N][M];
}
console.log(solution(input));
JavaScript
복사