[PY] LCS [9251 : LCS 포함]

가장 긴 공통 문자열 찾기 문제

Longest Common Subsequences 문제에 대해 알아보자. 두 개의 문자열에서 공통적으로 존재하는 가장 긴 문자열을 찾는 문제이다.
생물학에서는 두 생명체의 DNA가 얼마나 유사한지를 판단 할 때 사용한다. 더 와닿는 LCS 사용 예제는, 두 문서의 공통점과 차이점을 찾을 때 사용 할 수 있다. (git diff)

ABCBDAB	BDCABA
두 문자열의 LCS는 BCBA이다.

뭐 BCAB나 BDAB 같이 길이 4인 LCS가 더 있다는 것을 찾을 수도 있다. 대부분의 문제는 길이를 기준으로 하니 실제로 어떤 것이 내용이냐? 에 관한건 깊이 논하지 않겠다. 길이는 항상 4로 같은 결과가 나와야겠지?

문제를 이해하기 위해 두 가지를 주의깊게 보도록 하자.

1. 공통 문자열이 모두 연결되어 있지 않아도 된다. 중간에 다른 글자가 끼어 있을 수 있다는 의미이다.
   예를 들어 왼쪽 문자열은 BCB 와 A 사이에 D가 끼어있다. D는 LCS에 포함되지 않았다.
   
   
2. 공통 문자열 중에서 가장 긴 것을 찾기 위해서 전략적으로 선택을 뒤로 미룰 수 있다. 예를 들어 왼쪽의 첫 글자인 A로 시작하는 공통 문자열은 ABA를 찾을 수 있지만 길이는 3이다. 반면에 두 번째 글자인 B에서 시작해서 찾을 수 있는 공통 문자열은 BCBA 이고 길이가 4라서 더 길다.

2025.04.03 - [별 잡다] - D P

D P

동적 프로그래밍을 적용하는 단계를 다시 생각해보자.

• 최적 하부 구조를 찾는다.
• 재귀 구조를 찾는다.
• 중복되는 작은 문제들을 재사용해서 효율을 높이기.

LCS 문제의 최적 하부 구조는 더 작은 문자열에 대해 LCS를 찾는 것이다. 이해를 돕기 위해 재귀 함수를 사용해서 표현해보겠다.

1. 둘 중 하나의 길이가 0인 문자열이 매개변수 두 개중 하나로 들어가면 결과는 0이다.
   1. LCS("", "ABC") = "", LCS("DEF", "") = ""
2. 마지막 글자가 일치 할 경우 겹치는 문자를 제외한 부분 문제로 분리 하게 된다.
   1. LCS("AAAB", "AAAAB") = LCS("AAA", "AAAA") + "B"
3. 마지막 글자가 일치하지 않을 경우, 2가지 경우로 분기를 시도한다.
   1. LCS(X, Y)는 LCS(X에서 마지막 한 글자 제외, Y)와 LCS(X, Y에서 마지막 한 글자 제외) 중에서 결과가 더 긴 것을 선택한다.
   2. 예를 들어, LCS("ABC", "ABCD)는 LCS("AB", "ABCD") 와 LCS("ABC", "ABC") 중에서 결과가 긴 것을 선택한다.

근데 이거 그대로 하면 O(2^(something))이다. 그야말로 개느리다.

그래서 Bottom-Up 형식을 사용하기로 했다.

• 입력을 받고 table을 입력 된 길이 만큼 정의한다.
• strA, strB의 지속적인 비교를 한다.
  • 현 글자가 일치하면 대각선쪽 데이터에서 긁어온다.
  • 그렇진 않은데, 테이블 상에서 [i - 1][j]가 [i][j - 1]보다 크면 해당 값을 긁어온다.
  • 그 반대라면 또 그 반대 선상에서 값을 긁어 온다.
•  

import sys
sys.setrecursionlimit(10**8)



stringA = input()
stringB = input()

def bottomUPLCS(strA, strB, lenA, lenB):
        table = [[0] * (lenB + 1) for _ in range(lenA + 1)]

        for i in range(1, lenA + 1):
                for j in range(1, lenB + 1):
                        if(strA[i - 1] == strB[j - 1]):
                                table[i][j] = table[i - 1][j - 1] + 1
                        elif table[i - 1][j] >= table[i][j - 1]:
                                table[i][j] = table[i - 1][j]
                        else:
                                table[i][j] = table[i][j - 1]

        return table[lenA][lenB]

result = bottomUPLCS(stringA, stringB, len(stringA), len(stringB))
print(str(result))

DP를 다루는데 있어 갈길이 멀다. 아주 많이..