다이나믹 프로그래밍5

#11503 가장 긴 수열 https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

아 왜 DP에 적응을 못하는 느낌이 들까?

 

DP의 핵심과제는 이전에 연산한 값을 재사용함으로써 효율을 높이는 것이다.

그러니까, 항상 이전 항을 불러와서 +나 - 등을 하는 코드가 필요하다.

또, 리스트에 저장되는 값을 잘 정의하는 것도 중요하다.

이걸 잘 못 한다는 느낌이...

 

위 문제는 주어진 수열의 부분수열 중 가장 긴 증가하는 수열을 찾는 것이다.

증가하는 가장 긴 부분수열 (Longest Increasing Subsequence : LIS)

질문 검색에서 찾은 내용인데 증가한다는 개념이 strictly increasing(강한 증가함수)라는 점이다.

그러니까, 현재 값은 이전 값보다 커야한다. 같아서도 안된다.

( An > An-1, not An >= An-1 )

 

해결방법은 이렇다

* dp 리스트 안에는 그 원소까지 증가하는 부분수열을 구했을 경우의 길이를 저장한다.

** 시작 값은 1로 초기화를 해준다. (자기 자신만을 갖는 부분수열의 경우라고 생각하면 된다.)

1) 첫 번째 원소는 무조건 1값을 갖는다. (자기 자신만을 원소로 갖는 순열)

2) 두 번째 원소부터는 왼쪽에 위치한 원소들과 비교를 진행한다

3) 더 작은 원소일 경우에만 그 원소의 dp값을 가져온다. 여기에 1을 더해주면 현재 값의 LIS의 길이가 된다. (현재 값이 포함되기 때문에) 이를 현재값의 dp리스트에 저장해준다.

4) 이후 현재값의 왼쪽에 있는 수들과의 비교를 추가로 진행하게 되는데, 이들 중 하나가 이전에 구한 LIS보다 더 클 수도 있다. 때문에 이들과의 비교 후 더 큰 값을 찾아 현재값의 dp리스트에 다시 저장한다.

 

 

N = int(input())
nums = list(map(int, input().split()))

dp = [1]*N

for i in range(N):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1) # 1 더하기 잊지말자.
            # 이전 값을 호출 한 뒤 저장할 때 현재 원소까지 포함한 길이 (+1)로 저장했기 때문에
            # 다른 값들의 LIS를 호출하고 나서는 1을 더해서 비교해야한다.

print(max(dp))

그렇게 모든 원소의 LIS를 구해주면 된다.

 

그 중 최댓값이 정답이다.

 

#14002 출력까지 해보자 https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

 

출력을 하는 경우까지 추가된 내용이다. 고민 끝에 또 검색... 역시 비기너는 검색뿐인가..?

괜히 새로운걸 짜려고 애쓴 탓에 문제가 생겼던 것 같다.

저 방법을 이용하면 된다.

*nums의 길이는 dp의 길이와 같다.

**nums속 해당 숫자의 LIS는 동일한 인덱스의dp값과 같다.

N = int(input())
nums = list(map(int, input().split()))

dp = [1]*N

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

order = max(dp)
print(order)

answer = []

for i in range(N-1, -1, -1):
    if dp[i] == order:
        answer.append(nums[i])
        order -= 1
answer.reverse()
print(" ".join(map(str, answer)))

따라서, dp와 nums의 마지막 인덱스부터 호출 할 수 있도록 루프를 구성한 뒤,

위 문제의 정답이었던 최대 길이에서 1식 빼가면서

해당 값과 동일한 dp를 가지고 있는 num을 nums에서 찾아주면 된다.

 

생각보다 쉬워서 슬펐다.