[BOJ/백준] 9252 LCS 2

# Longest Common Subsequence
#  최장 공통 부분 수열
def LCSlength(X,Y):
    for i in range(1,len(X)+1):
        for j in range(1,len(Y)+1):
            if X[i-1] == Y[j-1]:
                LCS_ARRAY[i][j] = LCS_ARRAY[i-1][j-1] + 1
            else:
                LCS_ARRAY[i][j] = max(LCS_ARRAY[i][j-1],LCS_ARRAY[i-1][j])
    
def findBackTrack(C,X,Y,i,j):
    if i == 0 or j == 0:
        return ''
    if X[i-1] == Y[j-1]:
        return findBackTrack(C,X,Y,i-1,j-1) + X[i-1]
    if C[i][j-1] > C[i-1][j]:
        return findBackTrack(C,X,Y,i,j-1)
    return findBackTrack(C,X,Y,i-1,j)




string_1 = list(input())
string_2 = list(input())
LCS_ARRAY = [[0]*(len(string_2)+1) for _ in range(len(string_1)+1)]
LCSlength(string_1,string_2)
result = findBackTrack(LCS_ARRAY,string_1,string_2,len(string_1),len(string_2))
print(len(result))
print(result)

이론에 대한 설명은 다른 사람들의 블로그에 더 자세히 설명되어있고,

 

저같은 경우 ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

위키를 참조하면서 풀었다.

 

LIS와 LCS같은 DP 문제들은 반복 숙달이 되지 않으면 실전에서 푸는게 어려워 보인다.

 

 

제가 이해한 기본적인 원리는 다음과 같다.  문자열 S1 과 문자열 S2가 있으면, 이 두 문자열의 길이만큼의 2차원 행렬을 만들어준다.

 

이 행렬은 두 문자열이 같은 문자열을 얼마나 가지고 있는지 판별이 되는 행렬이다. 이행렬의 이름을 LCS라 하고, 이 행렬의 크기는 (문자열 S1의 길이 +1) X (문자열 S2의 길이 +1)이 된다. 왜냐하면 아무것도 선택하지 않았을때를 초기화 해주는 부분이 있기 때문이다.

 

그리고 S1,S2를 기준으로 2중 for문을 돌려준다. 그러면서 s1과 s2에서 똑같은 문자열이 발견이 되면, 

LCS[i][j]에 = LCS[i-1][j-1] +1 을 해준다.

왜 대각선 성분에 있는걸 더해주는 이유는 똑같은 문자열이 발견되기 직전의 각각의 index에 존재하는 값이 해당 부분직전까지의 최대값이기 때문이다.

코드를 보면 좀 헷갈리는 이유는 S1,S2의 index는 0부터 시작하기 때문이다. s1,s2의 i,j index의 LCS의 길이값은 LCS의 i+1,j+1 index에 저장이 된다.

만약 같지 않을 경우, [i-1, j], [i,j-1] 둘중 큰 값을 넣어주면 된다.

 

 

이렇게 구한 LCS를 이용해서 역추적으로 최장 공통 부분수열을 구성 값을 구해준다.

이 방법은 단 1개를 구하는 것이므로, 다른 방법은 위의 위키를 참조하거나, 다른 사람 블로그를 참조하길 바란다.

 

백트래킹으로 찾는 방법인데, 각가의 끝 인덱스에서 시작해서 만약에 두 인덱스에서의 S1,S2의 값이 같으면, 그 부분을 결과에 return 시켜주고, 현재 index는 두 값이 같기 때문에, i-1,j-1위치에서 백트래킹을 해준다.

그리고 그 외에는 LCS의 길이가 변경되는 순간이 같은 문자열이 존재하는 구간이기 때문에, 

[i-1][j] 와 [j][j-1의 LCS의 길이를 비교해서 더 큰 곳으로 이동해서 계쏙 반복을 해준다.

 

 

이 이론에 대해서는 아직 제대로 공부를 안했기 때문에 미숙한 부분이 많고,

 

저보다 더 나은 설명을 한 블로그들이 많으니 그 블로그를 참조하는 것을 권장합니다.