백준 9251번 - LCS (최장 공통 부분 수열)

 

각 문자열의 길이 + 1만큼의 2차원 배열을 선언해주고, 문자를 하나하나씩 비교하면서 최장 공통 부분수열의 길이를 구해야한다.

 

예제 입력을 예로 들면, 첫 번째 문자열의 앞 세글자 ACA와 두 번째 문자열의 앞 5글자 CAPCA를 비교해보면, 각 글자가 붙여지기 이전인 AC와 CAPC에 두 문자열에 모두 A가 붙여졌기 때문에, AC와 CAPC의 LCS에 1을 더한 값이 ACA와 CAPCA의 LCS일 것이다. 즉 하나하나 비교하면서, 같은 문자가 다음에 붙여진다면, 각 문자열의 이전 LCS값에 1을 더한 값이 LCS가 될 것이다.

 

반면에 ACAYKP와 CAPC를 예로 들면, 마지막 문자인 P와 C가 다르기 때문에, ACAYK와 CAP의 LCS에 1을 더하는 이전의 경우는 성립하지 않는다. 그러므로 각 문자열에서 하나씩 빠진 ACAYK와 CAPC, ACAYKP와 CAP의 LCS중에서 큰 값이 두 문자열의 LCS가 된다. ACAYK 다음에 P가 오는 경우엔, LCS의 값이 3인 반면에 CAP 다음에 C가 오는 경우는 LCS의 값이 2이기 때문이다. 조심해야 할 점은 다른 문자열이 온다고 해서 LCS의 값이 이전 시행의 값과 동일하다고 할 수 없다는 것이다.

##변수 선언 부분##
st1 = []
st2 = []
dp = []
##메인 함수 부분##
if __name__ == "__main__":
    st1 = input()
    st2 = input()
    dp = [[0]*(len(st1)+1) for x in range(len(st2)+1)]

    for i in range(1,len(st2)+1): #각 st1의 알파벳에 따른 st2의 알파벳을 비교해야하기 때문에
        for j in range(1,len(st1)+1): #st2에 대한 반복문 안에 st1에 대한 반복문을 넣어준다.
            if st2[i-1] == st1[j-1]: #같은 알파벳이면,
                dp[i][j] = dp[i-1][j-1] + 1 #이전 값에 1을 더한 값을 넣어준다.
            else: #다른 알파벳이면,
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]) #행에 대해 이전 값과 열에 대해 이전 값 중에서 큰 값을 넣어준다.

    print(dp[-1][-1])

    for i in range(len(st2)+1):
        for j in range(len(st1)+1):
            print(dp[i][j],end=" ")
        print("")

 처음에는 인덱스를 이용해서 한 문자열을 가지고 다른 문자열과 비교하는 방식으로 구해보려고 했지만, 딱히 LCS를 구하는 데 인덱스는 연관이 없어 보였다. LCS 알고리즘이 어떤 것인지를 훑어보고 문제를 풀었다. 다음에 오는 문자가 같은 경우에 dp[i][j]=dp[i-1][j-1]+1의 시행을 이해하는 데 시간이 좀 걸렸다. 

 

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