7.4

main.py

"""
문제 : 최장 공통 부누 수열 (Longest Common Subsequence)

- 두 문자열 (str1, str2)가 주어졌을 때 해당 두 문자열의 최장 공통 수열의 길이를 반환하라.
- 이 문제에서 언급하는 부분 수열은 연속적이지 않으나 순서대로 나열 될 수 있는 문자열을 말한다.
- 예를 들어서 'abcde' 라는 문자열에서 부분 수열을 'abc', 'ace', 'aed' 등 각 문자의 순서를 지킨 모든 부분 문자열을 말한다.

### 아이디어 (Brute-Force)

1 str1의 인덱스 i, str2의 인덱스 j를 0으로 초기화 한다.
2. 재귀 함수를 호출한다.
  - i 혹은 j가 각 문자열의 접근 인덱스를 넘어섰다면 0을 반환한다.
  - str1[i]와 str2[j]가 같다면, i + 1, j + 1을 인자로 재귀 호출한다. (문자가 같기 때문에 1을 더해준다.)
  - 같지 않다면, i + 1, j 조합으로, i, j + 1의 조합으로 재귀 호출하여 최종 큰 값을 선택 및 반환한다.

### 아이디어 (동적 프로그래밍 - Top Down)
1. dp[n][m]을 -1으로 초기화 한다.
2. dp[i][j]가 -1이 아니면 해당 값을 반환한다.
3. 전체 탐색에서 각 재귀 호출의 반환을 dp[i][j]에 저장한다.

### 아이디어 (동적 프로그래밍 - Bottom Up)

1. dp[n][m]을 할당하여 -1로 초기화한다.
2. n만큼 순회한다(i)
  - m 만큼 순회한다.
  - str1[i]와 str2[j]가 같다면 dp[i][j]에 dp[i - 1][j - 1] + 1을 더 해준다.
  - 같지 않다면, dp[i - 1][j]과 dp[i][j - 1] 중 큰 값을 dp[i][j]에 업데이트 한다.
3. dp[n - 1][m - 1]을 반환 한다.
"""


# BRUTE-FORCE
def lcs(str1: str, str2: str) -> int:
    def lsc_recur(i, j):
        nonlocal str1, str2

        if i >= len(str1) or j >= len(str2):
            return 0

        if str1[i] == str[j]:
            return 1 + lsc_recur(i + 1, j + 1)
        else:
            return max(lsc_recur(i + 1, j), lsc_recur(i, j + 1))

    return lsc_recur(0, 0)


# TOP DOWN
def lcs2(str1: str, str2: str) -> int:
    dp = [[-1 for _ in range(len(str2) + 1)]
          for _ in range(len(str1) + 1)]

    def lsc_recur(i, j):
        nonlocal str1, str2, dp

        if i >= len(str1) or j >= len(str2):
            return 0

        if dp[i][j] != -1:
            return dp[i][j]

        if str1[i] == str2[j]:
            dp[i][j] = 1 + lsc_recur(i + 1, j + 1)
        else:
            dp[i][j] = max(lsc_recur(i + 1, j),
                           lsc_recur(i, j + 1))
        return dp[i][j]

    return lsc_recur(0, 0)


# BOTTOM UP
def lcs3(str1: str, str2: str) -> int:
    n = len(str1)
    m = len(str2)

    dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]

    for i in range(m + 1):
        dp[0][i] = 0

    for j in range(n + 1):
        dp[j][0] = 0

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

if __name__ == "__main__":
    str1 = input()
    str2 = input()
    print(lcs3(str1, str2))