[백준/실버2] 11053번: 가장 긴 증가하는 부분 수열 (Python)

 

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

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

출력

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

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4

 

 

 

<풀이>

가장 단순한 방법은 완전 탐색이다.

전체 수열을 탐색하면서, 증가하는 부분수열을 저장하고, 이들의 길이를 비교해서 최댓값을 찾는 것이다.

하지만 이는 전체 수열의 크기가 커질 수록 매우 비효율적이다. 

 

🌱 DP를 이용한 풀이 : O(n^2)

앞에서 언급한 완전탐색방법을 DP로 최적화해보자.

 

가장 마지막 상태를 생각해보면,

부분수열의 마지막 숫자를 K라 했을 때, 앞 순서의 숫자들은 모두 K보다 작다.

DP테이블에 각각의 인덱스(i)에서 끝나는 최장 증가 수열 길이(LIS)를 저장하면, 마지막까지 탐색했을 때 최장 증가 수열 길이를 알 수 있다.

작성된 dp테이블에서 가장 큰 값이 답이다.

 

전체 수열을 탐색할 때,

1. 현재 인덱스의 값(arr[i])와 이전 인덱스에 있는 모든 값(arr[j])을 비교한다. 

2. arr[i] > arr[j] 이면, DP 테이블을 업데이트한다.

- 초기화: dp[i] = 1  => 해당 원소에서 끝나는 LIS 길이의 최솟값

-  arr[j]+1 => j에서 끝나는 LIS에 현재 수를 붙인 새 LIS 길이

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

 

코드

처음에는 직전 인덱스 값과 비교하는 것만 생각했다. 이는 연속 증가 수열을 구하는 것이므로, 문제의 의도와 맞지 않는다.

import sys
n  = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

dp = [1]*n #초기화
    
for i in range(1,len(arr)):
    for j in range(i):
        if (arr[j] < arr[i]):
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

 

 

 

참고: https://4legs-study.tistory.com/106