DP2D: 1143. Longest Common Subsequence

문제 링크 : 1143. Longest Common Subsequence

 

https://youtu.be/Ua0GhsJSlWM?si=-h73SwkVPoCVziy6

 

 

코드 

 

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for j in range(len(text2)+1)] for i in range(len(text1)+1)]

        for i in range(len(text1)-1, -1, -1):
            for j in range(len(text2)-1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i+1][j+1]
                else:
                    # (max(right position, down position))
                    dp[i][j] = max(dp[i][j+1], dp[i+1][j]) 
        
        return dp[0][0]

 

=========================================================

 

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        
        # DP 테이블 초기화 (0으로 채움)
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # dp = [[0]*(n+1)]*(m+1)
        
        # DP 테이블 채우기
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:  # 문자가 같을 때
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:  # 문자가 다를 때
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        # 최장 공통 부분 수열 길이 반환
        return dp[m][n]

 

# DP 테이블 초기화 시  (0으로 채움)

dp = [[0] * (n + 1) for _ in range(m + 1)] : **깊은 복사(deep copy)**

 

대신에,

dp = [[0]*(n+1)]*(m+1) : **얕은 복사(shallow copy)**

 

사용하면 안되는 이유

 

 

따라서, 

# DP 테이블 초기화 시  (0으로 채움)

dp = [[0] * (n + 1) for _ in range(m + 1)] : **깊은 복사(deep copy)**

 

를 사용해야 함.

 

그냥 풀림

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 가장 긴 공통 수열 -> 길이 반환
        len1 = len(text1)
        len2 = len(text2)

        dp = [[0] * (len2+1) for _ in range(len1+1)] # 길이는 1부터 시작이므로.. +1 해서 계산 쉽게

        for i in range(1, len1+1):
            for j in range(1, len2+1):
                # 문자가 같으면 이전값 갖고옴. 주의: 문자열 idx 는 0부터 시작하므로 -1 해줘야함
                if text1[i-1] == text2[j-1]: 
                    dp[i][j] = dp[i-1][j-1] + 1 # +1 은 현재껏도 포함해야하니깐, 1 늘려 줌
                else: # 문자가 다르면
                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
                
        return dp[-1][-1] # dp[len1][len2]

 

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 가장 긴 공통 서브 순열
        ROWS, COLS = len(text1), len(text2)

        dp = [[0] * (COLS+1) for _ in range(ROWS+1)]

        for r in range(1, ROWS+1):
            for c in range(1, COLS+1):
                if text1[r-1] == text2[c-1]: # 문자가 같을때
                    dp[r][c] = dp[r-1][c-1] + 1
                else: # 문자가 다를때
                    dp[r][c] = max(dp[r-1][c], dp[r][c-1])

        return dp[ROWS][COLS]