[Python] 9251번 : LCS

 

 

문제 3줄 요약

1. 두 문자열이 주어진다.

2. 문제가 간단하구만?

3. 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾아라

 

 

 

문제 이름처럼

최장 공통 부분 수열을 구하는

LCS 알고리즘 문제이다!

 

 

LCS가 무엇인지 모른다면,

아래 링크를 참고하면 좋을 것 같다!

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=power2845&logNo=220677085876

[Python] LCS 알고리즘(Longest Common Subsequence)

 

짧게 설명 해본다면,

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=power2845&logNo=220677085876

 

위의 그림처럼,

두 수열의 부분열을 찾는데,

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=power2845&logNo=220677085876

 

부분열을 찾았을 때,

값을 증가시키며 사선으로 정답을 추적해나가는 알고리즘이다.

 

위 그림은 

"ABCDA", "ACBDEA"의 LCS 알고리즘 동작 그림이다.

 

 

위의 동작 과정을 코드로 표현하면,

문제의 답이 된다!

 

from sys import stdin

if __name__ == "__main__":
    str1 = stdin.readline().strip()
    str2 = stdin.readline().strip()

    LCS_list = []
    # LCS
    for x in range(len(str1)+1):
        LCS = []
        for y in range(len(str2)+1):
        
        # 첫줄 0으로 초기화
            if (x==0) or (y==0):
                LCS.append(0)
            
            # 부분열을 찾았을 경우
            elif str1[x-1] == str2[y-1]:
                LCS.append(LCS_list[x-1][y-1]+1)
            
            # 값이 다른 경우
            elif str1[x-1] != str2[y-1]:
                LCS.append(max(LCS_list[x-1][y], LCS[-1]))
        LCS_list.append(LCS)

    print(LCS_list[-1][-1])

 

끝