[백준] 9251 : LCS / python

1. 문제 설명

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때,

모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

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

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다.

문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

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

 

2. 풀이 전 계획과 생각

두 문자열의 공통 부분 수열을 구하는 문제다.

 

모든 경우의 수를 다 따져 본다면?

2 * 1000! 😵  너무 크다! 시간 복잡도를 줄여보자.

 

🤔 문제를 정의 해보자.

dp[i][j] → A가 i번째 위치 일 때, LCS 길이 B가 j번째 위치일 때, LCS의 길이

dp[A의 문자열 길이][B의 문자열 길이] → 구하고자 하는 답

 

🤔 점화식은?

A가 i번째 일 때, B가 j번째 일 때 서로의 값이 같은 경우가 있고, 서로의 값이 다른 경우가 있다.

1. A[i] = B[j] : dp[i][j] = dp[i-1] + dp[j-1] + 1
2. A[i] ≠ B[j] :
   1. A의 체크해주는 위치가 그대로 있는 경우(= B의 체크해주는 위치가 움직이는 경우)가 있고
   2. B의 체크해주는 위치가 그대로 있는 경우 (= A의 체크해주는 위치가 움직이는 경우)가 있다.
   둘 중의 LCS의 길이가 더 긴 것을 고른다.
3. dp[i][j] = max(dp[i-1] [j], dp[i] [j-1])

• 초기값
  
  • dp[0][0] = 0
  • dp[1][0] = 0
  • dp[0][1] = 0

 

3. 풀이

str1 = input()
str2 = input()

N = len(str1)
M = len(str2)

dp = [[0]*(M+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        if str1[i] == str2[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[N][M])

 

4. 풀이하면서 막혔던 점과 고민

• indexing error
• index를 1번째 위치부터 시작하니까, 문자열 앞에 스페이스 추가해주자.

 

5. 풀이

str1 = input()
str2 = input()

N = len(str1)
M = len(str2)

str1 = " " + str1
str2 = " " + str2

dp = [[0]*(M+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        if str1[i] == str2[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[N][M])