def lcs_length(s1: str, s2: str) -> int:
"""
s1, s2 의 가장 긴 공통 부분수열의 길이를 반환.
어느 한쪽이라도 비어 있으면 0 을 반환합니다.
"""
if s1 == "" or s2 == "": return 0
arr = [[0 for _ in range(len(s1))] for idx in range(len(s2))]
for idx in range(len(s2)):
for jdx in range(len(s1)):
if idx == 0 and jdx == 0:
if s2[idx] == s1[jdx]: arr[idx][jdx] = 1
elif idx == 0:
if s2[idx] == s1[jdx]:
arr[idx][jdx] = 1
else:
arr[idx][jdx] = arr[idx][jdx - 1]
elif jdx == 0:
if s2[idx] == s1[jdx]:
arr[idx][jdx] = 1
else:
arr[idx][jdx] = arr[idx - 1][jdx]
else:
if s2[idx] == s1[jdx]:
arr[idx][jdx] = arr[idx - 1][jdx - 1] + 1
else:
arr[idx][jdx] = max(arr[idx - 1][jdx], arr[idx][jdx - 1])
return arr[-1][-1]
if __name__ == "__main__":
print("[테스트 1] 한쪽이 빈 문자열")
print(f' s1="", s2="abc" -> LCS 길이={lcs_length("", "abc")}')
print()
print("[테스트 2] 두 문자열이 동일")
print(f' s1="abc", s2="abc" -> LCS 길이={lcs_length("abc", "abc")}')
print()
print("[테스트 3] 공통 원소가 전혀 없음")
print(f' s1="abc", s2="xyz" -> LCS 길이={lcs_length("abc", "xyz")}')
print()
print("[테스트 4] 표준 예시 1")
print(f' s1="abcde", s2="ace" -> LCS 길이={lcs_length("abcde", "ace")}')
print()
print("[테스트 5] 표준 예시 2")
print(f' s1="AGGTAB", s2="GXTXAYB" -> LCS 길이={lcs_length("AGGTAB", "GXTXAYB")}')
print()
print("[테스트 6] 두 LCS 후보가 길이가 같은 경우")
print(f' s1="ABCBDAB", s2="BDCABA" -> LCS 길이={lcs_length("ABCBDAB", "BDCABA")}')
부분 수열이란
주어진 수열에서 일부 항을 골라내어 원래의 순서대로 나열하여 만든 새로운 수열
지금 위 코드에서는 만들어질 수 있는 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열 수열이라한다. 거기서 입력으로 들어올 2 문장에 대하여 공통인 것을 뽑는다.
위를 설명하면 각 두 문자열 S1과 S2를 기준으로 한쪽은 행, 한쪽은 열 값을 갖게 된다.
이후 행과 열 혹은 행 또는 열이 0인 경우를 따로 분류하여 처리한다. 그러면 기본 상태가 만들어지고 이후 진행하게 되는데 비교는 만약 두 문자열이 같다면 대각선 위와 비교하여 1을 추가하고 같지 않다면 위 혹은 왼쪽 옆의 값 중 최대값을 뽑아오게 된다.
이렇게 뽑는 이유는 각 행과 각 열의 요소가 갖는 의미이기 때문이다.
결론적으로는 이전의 최대값을 의도적으로 심판대에 올리는 행위이고 그 값을 지금의 내가 선택하냐 마냐를 이번 단계의 일치로 평가하는 것이기 때문이다.
그렇기 때문에 마지막 배열의 끝 값을 가져오는 것도 결론적으로는 끝까지 다 봤을 때 내가 선택한 값은 이거다 인 값을 가져온다고 생각한다.
