철학하는 개발자

있는 것은 있고, 없는 것은 없다.

PS/Code Tree

[Code Tree] 최대 증가 부분 수열 [Python]

kimyoungrok 2025. 7. 1. 19:51
728x90

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-longest-increasing-subsequence/description


풀이

문제 요약

주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하자.

아이디어

LIS를 구하는 가장 기본적인 문제다.

점화식은 다음과 같다.

dp[i] : i번째 요소로 끝나는 LIS의 최대 길이

현재 위치 i에 대해 이전 위치 0 ~ i - 1 중 현재 위치의 값 m[i]]보다 작고, 지금까지 구한 LIS보다 dp[j] + 1이 더 긴 LIS가 된다면 다음이 성립한다.

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

n = int(input())
m = list(map(int, input().split()))

# Please write your code here.

dp = [1] * n

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

print(max(dp))

풀이시간

5분


소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Algorithm Intro/DP I/13 최대 증가 부분 수열(intro-longest-increasing-subsequence).py

728x90