[백준 11055, 11722, 11054][파이썬] 증가, 감소하는 수열 dp 문제

백준 문제 11055, 11722, 11054는 비슷한 문제로 묶어서 풀이를 해보려한다.

 

먼저 11055번 문제이다.

https://www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

이 문제를 푸는 가장 간단한 알고리즘은 이중 반복문을 사용하여 전부 조사하는 방법이다.

 

이 방법도 좋은 방법이지만 더 빠른 방법을 사용해보려 한다.

 

간단하게 1,3,2,6,9 라는 수열이 있다고 해보자.

 

이 수열의 값을 배열의 인덱스로 사용하는 방법이다.

 

모든 값이 0인 배열을 만든다. 길이는 1001이어야 한다.

 

수열의 값을 인덱스로 사용할 예정이고 수열의 값은 1에서 1000이기 때문이다.

 

알고리즘은 다음과 같다.

 

1. 수열의 값이 x라면 새로 만든 배열의 인덱스 0부터 인덱스 x-1까지 가장 큰 값을 m이라고 한다.
2. 새로 만든 배열의 인덱스 x에는 m+1 값이 저장된다.

수열의 첫 번째 값은 1이다.

 

배열의 인덱스 0까지 최댓값은 0이므로 배열의 인덱스 1 값은 0+1이 된다.

 

 

두 번째 값은 3이다. 인덱스 2까지의 최댓값은 1이므로 인덱스 3의 값은 1+1이 된다.

 

 

세 번째 값은 2이다. 인덱스 1까지의 최댓값은 1이므로 인덱스  2의 값은 1+1이 된다.

 

이를 계속 반복하다 보면 최종 결과는 다음과 같다.

이 중에서 최댓값을 구하면 그것이 곧 가장 긴 증가하는 부분 수열의 길이이다.

n = int(input())
li = list(map(int, input().split()))
dp = [0]*1001
for i in range(n):
    temp = li[i]
    dp[temp] = max(dp[0:temp])+temp
print(max(dp))

이중 반복문을 사용하는 알고리즘과 4배정도의 차이가 나는 모습을 볼 수 있다.

이 방법의 단점은 다음과 같다.

 

1. 항상 입력받을 수 있는 수의 최댓값만큼의 길이를 가진 배열을 만들어야 한다

 

수열의 값을 인덱스로 사용하기 때문에 항상 입력받을 수 있는 수의 최댓값만큼의 길이를 가진 배열을 만들어야 한다

 

이 문제에서는 최대 1000까지의 수만 입력받기 때문에 1001이라는 그렇게 길지 않은 길이지만 최댓값이 커진다면 곤란할 것이다.

 

2. 리스트의 인덱스에 따른 최대 길이를 알  수 없다.

1, 3, 2, 6, 9라는 수열의 경우 1이라는 수열의 최대 길이는 1.

 

(1, 3)이라는 수열의 최대 길이는 2.

 

(1,3,2)라는 수열의 최대 길이는 2.

 

(1,3,2,6)이라는 수열의 최대 길이는 3.

.

.

 

위 방식으로 구하는 것이 아니기 때문에

 

0번 인덱스부터 n번 인덱스까지의 부분 수열의 최대 길이를 알 수 없다.

 

이 문제를 해결하기 위해서 코드를 한 줄 추가했다.

n = int(input())
li = list(map(int, input().split()))
dp = [0]*1001
dp2 = [0]*n
for i in range(n):
    temp = li[i]
    dp[temp] = max(dp[0:temp])+temp
    dp2[i]=dp[temp]
print(max(dp2))

 

이런식으로 2번 문제를 해결할 수 있는데 굳이 이러한 코드를 추가한 이유는 11054번 문제 때문이다.

 

https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

 

 

위 문제를 푸는 알고리즘은 모든 인덱스 i에 대하여 인덱스 0부터 i까지의 가장 긴 증가하는 수열을 구하고 i부터 마지막 인덱스까지 가장 긴 감소하는 수열을 구한다.

 

그리고 다시 0부터 마지막까지 조사하면서 (가장 긴 증가하는 수열의 길이) + (가장 긴 감소하는 수열의 길이) -1이 가장 큰 값을 찾아내면 된다.

 

즉 모든 인덱스에 따른 최대 길이를 구해야 한다는 점이다.

 

그렇기 때문에 11055번에서 발생한 문제 2번을 해결한 것이다.

 

11054번 문제를 해결한 알고리즘은 아래와 같다.

 

n = int(input())
li = list(map(int, input().split()))
asc = [0]*1001
ascdp = [0]*1001
des = [0]*1001
desdp = [0]*1001
for i in range(n):
    m=li[i]
    asc[m] = max(asc[:m])+1
    ascdp[i] = asc[m]
for i in range(n-1,-1,-1):
    m=li[i]
    des[m] = max(des[:m])+1
    desdp[i] = des[m]
res=0

for i in range(n):
    res = max(res, ascdp[i]+desdp[i]-1)
print(res)

 

시간만 초과하지 않는다면 그냥 이중 반복문을 사용하는 것이 더 좋을지도 모르겠다.