[BOJ] 9251번 : LCS

문제 바로가기 => LCS

🔒 문제

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

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

⌨ 입력

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

🖨 출력

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

📚 예제

Ex)

ACAYKP
CAPCAK

4

📌 풀이

arr1과 arr2에 각각 문자열을 저장해준다.
arr1의 문자열 길이를 n, arr2의 문자열 길이를 m으로 둔다.
조심해야할 점은 '\n'까지 문자열로 받아들였는지 생각해봐야한다.
나는 '\n'까지 문자열로 포함시켜서 문제를 풀어서 인덱스 수에 + 1을 해서 문제를 풀지않아도 괜찮았지만,
만약 그렇지 않다면 아래의 과정에서는 n + 1, m + 1을 해서 dp를 만들어줘야한다.

dp[n][m] = 그 위치 까지의 LCS 길이

위 그림을 보면 문자열이 시작되기 전에 padding 행과 열이 존재하는데, 계산할 때 편하게 하기 위해 만들었다.

위 그림의 맨 왼쪽 열은 arr1 문자열의 각 원소로, 비교 기준이 될 것이고, 맨 위의 행은 arr2 문자열의 각 원소로 비교 대상이 될 것이다.

그림을 보면서 풀이를 해보자.

1. arr1[i] == arr2[j] => dp[i][j] = dp[i - 1][j - 1] + 1

먼저 arr1의 첫 원소인 A를 arr2 문자열과 비교해 보는 것이다. 만약 arr2에도 A고 그 위치가 dp[i][j]라고 하자.
그러면 dp[i][j] = dp[i - 1][j - 1] + 1과 같다. dp[i - 1][j - 1]에 저장된 값에다가 1을 더해주면서 LCS를 구하는 것이다.
그림에서 파란색 화살표가 그것을 설명하고 있다.

2. arr1[i] != arr2[j] => dp[i][j] = min(dp[i - 1][j], dp[i][j -1])

만약 서로 원소가 일치하지 않는 경우 그 위치 즉 dp[i][j]의 왼쪽과 바로 위의 값 중 더 큰 값을 가져오면된다.
식으로 나타낸다면 dp[i][j] = min(dp[i - 1][j], dp[i][j -1]) 이다.
그림에서 빨간색 화살표가 그것을 설명하고 잇다.

3. 결과
   결과는 아래와 같다. 즉 최대값은 4 이다.

🔑 python 코드

import sys
arr1 = list(sys.stdin.readline())
arr2 = list(sys.stdin.readline())
n, m = len(arr1), len(arr2)
dp = [[0 for _ in range(m)] for _ in range(n)]

for i in range(1, n):
    for j in range(1, m):
        if(arr1[i - 1] == arr2[j - 1]):
            dp[i][j] = dp[i - 1][j]  + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

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