1. 문제

---

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

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

2. 아이디어

---

• LCS(Longest Common Subsequence, 최장 공통 부분 수열)

  1. 말 그대로 핵심은 공통 부분 수열 중 가장 긴 것을 찾는 것!
  2. 최근에 추가된 문자가 같으면 전에 있던 공통 부분 수열 개수 + 1
  3. 아니면 기존에 주어진 문자열로 만들 수 있던 최대 길이를 갖게 됨

3. 코드

---

clone

x = input()
y = input()

dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)] # 2차원 배열 생성

for i in range(1, len(x) + 1):
  for j in range(1, len(y) + 1): 
    if x[i - 1] == y[j - 1]: # 최근에 추가된 문자가 서로 같을 때
      dp[i][j] = dp[i - 1][j - 1] + 1 # 전에 있던 부분 수열 개수 + 1
    else: # 다르면 
      dp[i][j] = max(dp[i][j-1], dp[i-1][j]) # 기존에 주어진 문자열로 만들 수 있던 최대 길이를 갖게 됨

print(dp[-1][-1])

출처 : https://github.com/ndb796/Fast_Campus_Algorithm_Lecture_Notes/blob/master/Notes/%5B13%5D%20CHAPTER%2008.%20%EB%8F%99%EC%A0%81%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20-%20%ED%95%B5%EC%8B%AC%20%EC%9C%A0%ED%98%95%20%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4.pdf
https://suri78.tistory.com/11