한 살도 이해하는 백준 9251번 LCS [DP][Python]

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

---

문제 유형

DP

---

문제 풀이

 

문제를 풀기 위해서

한 문자열을 기준으로 잡고, 한 글자씩 추가하면서 지금까지의 부분 문자열의 'LCS(최장 공통 부분 수열)'이 몇 개인지 기록해나간다.

 

주어진 첫 번째 문자열의 sub suquence를 S1, 두 번째 문자열의 sub sequence를 S2라고 했을 때,

S1를 기준으로 잡고, S2에 문자를 하나씩 늘려가면서 비교한다.

 

하나 하나 해보기

단순하게 생각해보면, 문자를 비교하면서 같은 글자가 나오면 우선 LCS에 +1을 해주는 것이 맞다고 생각이 든다.

그런데, 

S1: A

S2: CA

 

S1: A

S2: CAPCA

와 같은 상황을 봤을 때, 문자가 같다고 무조건 +1을 해주는 단순한 방법으로는 

+1을 해야하는데 중복으로 +2가 될 수 있으므로, 조금 더 생각을 해봐야 할 것 같다.

 

한 바퀴를 직접 더 진행해보자.

S1: AC

S2: C

 

S1: AC

S2: CAPC

두 상황에서 S1의 C와 S2의 C가 같다.

이 상황에서 어떻게 LCS에 +1을 해줘야할까?

 

'비교하는 글자가 있기 바로 전까지의 LCS'  + ( if 현재 문자를 비교한 결과가 같으면  1, 다르면 0)

 

을 해주면 될 것 같다.

 

S1: AC

S2: CAPC

의 바로 이전까지의 LCS는

현재 비교하고 있는 C가 있기 전인

 

S1: A

S2: CAP

까지의 LCS이다.

 

따라서, 현재 문자를 비교했을 때 같다면 바로 이전까지의 LCS에 +1 을 해주고,

같지 않다면, 비교 이전까지의 LCS를 갖고 있으면 된다.

 

즉, 현재 위치 기준 LCS는 이전 LCS에  + 1을 더하거나,  더하지 않거나  두 가지 중 한 가지가 된다.

위를 기반으로 점화식을 만들 수 있으며,
각 부분에서 이전의 결과가 반복적으로 사용되고 해당 최적 결과값이 그대로 사용되니 
DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

 

이 문제에서는 문자를 하나씩 증가시키며 비교하고 있으므로,

두 문자열로 2차원 행렬을 만들어 표로 보는 것이 규칙을 찾고 점화식을 만들때 더욱 편하다.

 

2차원 행렬로 lcs[i][j] 라고 표현할 때, 바로 이전까지의 LCS는 lcs[i-1][j-1] 임을 알 수 있다.

따라서 비교한 문자가 같은 경우, 

 

 lcs[i][j] = lcs[i-1][j-1] + 1 

 

이라고 점화식을 세울 수 있겠다.

 

그렇다면, 나머지 경우인 비교한 문자가 같지 않은 경우는 어떻게 점화식을 세울 수 있을까?

 

S1: AC

S2: CAPCA

를 예를 들어보자,

 

C와 A는 비교했을 때 문자가 같지 않으므로,

각각 두 문자를 비교하기 전인

 

S1: AC

S2: CAPC

일 때의 LCS나

 

S1: A

S2: CAPCA

일 때의 LCS 중에서

 

즉, 기존에 주어진 문자열로 만들 수 있던 LCS 중 최대 LCS를 가지면 될 것 같다.

따라서 비교한 문자가 같지 않은 경우는 점화식을 다음과 같이 작성할 수 있다.

 

lcs[i][j] = max( lcs[i-1][j], lcs[i][j-1] )

 

 

정리해 보면, 점화식은 다음과 같다.

 

✅ 비교한 문자가 같은 경우,
lcs[i][j] = lcs[i-1][j-1] + 1 

✅ 비교한 문자가 같지 않은 경우,
lcs[i][j] = max( lcs[i-1][j], lcs[i][j-1] )

---

DP 단계별로 풀어나가기

 

1️⃣ DP로 풀 수 있는 문제인지 확인하기

🔽

2️⃣ 문제의 변수 파악하기

정의

: lcs[i][j] = 문자 위치 [i][j]에서의 LCS

🔽

3️⃣ 점화식 만들기

점화식

✅ 비교한 문자가 같은 경우,
lcs[i][j] = lcs[i-1][j-1] + 1 

✅ 비교한 문자가 같지 않은 경우,
lcs[i][j] = max( lcs[i-1][j], lcs[i][j-1] )

🔽

4️⃣ 메모하기(Memoization)

lcs 2차원 배열에 메모되고 있다.

🔽

5️⃣ 기저 상태 파악하기

기저 상태는 행과 열에서 가장 첫번째 문자를 비교하는 경우일 것이다.

기저 상태

lcs[0][j], lcs[i][0] = 0

그런데 점화식을 사용하기 위해서는 i-1, j-1이 사용되어야 하므로,

행렬에서 0으로 구성된 한 행과 한 열을 추가해준다.

(아무 문자도 비교하지 않는 상태를 의미하고, 계산을 위해 추가한다 생각하면 편하다.)

🔽

6️⃣ 구현하기

1) Bottom-Up  - 반복문 사용 ✅

 

 

 

참고로, 0으로 구성된 한 행과 한 열 때문에 행렬에서의 문자 위치가 하나씩 뒤로 밀렸으므로(+1), 
문자열에서의 비교는 1을 빼준 s1[i-1]과 s[j-1]을 비교한다.