철학하는 개발자

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

Longest Increasing Subsequence 3

[Code Tree] 증가했다가 감소하는 부분 수열 [Python]

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-increasing-and-descreasing-subsequence/description 증가했다가 감소하는 부분 수열 설명 | 코드트리증가했다가 감소하는 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약가장 긴 LIS + LDS를 구하자.아이디어LIS와 LDS를 동시에 구해주자.점화식은 다음과 같다.dp[state][i] : i번째 요소로 끝나는 LIS 또는 LDS의 최대 길이LIS, LDS를 비교하며 최댓값을 LDS에 기록해 하나의 부분 수열에 대한 최대 길이로 계산하자...

PS/Code Tree 16:13:28

[Code Tree] 최대 감소 부분 수열 [Python]

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-longest-decreasing-subsequence/description 최대 감소 부분 수열 설명 | 코드트리최대 감소 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 수열에서 가장 긴 감소하는 부분 수열의 길이를 구하자.아이디어점화식은 다음과 같다.dp[i] : i번째 요소로 끝나는 LDS의 최대 길이LIS의 응용문제다. 부등호만 바꾸면 된다.n = int(input())m = list(map(int, input().split()))# Please write yo..

PS/Code Tree 2025.07.02

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

문제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()))# Ple..

PS/Code Tree 2025.07.01