[백준] 가장 긴 증가하는 부분 수열

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

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

다이나믹 프로그래밍을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

수열이 주어졌을 때, 이 수열에서 가장 긴 증가하는 부분수열을 구하는 프로그램을 만들어야 합니다. 

예를 들면, A = {10, 20, 10, 30, 20, 50}의 수열에서 가장 긴 부분수열은 A = {10, 20, 10, 30, 20, 50} 으로 길이가 4입니다.

 

<Solution>

다이나믹 프로그래밍으로 간단하게 해결할 수 있습니다. 

 

dp[i] = i번째 원소를 마지막으로 하는 가장 긴 증가수열의 길이로 정의하면, dp[i] = dp[0] ~ dp[i-1] 까지중 수열의 해당원소가 현재의 i번째 원소보다 작은 경우중 dp값이 max인것 + 1을 하면 됩니다. 

 

사실 이 과정이 그렇게 효율적이여 보이지는 않습니다.

 

간단한 예시로 수열을 array라 두고 dp[4]를 구하는 상황을 생각해보면, 

dp[4]를 구하기 위해 array[0], array[1], array[2], array[3] 까지의 원소들과 array[4]의 원소를 비교하는 과정이 필요합니다. 또한 이에 해당하는 dp 값 또한 대소비교를 해야합니다. 만약 dp후보군이 dp[0~3] 모두 나왔을 경우, dp[4]를 구하기 위해서는 8번 만큼의 대소비교 연산이 필요합니다. 

 

즉 dp[i]를 위해 2i 만큼의 대소비교 연산이 필요하고, 이것을 i = 1~n-1 까지 한다고 생각해보면, n^2의 time complexity를 가지는 것을 알 수 있습니다.

 

인터넷을 보니 nlogn의 time complexity로 해결하는 방법이 있던데 추후에 아래의 문제를 통해 다시 다루어 보도록 하겠습니다.

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

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

 

(n^2의 time complexity를 가지는 코드)

import sys

N = int(sys.stdin.readline().rstrip())

array = list(map(int, sys.stdin.readline().rstrip().split()))

dp = [0] * N
dp[0] = 1
for i in range(1, N):
    tmp = 0
    for j in range(i):
        if array[j] < array[i] and tmp < dp[j]:
            tmp = dp[j]
    dp[i] = tmp+1

print(max(dp))