9251번:LCS

🔗 문제 ∙ 9251번: LCS

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP 와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째, 둘째 줄에 두 문자열이 주어지고, 문자열은 알파벳 대문자로만 이루어져 있고, 최대 1000글자로 이루어져있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

🔑 풀이

이 문제는 전형적인 dynamic programming 문제이다. 필수적으로 알아야 하는 문제라고 함.

어쨌든 두 문자열을 비교하면서 답을 찾아야하는데, 비교하는 방법을 찾아내는게 좀 까다로운 것 같다. 각 문자열을 '' 빈 문자열에서 주어진 문자열 형태로 하나씩 추가하면서 두 문자열을 비교한다고 생각하면 쉽다.

첫 줄을 보면, 문자열 A의 첫번째 문자열 부터 비교한다. 문자열 B는 ''부터 시작한다.

• (A, '') 와 같이 빈 문자열과 비교했을 때는, 공통되는 부분이 없기 때문에 0으로 초기화 되어있다.

• (A, C)
  A, C는 같지 않다. 해당 단계에서 가져가는 값은 0. 이전 단계들에서 중복되는 문자열이 있었다면 추가 되었을 것이기 때문에 (A, ''), ('', C) 비교에서 얻은 값들 중 최대 값을 가져온다(위의 핑크색 부분들). 둘다 0 이므로, A,C 비교 단계에서 최대 부분 수열의 길이는 0

• (A, CA)
  A와 A는 같다. 해당 단계에서 부분 수열은 A로 길이가 1이 되었다. 문자열 A에서의 'A'와 문자열 B에서 'A' 모두 고려하여 1로 추가한 것이다.
  마찬가지로 이전 단계에서 가져올 수 있는 값을 가져와야 하는데 이미 각 문자열에서 현재 A를 부분수열로 추가하였기 때문에, 이전 단계는 이 A를 고려하지 않은 바로 전 단계를 생각 해야한다. (A, CA) 에서 모두 A를 고려하지 않는 지점은 ('', C) 비교 지점이다. 이 단계의 값은 0 이기 때문에
  현재 단계 값 + 이전 단계 = 1+ 0 = 1 이 된다.

• (A, CAP)
  A와 P는 같지 않다.
  이전 단계는 (A, CA) 비교 지점, ('', CAP) 비교 지점이 된다. 이를 수치화 하면 각각 dp[i, j-1], dp[i-1, j] 지점이라고 할 수 있다.
  현재 값이 같지 않을 경우에는 아래와 같이 표현할 수 있고, 'A'와 'CAP' 문자를 비교하였을 때 최대 부분 수열의 길이는 1이 된다.

 dp[i][j] = max(dp[i][j-1], dp[i-1][j])

• (A, CAPC)
  A, C는 같지 않고, 위와 동일한 방법으로 진행한다.

• (A, CAPCA)
  A, A는 같다.
  해당 'A'를 부분 수열로 추가할 것이기 때문에 이전 단계에서 현재 부분 수열 'A'의 길이인 1을 더해주어야 한다. 여기서 이전 단계는 이 'A'를 고려하지 않은 ('', CAPC) 가 되고 해당 단계는 dp[i-1][j-1]로 표현할 수 있다.
  따라서

dp[i][j] = dp[i-1][j-1]+1

위와 같은 방법으로 (ACAYKP, CAPCAK)를 비교해나가면 dp[len(A)][len(B)]위치에 최장 부분 수열 길이가 오게 된다.

코드

A = input()
B = input()

dp = [[0] * (len(A)+1) for _ in range(len(B)+1)]

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

print(dp[len(A)][len(B)])

🛎 패스트 캠퍼스: 알고리즘/ 자료구조 온라인 강의의 해설을 참고하였음.

• 참고했는데, 구체적으로 왜 이렇게 되는지에 대해서는 강의 설명이 넘 부족한 것 같다ㅠ 내가 이해력이 부족한 것일 수 도 있.
  어쨌든 두뇌 풀가동 하여 풀이의 근거를 생각해보았는데 맞는 설명인지도 잘 모르겠다. dp 문제를 좀 더 풀고 다른 풀이들도 참고 해봐야겠음.