📝 BOJ - LCS

thumbnail

문제

BOJ 9251번 : LCS

접근 방법

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

예시

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

마지막 문자가 같은 경우

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

마지막 문자가 다른 경우

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

결론

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

lcs-table

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

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

  • 마지막 문자가 같은 경우 : table[i][j]=table[i1][j1]+1table[i][j] = table[i-1][j-1] + 1
  • 마지막 문자가 다른 경우 : table[i][j]=max(table[i][j1],table[i1][j])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])

👋@코딩하는펭귄
파이썬과 웹에 관심 많은 컴공 전공자

GitHubInstagram