[파이썬(Python)] 백준 11722번 가장 긴 감소하는 부분 수열

 

 

백준 11722번: 가장 긴 감소하는 부분 수열

문제 바로 가기

---

📌 문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

 

 

 

 

 

 

 

 

 

 

📝 아이디어

 

 

문제 분석

 

이 문제는 주어진 수열 $A$에서 가장 긴 감소하는 부분 수열(LDS, Longest Decreasing Subsequence)의 길이를 찾는 것입니다.

 

부분 수열이란 원래 수열에서 순서를 유지하면서 일부 원소만 선택하여 만든 새로운 수열을 말합니다. 예를 들어, 수열 $A = \{ 10, 30, 10, 20, 20, 10 \}$가 주어졌을 때 $\{ 10, 30, 10 \}$은 $A$의 부분 수열입니다.

 

 

감소하는 부분 수열은 이러한 부분 수열 중에서도 왼쪽에서 오른쪽으로 진행할 때 다음 숫자가 반드시 이전 숫자보다 작아야 하는 수열을 의미합니다. 예를 들어, $A = \{10, 30, 10, 20, 20, 10\}$에서 $\{30, 20, 10\}$이 감소하는 부분 수열이 됩니다. 반면 $\{30, 10, 20\}$은 부분 수열이지만 감소하는 조건을 만족하지 않으므로 감소하는 부분 수열로 볼 수 없습니다. 

 

 

이 문제의 목표는 주어진 수열에서 이러한 감소 조건을 만족하는 가장 긴 부분 수열의 길이를 구하는 것입니다. 

 

 

 

 

 

 

 

알고리즘: 다이나믹 프로그래밍(DP)

 

이 문제는 다이나믹 프로그래밍을 사용하여 효율적으로 해결할 수 있습니다. DP를 사용하는 이유는 다음 두 가지 성질을 만족하기 때문입니다.

 

 

 

1. 최적 부분 구조

 

최적 부분 구조란 문제를 작은 하위 문제로 나누어 해결한 결과를 조합하여 전체 문제를 해결할 수 있는 성질을 의미합니다. 

 

이 문제에서는 $dp[i]$를 수열 $A$에서 $A[i]$를 마지막 원소로 포함하는 가장 긴 감소하는 부분 수열의 길이라고 정의합니다. 이를 기반으로 $dp[i]$는 $A[i]$ 이전의 모든 원소 중 $A[j] > A[i]$를 만족하는 원소의 결과 $dp[j]$를 사용해 계산할 수 있습니다. 

 

 

 

 

 

2. 중복되는 부분 문제

 

중복되는 부분 문제란, 동일한 하위 문제를 반복적으로 해결해야 하는 상황을 의미합니다.

 

$dp[i]$를 계산하기 위해 $j < i$인 모든 $dp[j]$를 탐색합니다. $i$가 커질수록 $j$의 탐색 범위가 겹치게 되므로 동일한 계산이 반복됩니다. 이를 해결하기 위해 다이나믹 프로그래밍에서는 이전에 계산한 결과를 메모이제이션 또는 타뷸레이션을 통해 재사용합니다. 이를 통해 불필요한 계산을 줄이고 시간 복잡도를 효과적으로 감소시킬 수 있습니다. 

 

 

 

 

 

 

 

접근 방법

 

1. DP 배열 정의

 

$dp[i]$를 수열 $A$에서 $A[i]$를 마지막 원소로 포함하는 가장 긴 감소하는 부분 수열의 길이라고 정의합니다. 

 

 

예를 들어 $A = {10, 30, 10, 20, 20, 10}$일 때 

• $dp[0] = 1$: 원소 $A[0] = 10$만으로 길이 1의 감소하는 부분 수열을 이룰 수 있습니다.
• $dp[2] = 2$: $A[2] = 10$을 마지막으로 포함하는 감소하는 부분 수열을 $\{ 30, 10 \}$으로 길이는 2입니다. 

 

 

DP 배열의 각 원소 $dp[i]$는 해당 위치까지의 최적의 답을 저장하며 이를 조합하여 전체 문제의 최적 해를 구합니다.

 

 

 

 

 

2. 초기화

 

모든 원소는 최소한 자기 자신만으로 길이 1의 감소하는 부분 수열을 이룰 수 있으므로 DP 배열을 $dp[i] =1$로 초기화합니다. 

 

 

 

 

 

3. 점화식 

 

$dp[i]$는 $A[i]$ 이전에 등장한 $A[j] \quad (j < i)$ 중에서 $A[j] > A[i]$를 만족하는 원소를 찾아 가장 긴 감소하는 부분 수열을 확장한 결과로 계산됩니다. 

 

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

 

• $j < i$: $A[j]$는 $A[i]$보다 앞에 있어야 합니다.
• $A[j] > A[i]$: $A[j]$가 $A[i]$보다 커야 감소하는 부분 수열로 확장할 수 있습니다. 
• $dp[j] + 1$: $dp[j]$는 $A[j]$까지의 가장 긴 감소하는 부분 수열의 길이이므로 $A[i]$를 추가하면 길이가 1 늘어납니다. 

 

 

 

 

 

4. 최종 결과

 

DP 배열을 모두 계산한 후 배열에서 가장 큰 값이 가장 긴 감소하는 부분 수열의 길이가 됩니다.

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

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

dp = [1] * n

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

print(max(dp))