풀이
일전에 풀었던 LIS문제에서 사용한 방법을 응용해 풀이할 수 있다.
[백준 11053] 가장 긴 증가하는 부분 수열 [Python]
풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가
kyr-db.tistory.com
LDS (Longest Decreasing Subsequence) 라고 하더라도, 결국은 LIS와 동일하게 요소간의 차이가 항상 커지거나 작아지는 비연속 부분 수열을 찾으면 되기 때문이다.
다만 주의할 점이 있는데, LIS의 길이를 구할 때 처럼 1번 요소부터 N번 요소 방향으로 탐색을 진행하면 기록되는 LDS의 길이 또한 점점 증가한다는 점이다.
해당 문제를 풀이하는데 있어서 크게 중요한 부분은 아니지만, 비슷한 문제로 분류되는 LBS (Longest Bitonic Subsequence)의 길이를 구하는데 있어 예외 처리를 위해 중요한 부분이다.
[백준 11054] 가장 긴 바이토닉 부분 수열 [Python]
풀이 LIS문제의 원리를 잘 다룬 문제이다. 기존에 O(N^2) 방식으로 LIS를 구할 때, 비연속 LIS 길이를 찾을 수 있었다. [백준 11053] 가장 긴 증가하는 부분 수열 [Python] 풀이 LIS (Longest Increasing Subsequence)
kyr-db.tistory.com
즉, LDS의 길이를 구하는 좀 더 명확한 방법은 LIS 의 길이를 N번 요소부터 1번 요소 방향으로 탐색해 찾는다고 생각하면 편하다.
소스코드
출처
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 17863] FYI [Python] (0) | 2023.04.30 |
|---|---|
| [백준 11054] 가장 긴 바이토닉 부분 수열 [Python] (0) | 2023.04.29 |
| [백준 11053] 가장 긴 증가하는 부분 수열 [Python] (0) | 2023.04.29 |
| [백준 2407] 조합 [Python] (0) | 2023.04.27 |
| [백준 1167] 트리의 지름 [Python] (0) | 2023.04.25 |