Longest Common Subsequence

LeetCode - The World's Leading Online Programming Learning Platform

문제 파악 [필수 작성]

문제이해

일부 글자를 빼서 같아질 수 있는 가장 긴 부분글자순열
아예 없으면 0 리턴

제한 조건 확인

두 문자열 각 길이 최대 1000 = 10^3

아이디어

30분 고민해봤는데 모르겠어서 해설 아이디어 참고 후 직접 구현
top-down 방식
text1 과 text2 맨 첫번째 글자 비교하는데
다르면, 위에꺼 하나 전진한거랑 text2 또는
밑에꺼 하나 전진한거랑 text1 두개 비교해서
더 큰값 리턴하는걸로 업데이트
같으면, 두개다 하나씩 전진해서 그 다음 소문제 비교

시간복잡도

최대 O(n^2)

자료구조

접근 방법 [필수 작성]

자유 형식

코드 구현 [필수 작성]

1차 시도

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = set()
        def lcs(t1,t2,tmp_len):
            if (t1,t2,tmp_len) in cache:
                return 0
            else:
                cache.add((t1,t2,tmp_len))
                if len(t1) == 0 or len(t2) == 0:
                    return tmp_len
                elif t1[0] == t2[0]:
                    return lcs(t1[1:],t2[1:],tmp_len+1)
                else:
                    return max(lcs(t1[1:],t2,tmp_len),lcs(t1,t2[1:],tmp_len))

        return lcs(text1,text2,0)
        

2차 시도

문자열을 set 에 넣어주는걸 포인터를 넣어주는걸로 변경

여전히 동일한 메모리 에러 발생

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = set()
        def lcs(p1,p2,tmp_len):
            if (p1,p2,tmp_len) in cache:
                #print("true")
                return 0
            else:
                cache.add((p1,p2,tmp_len))
                if p1 == len(text1) or p2 == len(text2):
                    return tmp_len
                elif text1[p1] == text2[p2]:
                    return lcs(p1+1,p2+1,tmp_len+1)
                else:
                    return max(lcs(p1+1,p2,tmp_len),lcs(p1,p2+1,tmp_len))

        return lcs(0,0,0)

3차 시도

갈아없고 해설 아이디어 빌린 Bottom-Up 방식 직접 구현

'''
dp_table 초기화 0번째 row 와 col 은 0 으로 초기화
i,j 가 다르면, i-1,j 와 i,j-1 중 최대값 저장
i,j 가 같으면 i-1,j-1 에서 +1 해서 저장
'''

#Bottom-Up
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp_table = [[0 for _ in range(len(text1)+1)] \
                    for _ in range(len(text2)+1)]
        for row in range(1,len(dp_table)):
            for col in range(1,len(dp_table[0])):
                if text1[col-1] == text2[row-1]:
                    dp_table[row][col] = dp_table[row-1][col-1] + 1
                else:
                    dp_table[row][col] = \
                    max(dp_table[row][col-1],dp_table[row-1][col])
        return dp_table[-1][-1]

4차 시도

from collections import defaultdict
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = defaultdict(int)
        def lcs(p1,p2):
            if p1 == len(text1) or p2 == len(text2):
                return 0
            else:
                if text1[p1] == text2[p2]:
                    return lcs(p1+1,p2+1) + 1
                else:
                    return max(lcs(p1+1,p2),lcs(p2+1,p2))

        return lcs(0,0)

5차 시도

from collections import defaultdict
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = defaultdict(int)
        def lcs(p1,p2,tmp_cnt):
            if cache[(p1,p2)] > tmp_cnt:
                return 0
            else:
                cache[(p1,p2)] = tmp_cnt
                if p1 == len(text1) or p2 == len(text2):
                    return 0
                else:
                    if text1[p1] == text2[p2]:
                        return lcs(p1+1,p2+1,tmp_cnt+1) + 1
                    else:
                        return max(lcs(p1+1,p2,tmp_cnt),lcs(p1,p2+1,tmp_cnt))

        return lcs(0,0,0)

배우게 된 점 [필수 작성]

자유 형식

질문 [ 필수 X ]

Q1. Top-Down 방식 코드 구현 방법

2차시도, 3차시도, 5차시도 코드가 top-down 방식의 코드 구현인데, 2차의 경우 통과해야한다고 생각하는데 메모리 초과가 납니다.

혹시 top-down 방식을 어떻게 구현할 수 있는지 궁금하고, 메모리 초과는 코드 제출 전에 어떻게 예상하고 검증할 수 있는지 궁금합니다.

Q2.(추가질문)

해설강의에서는 top down 방식으로 구현할 수 있는 것처럼 설명이 되어있는데
그럼 Top down 방식으로는 풀 수 없는 유형의 문제인가요?

답변

set, dict의 경우 해시값을 저장한다는 특성과 key-value 페어를 저장한다는 특성에 의해 같은 길이의 리스트보다 메모리를 더 크게 차지하게 됩니다. 그렇기에 1000*1000의 사이즈를 가질 수 있는 해당 문제에서 set, dict등의 자료구조로 top-down을 구현할 때 메모리 초과가 발생하게 됩니다. 다음 링크를 참고하시기 바랍니다.

https://stackoverflow.com/questions/39914266/memory-consumption-of-a-list-and-set-in-python

추가질문 답변

top down방식으로 구현할 수 있습니다 단지 set, dict 자료형을 통해 구현할 수 없을 뿐입니다. 1000*1000크기의 이차원 리스트를 통해 구현한다면 메모리 초과가 발생하지 않으며 top down방식으로 구현할 수 있습니다.