Longest Common Subsequence

백준 9251번 문제

LCS(최장 공통 부분수열)

 

ACAYKP

CAPCAK

 

와 같이 입력이 주어지면

 

A C A Y K P

C A P C A K

 

=> ACAK가 모두의 부분수열이 되는 수열 중 가장 긴 것이 된다.

 

<소스코드>

# 9251_LCS.py

s1 = input()

s2 = input()

 

len_a = len(s1)

len_b = len(s2)

 

lcs_list = [[0 for i in range(len_a+1)] for j in range(len_b+1)]

count = 0

 

for i in range(1,len_b+1):

    for j in range(1,len_a+1):

        if s2[i-1] == s1[j-1]:

            lcs_list[i][j] = lcs_list[i-1][j-1] + 1

        else:

            lcs_list[i][j] = max(lcs_list[i-1][j], lcs_list[i][j-1])

            

for i in range(len_b,0,-1):

    for j in range(len_a,0,-1):

        if lcs_list[i-1][j] == lcs_list[i][j-1] == lcs_list[i][j]:

            break

        elif lcs_list[i-1][j] == lcs_list[i][j-1]:

            count += 1

            break

        else:

            continue

print(count)

 

저는 

[

[0, 0, 0, 0, 0, 0, 0], 

[0, 0, 1, 1, 1, 1, 1], 

[0, 1, 1, 2, 2, 2, 2], 

[0, 1, 1, 2, 2, 2, 3], 

[0, 1, 2, 2, 2, 2, 3], 

[0, 1, 2, 3, 3, 3, 3], 

[0, 1, 2, 3, 3, 4, 4]]

와 같이 배열을 만들어 최장거리를 저장을 하였는데요

다른분들 코드를 보니 1열짜리 배열만 만들고 최대값을 담을 변수만을 이욯해서 짰더라구요ㅠ

아직은 부족함이 많이 느껴지네요. 분발해야겠어요!

 

여기 글쓰면서 생각해낸건데

제가 구했던 lcs_list의 max값의 max을 해도 같은 결과값이 나오는걸 알 수 있었어요.

아래가 위에 첨부된 소스코드고, 위에는 max(max(list))만 했는 코드입니당

그렇다고 크게 나아진 것 같진 않지만 이런것도 가능하단게 신기할 따름이에요.