BOJ 9251번 : LCS

LCS (Longest Common Subsequence)알고리즘이다.

 

문자열을 쉽게 처리하기 위하여 python으로 코드를 구성하였다.

 

최장 공통 부분 수열 문제는, 두 수열에서 공통이 되는 가장 긴 수열을 찾아내는 문제이다.

 

ACAYKP 와 CAPCAK 의 LCS는 ACAK가 될것 이다.

이 알고리즘을 이해하기 위해서 표를 그려보자면, 아래와 같다.

 

서로 같은 문자가 나올 경우, 대각선 위에서 점수를 더해준다.

서로 다른 문자가 나올 경우, 위와 왼쪽에서 큰 수를 가진다.

즉,

(_str1[j-1] == _str2[i-1]) -> arr[i][j] = arr[i-1][j-1]+1

(_str1[j-1] != _str2[i-1]) -> max(arr[i-1][j], arr[i][j-1]) 이다.

 

<소스코드>

_str1 = [x for x in input()]
_str2 = [x for x in input()]
arr = [[0] * (len(_str1) + 1) for _ in range(len(_str2) + 1)]
for i in range(1,len(_str2)+1):
    for j in range(1, len(_str1)+1):
        if(_str1[j-1]==_str2[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[len(_str2)][len(_str1)])

문제 : 

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

9251번: LCS