[백준] 9251 LCS / DP / Python / 골5

최장 공통 부분 수열 LCS를 구현하는 문제이다

 

LCS 개념은 이분이 굉장히 잘 설명해 두셨음

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

 

첫 번째 문자열과 두 번째 문자열의 길이를 각각 가로, 세로로 두고 2차원 배열을 만든다

 

이중 for문을 돌면서 문자열의 원소를 비교한다

(두 번째 문자열의 i번째 문자에 대해 첫 번째 문자열과 전부 비교한다)

 

첫 번째 문자열의 i번째, 두 번째의 문자열의 j번째를 비교했을 떄

 

1. 두 문자열이 같은 경우

- dp[i-1][j-1] 값에 1을 더한 값으로 입력한다

- 부분 수열의 특징은 연속되지 않아도 되기 때문에, 계속 누적해서 부분수열 길이를 가지고 있음

- 현재 비교 값이 같다는 의미는 누적 길이에 1이 늘어난다는 뜻

- 현재 비교 하고 있는 원소의 이전 값에 저장된 부분 수열에 길이에 1을 더해줌

 

2. 다른 경우

- dp[i-1][j], dp[i][j-1] 중에 max 값을 고른다

- 마찬가지로 부분 수열의 누적 길이를 가지고 있기 때문에, 이전에 저장된 값 중에 max 값을 연장해주는 것

 

a = list(input().strip())
b = list(input().strip())

al = len(a)
bl = len(b)

arr = [[0 for _ in range(al+1)] for _ in range(bl+1)]

for i in range(1,bl+1):
    for j in range(1,al+1):
        if a[j-1]==b[i-1]:
            arr[i][j]=arr[i-1][j-1]+1
        else:
            arr[i][j]=max(arr[i-1][j],arr[i][j-1])
print(arr[bl][al])