반응형
11722
-
백준 11722번 - 가장 긴 감소하는 부분 수열 (LDS) 파이썬개발/알고리즘 2025. 3. 27. 18:11
📌 백준 11722번 - 가장 긴 감소하는 부분 수열 (LDS)✨ 문제 요약수열이 하나 주어졌을 때,그 수열에서 감소하는 부분 수열 중 가장 긴 길이를 구하는 문제입니다.🧠 문제 해석LIS(가장 긴 증가하는 부분 수열)와 반대 개념즉, 수열의 요소들이 점점 작아지는 방향으로 이어져야 함연속되지 않아도 되고, 순서만 지켜지면 됨🔧 점화식 설계dp[i] = i번째 원소를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이for i in range(N): for j in range(i): if arr[i] 🧱 DP 테이블 예시입력: arr = [10, 30, 10, 20, 10]i arr[i] dp[i] 의미 (i까지 고려했을 때 감소하는 수열 길이)0101 (처음 원소)1301 (증..