[Algorithm] 감소하는 부분 수열

0. 문제

 

link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-lis-2/description

코드트리

유료 사이트여서 누구나 접근할 수는 없지만, 자료구조 개념을 정리하기 유용하다. 코딩 테스트, cs 면접을 준비한다면 추천한다. 

 

부분 수열이란, 간단히 말하자면 모든 원소의 부분집합을 만들되, 원소의 순서를 지키는 것을 의미한다.

예를 들면, [10, 30, 50, 40] 에서 [10, 30]은 부분 수열이지만 [10, 30, 40]은 부분 수열이 아니다.

감소하는 부분 수열은 부분 수열 중 원소들이 감소하고 있는 것을 의미한다.

우리는 주어진 수열 중 가장 긴 감소하는 부분 수열의 길이를 구할 것이다.

 

1. 풀이

 

왜 동적 계획법 문제인가? 다른 말로 하면 이를 어떻게 쪼갤 수 있는가?

개인적으로 dp 문제의 핵심은 나를 선택하느냐 선택하지 않느냐에 있다고 본다(사견입니다).

dp[i]를 i번째까지의 가장 긴 감소하는 부분 수열의 길이라고 할 때, i번째에서 고민할 것은 나를 선택해서 수열을 만드느냐, 그렇지 않느냐이다.

i번째를 선택한다면 i-1번째까지의 최장 길이 부분 수열에 1을 더한 것이 dp[i]의 값이 될 것이고, 그렇지 않다면 dp[i]를 그대로 유지할 것이다. 이 중 최대를 구한다면 i번째까지의 최장 길이의 감소하는 부분 수열을 구할 수 있다. 

이를 점화식으로 표현하면 다음과 같다.

 

dp[i] = max(dp[j] + 1, dp[i]) for j  in range(i)

 

2. 구현

 

num = input()
nums = num.split()
n = len(nums)
dp = [1 for _ in range(n)]

for i in range(n):
    nums[i] = (int)(nums[i])

for i in range(n):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[j] + 1, dp[i])

print(dp)

dp를 1로 초기화하는 것은 i번째부터 시작하면 수열의 길이는 1이 되기 때문이다.