LDS(최장 감소 부분 수열)

왜 확장이 필요한가?

기본 LIS(최장 증가 부분 수열)는

단조 증가하는 수열 하나만 고려합니다.

 

하지만 실전 문제에서는 다음과 같은 유형도 등장합니다:

• LDS (Longest Decreasing Subsequence) – 감소하는 수열
• Bitonic (이중 수열) – 증가했다가 감소하는 수열
• Double LIS – 앞에서 LIS, 뒤에서 LIS 또는 LDS 등
• 양방향 접근 문제 – 양쪽에서 동시에 LIS/LDS 계산

---

최장 감소 부분 수열 (LDS)

정의: LSD는 원소들이 점점 작아지는 부분 수열 중 가장 긴 것을 의미합니다.

 

예시:

arr = [5, 3, 4, 8, 6, 7]
→ LDS: [5, 4] or [8, 6] → 길이 = 2

 

핵심: LIS와 구조가 거의 동일, 단 부등호 방향만 반대입니다.

---

Python 코드 (O(n²))

def lds_dp(arr):
    n = len(arr)
    dp = [1] * n

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

    return max(dp)

 

arr[ j ] < arr[ i ] → arr[ j ] > arr[ i ] 로만 바뀌면 끝

 

---

Python 코드 (이분 탐색 방식, O(n log n))

이 경우, 입력을 반대로 뒤집고 LIS 구하기 방식으로 처리하면 동일합니다.

def lds_binary(arr):
    reversed_arr = [-x for x in arr]
    return lis_binary(reversed_arr)

 

---

바이토닉 수열(Bitonic Sequence): 증가 후 감소

어떤 i를 기준으로 앞에서는 LIS, 뒤에서는 LDS인 구간을 찾아야합니다.

 

arr = [1, 5, 2, 1, 4, 3, 2]
→ LIS: [1, 5]
→ LDS: [5, 4, 3, 2]
→ 최장 Bitonic 길이 = 5

 

알고리즘 핵심

• dp1[ i ] : 왼쪽부터 LIS (i를 끝으로 하는 증가 수열)
• dp2[ i ] : 오른쪽부터 LIS (i를 시작으로 하는 감소 수열)

비트닉 길이 = dp1[ i ] + dp2[ i ] -1

중복된 i 요소는 한 번만 카운트해야 하므로 -1 필요

 

Python 구현

def longest_bitonic(arr):
    n = len(arr)
    inc = [1] * n
    dec = [1] * n

    # 증가 부분 수열
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                inc[i] = max(inc[i], inc[j] + 1)

    # 감소 부분 수열 (뒤에서부터 LIS)
    for i in reversed(range(n)):
        for j in range(i + 1, n):
            if arr[j] < arr[i]:
                dec[i] = max(dec[i], dec[j] + 1)

    return max(inc[i] + dec[i] - 1 for i in range(n))

---

LIS & LDS 동시 사용 유형

유형	설명	해결 방식
LIS + LIS (앞/뒤)	연결되는 쌍 찾기	dp1[i] + dp2[i] - 1
LIS + LDS	바이토닉 문제	위와 동일
LIS → 역추적 → LIS 만들기	실제 수열 출력	prev[] 저장
LIS 길이 유지하며 변경	편집 최소 횟수 문제	dp[i] - 1 차이

---

요약

개념	설명
LDS	감소하는 부분 수열, LIS와 구조 동일 (부등호만 반대)
Bitonic	증가 후 감소 수열 → LIS + LDS를 하나로 결합
중복 카운트 제거	dp1[i] + dp2[i] - 1 사용
시간복잡도	기본 DP는 O(n²), 이분 탐색은 O(n log n) 가능