[백준 / Python] 9252 LCS 2

1️⃣ 서론

이 문제는 백준 9252 LCS 2 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다.

2️⃣ 문제 설명

최장 공통 부분 수열(LCS)의 길이와 최대 길이에 대한 문자열을 출력하는 문제이다.

3️⃣ 풀이

LCS문제는 전형적으로 dp로 해결이 가능한 문제이다.

dp에 대한 수도 코드는 다음과 같다.

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

자세한건 LCS 나무위키를 참조하면 잘 나와있다. 여기서 기존의 LCS 문제와 달랐던 것이 역추적인데 이 문제에서 나온 새로운 유형이라 이에 대해 자세히 써보려고 한다.

아래와 같이 LCS의 부분길이가 담겨진 DP가 있다고 가정해보자

lcs2

역추적은 dp의 마지막 셀에서 출발한다. 역 추적은 다음 공식을 따른다.

현재 셀의 왼쪽 셀과 위쪽 셀이 모두 자신보다 1씩 작다면 현재 셀이 답에 포함되고 대각선 위쪽 셀로 이동한다.
1번이 아니라면 왼쪽 셀과 위쪽 셀중 더 큰곳으로 이동해서 다시 1번 부터 수행
셀의 원소가 0(LCS의 길이가 0)이 될 때까지 1,2 번을 계속 수행

위 그림의 밑줄을 보며 이 공식을 적용하면 역추적이 가능한 것을 알 수 있다.

이를 수행하면 아래와 같은 그림과 같이 역 추적이 되어 MZJAWXU 와 XMJYAUZ의 LCS는 MJAU 임을 알 수 있다.

LCS_ANSWER

이를 구현한 코드는 아래와 같다.

4️⃣ 코드

a = input()
b = input()

len_a = len(a)
len_b = len(b)
dp = [[0] * (len_a + 1) for _ in range(len_b + 1)]

for i in range(1, len(b) + 1):
    for j in range(1, len(a) + 1):
        if b[i - 1] == a[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

ans = ""
now = dp[-1][-1]
y = len_b
x = len_a

while now != 0:
    if dp[y][x - 1] == now - 1 and dp[y - 1][x] == now - 1:
        ans = a[x - 1] + ans
        now -= 1
        y -= 1
        x -= 1
    else:
        if dp[y - 1][x] > dp[y][x - 1]:
            y -= 1
        else:
            x -= 1

print(dp[-1][-1])
print(ans)

5️⃣ 마치며

LCS에 대해 알고 있었는데 LCS 역추적의 알고리즘을 알 수 있었던 좋은 문제였다. 앞으로 최적화하는 방법도 나무위키에 있었는데 이 쪽도 다음 문제가 나오면 풀어볼 것 같아 기대가 된다.