백준 9251- LCS 풀이

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

처음 문제를 봤을때, 접근법이 선뜻 떠오르지 않았던 문제이다.

dp 알고리즘의 대표격인 문제라 정리해둔다.

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제

부분 수열이란?

원래 수열에서 몇 개를 골라 순서는 유지한 채 만든 수열이다.

- 순서는 유지해야 한다.

- 중간 원소는 건너뛰어도 된다.

 

예를 들어 원래 수열이 [2, 3, 5, 6, 9] 라면, 부분 수열은

- [2, 3, 5, 6]

- [2, 5, 6]

- [3, 9]

... 등이 있다.

이런식으로 원래 순서만 안 바꾸면 된다.

 

왜 DP 알고리즘 대표 문제일까?

DP의 핵심 사고 방식은 다음과 같다.

1. 큰 문제를 작은 문제로 나누고,
2. 그 작은 문제의 답을 재사용해서 큰 문제를 푼다.

 

LCS 문제는 다음과 같은 특성을 가지고 있다.

1. 완전탐색으로 풀면 경우의 수가 너무 많다.

- 두 문자열에서 공통 부분 수열을 찾으려면 각 문자를 고를지 말지 계속 결정해야 하니까 경우의 수가 매우 커진다.

 

2. 같은 부분 문제가 계속 반복된다.

- 문자열 A의 앞 i글자와 B의 앞 j글자의 LCS를 다시 구해야되는 경우가 많다.

- 즉 중복되는 부분 문제가 많다.

 

3. 큰 문제의 답이 작은 문제의 답으로 결정된다.

➡️ 따라서 DP 알고리즘을 통해 최적의 해답을 구할 수 있다.

 

1. dp[i] 정의

문자열 전체를 한 번에 보지 말고, 앞에서부터 조금씩 잘라서 생각해보자.

dp[i][j] = A의 앞 i글자와 B의 앞 j글자의 LCS 길이

 

2. 점화식 세우기

LCS의 점화식은 2개의 경우의 수를 고려해봐야 한다.

 

1️⃣ 마지막 문자가 같은 경우

문자열 A와 B의 마지막 문자가 같다고 가정해보자.

- A[i - 1] == B[j - 1] 인 상황

두 문자가 같다면 그 문자는 공통 부분 수열에 포함시킬 수 있다. 즉...

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

왜냐하면 A 앞 i - 1 글자와 B 앞 j - 1 글자의 LCS 뒤에 마지막 같은 문자 하나만 추가하면 되기 때문이다.

 

2️⃣ 마지막 문자가 다른 경우

문자열 A와 B가 다르다고 가정해보자.

- A[i - 1] != B[j - 1] 인 상황

이런 상황에서 dp[i][j] 를 채우려면 더 작은 부분 문제의 결과를 이용해서 채워야 한다.

예시를 통해 이해를 해보자.

- A = "ABC"

- B = "AEB"

 

인 상황에서 dp[3][3] 을 생각해보자. (A의 3번째 문자와 B의 3번째 문자)

 

A[2]는 'C', B[2]는 'B'이므로 LCS에 추가할 수 없다. LCS는 두 문자열에 공통으로 존재하는 같은 문자들만 순서를 지켜서 뽑아야 하므로, 'C'와 'B'를 한 번에 채택하는 것은 불가능하다.

 

따라서 현재 위치에서는 두 가지 경우를 생각해야 한다.

1. A의 마지막 문자 'C'를 사용하지 않고, A의 범위를 하나 줄인 경우

2. B의 마지막 문자 'B'를 사용하지 않고, B의 범위를 하나 줄인 경우

즉, dp[i-1][j] 와 dp[i][j-1]를 비교해서, 그중 더 긴 LCS의 길이를 dp[i][j]로 선택하면 된다.

 

그래서 점화식은 다음과 같다.

# 두 문자가 같을때
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])

 

3. base case

문자열 둘 중 하나라도 길이가 0이면 LCS의 길이는 당연히 0이다.

- dp[0][j] = 0

- dp[i][0] = 0

 

코드

A = input()
B = input()

len_A = len(A)
len_B = len(B)

dp = [[0] * (len_B + 1) for _ in range(len_A + 1)]

for a in range(1, len_A + 1):
    for b in range(1, len_B + 1):
        if A[a - 1] == B[b - 1]:
            dp[a][b] = dp[a - 1][b - 1] + 1
        else:
            dp[a][b] = max(dp[a - 1][b], dp[a][b - 1])

print(dp[len_A][len_B])

dp[i][j] 를 A의 앞 i 글자, B의 앞 j 글자로 정의했기 때문에, dp의 인덱스를 1부터 시작하게끔 구현하였다. 그래서 실제 문자열에 접근할때는 -1을 해주는 것을 볼 수 있다.

여기서 모든 인덱스를 0부터 시작하게 할 수도 있다.

하지만 그렇게 되면 이전 경우의 dp 인덱스가 접근할 때, 즉

dp[a-1][b-1]과 같이 이전 인덱스에 접근할때 음수 인덱스에 접근하게 될 수도 있다.

그래서 불필요한 예외처리 코드가 추가되어야 한다.