[백준/python] DP 유형 - LIS & LDS 그리고 LCS

내용은 더 추가될 수 있습니다

---

 

LIS (Longest Increasing Subsequence)
LDS (Longest Decreasing Subsequence)

 

조건에 맞게 선택적으로 전진하는 DP

최장 감소 부분 수열 (LDS) 백준 #11722 가장 긴 감소하는 부분 수열 (길이) 최장 증가 부분 수열 (LIS) 백준 #11053 가장 긴 증가하는 부분 수열 (길이)

dp[i] = i번째 원소를 끝으로 하는 LIS 혹은 LDS 길이 Q. 아래 방법은 N^2 아닌가? 매번 탐색해야해서 말야.  A. N<=1000, O(N^2 = 10^6) <= 1초

#11053

 

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        n = len(nums)
        dp = [1]*n # init: 한자리 LIS

        for cur in range(1, n):
            for prev in range(cur):
                if nums[prev] < nums[cur]:
                    dp[cur] = max(dp[prev]+1, dp[cur])

        return max(dp)

 

백준 #12015 가장 긴 증가하는 부분 수열 2 (길이)

- 위 문제와 유사해보이지만, N<= 10^6, N^2 탐색 못함. 다른 방법이 필요함 - 이분탐색

 

 

LCS (Longest Common Subsequence)
LCS (Longest Common Substring)

 

String Matching

코드트리 #표절검사 LCS (Longest Common Subsequence, 최장 공통 부분 수열); 불연속 백준 #9252 (LCS 자체를 dp 값으로 가지면서 원리 이해하기 좋음) 백준 #9251 (LCS 길이만 관리)

비교값의 상태에 따라 분기된 점화식으로 정의될 수 있음

 

 

 

#9249 LCS (Longest Common Substring, 최장 공통 부분 문자열); 연속

TODO: 다시 풀어봐야함

[키워드 모음] - suffix array - Manber-Myers Algorithm - LCP (longest Common Prefix) [DP 문제들은?] "두 문자열 길이의 합은 20만을 넘지 않는다..."  이런걸 보면, A+B 로 풀라는 힌트인건가? 아무리 블로그 봐도 이해가 안되네.. 백준 #11656 접미사배열, #13013 접미사 배열2 이 문제들을 풀어봐야하나? 그런 문자열 관련 문제 모음 https://inner-game.tistory.com/380

 

 

기타

 

#16500 문자열 판별

- 점화식 아니어도, 완전 탐색으로도 접근할 수 있어야한다. - dp[i] = 문장 내 idx 위치를 끝으로 부분 단어를 포함하고 있다.