[백준][Python] 1958 LCS 3

 

 

 

알고리즘 종류

    - 문자열

 

 

 

사고 과정

    - LCS이 뭐지? Longest Common Subsequence에서 subsequence의 뜻은 연속되지 않은 문자열이다. 즉, 문자열이 연속되지 않아도 공통되는 것 중에 가장 긴 것을 찾으면 된다. 아래에 subsequence와 substring을 비교한 예시가 있다.

 

    - 문자열 내의 모든 문자를 방문하면서 비교해야 한다. 비교하는 과정에 같은 문자를 찾았다면 어떻게 저장하고 숫자를 기록할까? 이 부분에 대해서 정형화된 방법이 있을 것 같아서 찾아보니 LCS 알고리즘이 있었다. (이 문제 자체가 LCS 알고리즘을 묻는 문제였다) 방법은 DP를 이용해서 저장하고 최대 공통 문자열의 길이를 기록한다. 본인은 이 블로그에서 시각적인 정보를 참고하여 이해할 수 있었다.

 

 

 

구현(C++)

# 문자열 입력 받는다.
s1, s2, s3 = input(), input(), input()
 
# DP를 사용할 3차원 matrix를 만든다.
# +1를 해서 만드는 이유는, 이전 기록을 가져와서 현재 기록을 갱신하기 위해서 이다.
dp = [[[0]*(len(s3)+1) for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
 
for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        for k in range(1, len(s3)+1):
            # 검사하는 문자들이 같다면
            if(s1[i-1] == s2[j-1] == s3[k-1]):
                # metrix에서 i-1, j-1, k-1에 있는 이전까지 기록된 최장 길이 값에 +1을 해서
                # 현재 i, j, k 위치에 넣어준다.
                dp[i][j][k] = dp[i-1][j-1][k-1]+1
            else:
                # 일치하지 않다면, i-1 위치, j-1 위치, k-1 위치에 있는 최장 길이들 중에
                # 가장 긴 값을 가져온다.
                dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
                
# matrix의 끝에 최장 길이의 값이 저장되게 된다. 가져온다.
print(dp[-1][-1][-1])
 

 

 

 

시행착오

    - 문자열 알고리즘은 다루어 본 적이 없어서 생소하다. Python으로 코딩하는 것도 생소하다. 하나 하나 배워 가야겠다.