[알고리즘] 백준 9251번 : LCS

백준 9251번 : LCS(문제 링크)

• 사용 언어 : 파이썬(Python)
• 문제 유형 : 동적 프로그래밍(DP), LCS
• 난이도 : 하

소스코드

import sys

x = sys.stdin.readline().rstrip()
y = sys.stdin.readline().rstrip()

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

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

print(D[len(x)][len(y)])

설명

• 최장 공통 부분 수열(LCS)로 알려진 대표적인 DP문제이다.
• 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾아야 한다.
• 두 수열의 길이가 n미만 일 때, O(n^2)으로 문제를 해결할 수 있다.

---

• 우선적으로, 이 문제 해결을 위한 점화식을 구해보면 다음과 같다. 이 점화식을 그대로 코드로 옮기면 된다.

  

  • X, Y는 두 수열을 의미 한다.
  • D[i][j]는 X[0] ~ X[i]와 Y[0] ~ Y[j]의 공통 부분 수열의 최대 길이를 의미한다.
  • 아래표와 함께 보면서 생각해보면 이해가 훨씬 쉽다.

• 문제 링크의 예시 데이터와 점화식을 바탕으로 표를 만들어 채워보면 다음과 같다.

  • D[2][4](빨간 네모 박스 참고)의 값을 구할 때는 점화식의 1)번 경우에 해당한다. X[1], Y[3]가 각각 'C'로 동일하기 때문이다.
    이 때, 점화식대로 D[1][3](파란 네모 박스)에 +1을 해주면 D[2][4]값을 구할 수 있다.
    이를 풀어 설명해보면, D[1][3](파란 네모 박스)는 X[1], Y[3]인 C를 추가하기 전의 X, Y의 부분 수열이다. 즉, 각각 'A', 'CAP'이다. 이 두 수열의 최장 공통 부분 수열은 'A'로 길이가 1이다. 그 다음에 추가될 글자가 두 수열 모두 'C'로 동일하므로 C를 추가하기 전의 최장 공통 부분 수열의 길이에 그냥 +1을 해주면 되는 것이다.
  • 반면, D[4][2](초록 네모 박스 참고)의 값을 구할 때는 점화식의 2)번경우에 해당한다. X[3], Y[1]이 각각 'Y'와 'A'로 상이하기 때문이다.
    이 때, 점화식대로 D[4][1]과 D[3][2]값 중에 큰 값이 D[4][2]의 값이 된다.
    이를 풀어 설명해보면, X[3]을 추가하기 전인 X의 부분 수열 'ACA'와 Y[1]을 추가한 후의 Y의 부분 수열 'CA'의 공통 부분 수열의 최대 길이인 2와 X[3]을 추가한 후의 X의 부분 수열 'ACAY'와 Y[1]을 추가하기 전의 Y의 부분 수열 'C'의 공통 부분 수열의 최대 길이 1 중에 더 큰 값이 D[4][2]값이 되는 것이다.
  • 나머지 칸들도 위와 같은 방식으로 채워진다.