LCS 문제

LCS 문제

---

LCS란 Longest Common Subsequence 혹은 Longest Common String 의 약자다. LCS 문제는 특정 문자가 같은 지 여부에 따라 테이블에 기록하는 형식으로 길이와 부분 문자열을 구할 수 있다. 즉, 동적계획법을 활용하여 문제를 풀 수 있다.

문제접근법

---

LCS 문제는 동적 프로그래밍 접근법에 따라 해결한다.

1. 문재의 해를 분석한 후 부분문제로 분할한다.
2. 부분문제의 해를 보고 큰 문제와의 관계식을 세운다.(점화식 설계)
3. 적당한 순서로 dp table을 채운다.
4. table에서 해를 계산한 후에 정확성을 증명한다.

동적계획법에서 중요한 부분은 큰문제와 작은문제의 관계로부터 재귀형태를 찾아 dp table을 채우는 것이다. 정확성 증명은 테이블 채우면서 자연스레 증명된다.

점화식

문자열 X와 문자열 Y가 존재할 때, X의 부분문자를 i, Y의 부분문자를 j라고 한다면,
x[i] == y[j]: LCS(i,j) = LCS(i-1, j-1) + 1
x[i] != y[j]: LCS(i,j) = max(LCS(i-1,j), LCS(i, j-1))

비교하는 문자가 같다면 부분문자열의 길이는 위의 식을, 비교하는 문자가 다르다면 부분문자열의 최대길이는 아래의 점화식을 통해 계산할 수 있다.

내 코드

---

import sys
input = sys.stdin.readline

x = input().strip()
y = input().strip()

dpt = [[0] * (len(x) + 1) for _ in range(len(y) + 1)]

for i in range(1, len(y) + 1):
    for j in range(1, len(x) + 1):
        if x[j-1] == y[i-1]:
            dpt[i][j] = dpt[i-1][j-1] + 1
        else:
            dpt[i][j] = max(dpt[i][j-1], dpt[i-1][j])

print(dpt[-1][-1])

마주쳤던 문제

LCS는 다이나믹 프로그래밍을 통해 쉽게 해결할 수 있는 문제다. 대신에 문자열의 길이가 길어지면 시간복잡도가 O(N^2)이기 때문에 풀이 시간이 길어진다.

문자열에서 바라보는 문자, 테이블 갱신의 인덱스를 일치하는데에 시간을 잡아먹었다. 하나의 인덱스가 움직일 때마다 문자열과 dp 테이블에 어떤 영향을 가는지 제대로 확인하지 못해서 계속 인덱스 오류가 났다.

for i in range(1, len(y) + 1):
    for j in range(1, len(x) + 1):
        if x[j-1] == y[i-1]:

특히, 2차원 테이블의 열과 행을 바꿔서 인식을 하다보니 뒤에서 디버깅을 하는데 애를 많이 먹었다.

표를 각각의 인덱스가 서로에게 어떤 영향을 주는지 직관적으로 파악할 수 있을 때까지 그려야겠다.

문제출처

---

9251번: LCS