[BOJ 9251] LCS(왜 동적계획법인가?)

https://www.acmicpc.net/problem/9251

9251번: LCS

 

 

 

이 문제는 정말 다이나믹 프로그래밍의 정석같은 문제라고 볼 수 있다.

 

 

 

---

 

 

 

이 문제를 재귀 함수나, 동적 계획법으로 풀지 않았을 경우를 생각해보자.

 

 

 

 

두 문자열중에, 짧은 문자열을 사용해서 나올 수 있는 조합들을 모두 체크해본다고 가정하자.

 

 

 

 

짧은 문자열의 길이가 5라고 가정하면,

 

 

 

 

5C0 + 5C1 + 5C2 + 5C3 + 5C4 + 5C5의 연산이 필요하다.

 

 

 

 

물론 문자열의 길이가 짧다면 이렇게 해결할 수 있지 않을까?

 

 

 

 

조합의 합은 2의 5승이다. 즉 2의 n(문자열의 길이)가 되게 된다.

 

 

 

 

문자열의 길이가 1000인 것을 고려하면, 시간복잡도에서 틀렸다는 것을 알아야 한다!

 

 

 

 

이제, 시간 복잡도가 작은 해결책을 찾아야 한다.

 

 

 

 

두 문자열의 LCS를 찾을 때, 재귀함수로 구할 수도 있다. 하지만, 재귀함수를 쓰면 시간초과가 발생한다.

 

 

 

 

시간 초과를 직접 경험해보기전에 동적 계획법(Dynamic Programming)을 생각하면 가장 좋다.

 

 

 

 

앞선, 글에서 모든 재귀함수가 동적 계획법이 되는 건 아니라고 했다.

 

 

 

 

하지만, 이 경우에 재귀함수는 동적 계획법을 적용할 수 있다.

 

 

 

---

 

 

 

동적 계획법은, 기존 문제를 해결하기 위해서, 작은 문제들의 해결 방식을 이용해야 한다.

 

 

 

 

S1과 S2의 문자 인덱스를 i, j라고 생각해보자.

 

 

 

 

그렇다면, 두 가지의 경우로 작은 문제들의 해결 방식을 이용할 수 있다.

 

 

 

 

문제의 정답을 DP[i][j]라고 정의해보자.

 

 

 

 

1. S1[i] == S2[j]인 경우, DP[i][j] = 1 + DP[i - 1][j - 1]

 

 

 

 

2. S1[i] != S2[j]인 경우, DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])

 

 

 

 

위 두 가지 점화식으로 모두 구할 수 있다.

 

 

 

 

For문을 이용해서 DP배열(작은 문제들)들을 채워가면, 우리가 원하는 문제의 값을 찾을 수 있다.

 

 

 

 

---