알고리즘 - 동적계획법 (9251 LCS)

문제

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

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

입력

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

 

출력

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

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4

---

문제 요약

두 문자열중 공통된 단어중 가장 긴 수열을 찾는 문제

 

접근 방식

지금까지는 모두 자신의 배열에서 이전 값을 비교하며 사용했기에 1차원 dp를 선언했지만 다른 문자열과 비교를 하기때문에 두개의 배열이 필요하다 생각했다.

하지만 그렇게 되면 모든 경우에 대해서 중복되는 계산을 하게 되었고 2중배열로 변경

 

ACAYKP
CAPCAK

위 경우에 대해 보면

 

하나에 대해 중복되는 갯수를 먼저 구하게 되면 위와같이 된다.

 

첫 줄에서 A와 C는 0, A와 CA는 1개 그 이후로도 A가 중복된 갯수는 1개가 된다.

 

 

그 다음으로는 1,1위치의 값을 보면 C와 A는 같지 않기때문에 이전 값중 가장 큰 값을 가져오면 된다.

 

그 후 1,2지점을 보면, C값이 같다는 것은  "AC"와 "CAC"의 값중 중복되는 값이 2개 있다는 것이다. 여기서 마지막 C를 제외하면 A와 CA값이 1개가 같다는 것으로 이 값에서 1을 더해주면 된다.

따라서

 

A = input()
B = input()
 
check = [[0]*len(B) for i in range(len(A))]
 
check[0][0] = (A[0]==B[0])
for i in range(1, len(B)):
    if A[0] ==B[i] or check[0][i-1]:
        check[0][i] = 1
        
for i in range(1, len(A)):
    if A[i] ==B[0] or check[i-1][0]:
        check[i][0] = 1
 
for i in range(1,len(A)):
    for j in range(1,len(B)):
        if A[i] == B[j]:
            check[i][j] = check[i-1][j-1] + 1
        else:
            check[i][j] = check[i-1][j] if check[i-1][j] > check[i][j-1] else check[i][j-1]
 
print(check[-1][-1])