📝 BOJ - LCS

문제

BOJ 9251번 : LCS

접근 방법

영어 대문자로 이루어지고 같은 길이의 문자열 2개가 주어졌을 때, 두 문자열의 최장 공통 부분 수열(Longest Increasing Subsequence, LCS)을 구하는 문제이다.

예시

문제의 예시인 CAPCAK와 ACAYKP를 가지고 생각해보자. 이 때 공통 부분 수열을 어떻게 파악할 수 있을까? 바로 첫 문자부터 시작해 하나씩 대상을 넓혀가면서 마지막 문자를 비교하고 그 문자가 없기 전의 상황을 살펴보면 된다.

마지막 문자가 같은 경우

CA와 ACA의 상황에서 마지막 문자는 A임을 확인할 수 있다. 과거의 상황이 어찌되든 간에 최장 공통 부분 수열의 길이는 최소 1 이상이다. 그럼 과거의 상황은 언제일까? C와 AC인 상황이다. 이 때의 최장 공통 부분 수열의 길이에 +1을 해주면 CA와 ACA의 공통 부분 수열 길이를 구할 수 있다

마지막 문자가 다른 경우

ACA와 CAP의 상황에서 마지막 문자는 각각 A와 P이므로 다르다. 이 경우는 마지막 문자는 고려하되 두 문자가 다르므로 두 경우 중 가장 큰 경우를 가져온다. 그 경우가 바로 AC와 CAP인 경우와 ACA와 CA이다. 전자는 최장 길이가 1이고 후자는 2이므로 가장 큰 값인 2가 ACA와 CAP의 최장길이가 된다.

결론

모든 경우의 수를 테이블로 나타내면 다음과 같다. 각 행과 열은 문자열을 나타내며 각 칸은 각 문자열을 행과 열의 값까지 제한할 때의 최장 공통 수열의 길이이다. 예를 들면, (3, 3)이면 CAP와 ACA일 때의 최장 공통 수열의 길이를 말한다.

정리하면 제약사항인 문자열의 길이에 따라 최장 공통 수열의 길이를 갱신하면 된다. 즉, 현재 각 문자열의 마지막 문자를 비교하여 같은지 파악한다. 만약 같다면 바로 그 전 상황의 최장 길이에 +1을 하고, 같지 않다면 다른 두 문자를 각각 포함하지 않은 경우 중 큰 경우의 값을 가져오면 된다.

위의 테이블을 점화식으로 나타내면 다음과 같다.

• 마지막 문자가 같은 경우 : $table[i][j] = table[i-1][j-1] + 1$
• 마지막 문자가 다른 경우 : $table[i][j] = max(table[i][j-1], table[i-1][j])$

교훈

제약사항을 풀어간다고 생각했지만 동적계획법의 본질은 큰 문제를 작은 문제로 쪼개는 것이다. 이를 항상 염두해두고 제일 최소 단위로 쪼갰을 때 어떻게 현재의 문제를 해결할 수 있는지 생각하자.

소스코드

seq1, seq2 = input(), input()
l1, l2 = len(seq1), len(seq2)
table = [[0]*(l2+1) for _ in range(l1+1)]

for i in range(1, l1+1):
  for j in range(1, l2+1):
    # 마지막 문자가 같은 경우
    if seq1[i-1] == seq2[j-1]:
      table[i][j] = table[i-1][j-1] + 1
    # 마지막 문자가 다른 경우
    else:
      table[i][j] = max(table[i-1][j], table[i][j-1])

print(table[l1][l2])