백준 9251 LCS

백준 9251번 LCS 문제입니다.

https://www.acmicpc.net/problem/9251

파이썬 풀이

first = list(input())
second = list(input())

def lcs(first, second):
  n = len(first)
  m = len(second)
  lcs_table = [[0 for _ in range(n+1)] for _ in range(m+1)]
  for i in range(m):
    for v in range(n):
      if first[v] == second[i]:
        lcs_table[i+1][v+1] = lcs_table[i][v] + 1
      else:
        lcs_table[i+1][v+1] = max(lcs_table[i+1][v], lcs_table[i][v+1])

  return lcs_table[m][n]

print(lcs(first, second))

LCS 알고리즘 & 다이나믹 프로그래밍

이 문제는 LCS 알고리즘을 활용하여 푸는 문제이다. LCS는 다이나믹 프로그래밍 알고리즘으로부터 기인하는데 중간 계산을 저장하는 방식이다.

항상 다이나믹 프로그래밍 알고리즘이 직관적으로 이해하기가 힘든 상황이 오는데 이 문제가 그랬다.

두 문자열을 비교할 때 dp 테이블을 하나 만들어주고 문자열을 차츰 늘려나가면서 전부 비교해봐야한다. 이때 전부 일일이 비교 및 계산하려면 시간이 많이 소요된다.

따라서 각 알파벳을 하나씩 비교하면서 비교한 값을 저장하는 방식이다. 다음 알파벳을 계산할 때에는 여태까지 적용된 알파벳에 대한 값을 dp 테이블에서 꺼내와 현재 알파벳과 비교값을 더해주는 것이다.

여기서 예제로 나온 문자열은

ACAYKP ---- 1th
CAPCAK ---- 2th

이다.

원래 정확한 계산은

• ACAYKP 와 CAPCAK의 부분 수열의 최장길이를 구해준다.

-> ACAYKP 와 CAPCA의 부분 수열과의 최장길이를 구하고 마지막 'P' 만 고려해도 되지 않을까??

-> 순서대로 CAPC, CAP, CA, C 까지 내려와서 각각의 해를 구한 후 최종적인 문제의 해결을 하는데 사용해도 무관하다.

-> 다이나믹 프로그래밍을 사용하는 이유이다!!

알고리즘

1. 2th의 'C'를 1th의 각 부분 수열과 비교하고 최장길이를 구해주고 dp 테이블에 저장한다.

2. 'CA'를 1th의 각 부분의 수열과 비교할텐데 dp 테이블에 있는 'C'와의 결과를 활용하여
   'CA'의 최장거리 = 'C'와의 결과 + 'A'와의 결과
   dp 테이블에 저장한다.

3. 다음과 같은 방식을 순차적으로 하면 최종적으로 dp 테이블에 마지막 수는 ACAYKP 와 CAPCAK의 부분 수열의 최장길이에 대한 해답이다.