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

문제 설명

주어진 수열에서 부분 수열 중,

1. 값이 연속하여 증가하고

2. 그 부분 수열의 길이가 가장 긴 값

을 구하라.

접근 방법

1. Greedy 접근

이 접근 방식은 문제를 이해하는데 도움을 준다.

단계를 i번째 수열의 선택

매 단계의 값을 i번째를 선택했을 때 가장 긴 부분수열의 길이라 정의하였다.

주어진 예제의 수열 {10,20,10,30,20,50}이 수열에서 그리디한 접근 방법을 적용한다면,

​ step1. 첫번째 단계는 자명하다. 10 하나 선택하여 최적 값은 1이 된다.

​ step2. 20보다 직전 값이 더 작으므로 선택. 따라서 최적 값은 2.

​ step3. 10에선 직전 값이 더 크므로 자기 자신 1

​ step4. 30에선 직전값이 더 작으므로 2

.....

이런 식이면 최적 값 4가 나올 수 없다.

step4에서 보듯, 직전 값 뿐만이 아닌 그 이전의 값 또한 고려해야만 한다.

2. DP 접근

따라서 이전의 값을 고려하는 방법으로 두가지를 들 수 있는데,

1. 지나왔던 수 중 가장 긴 길이의 수만을 기억하는 방법
   • step4에서 step2의 20을 선택한다면 step4에서 step1의 수를 고려할 필요가 없다. 따라서 이미 선택한 수 중에 가장 긴 부분의 큰 값을 가지고 있는 가지고 있는 수를 만든다.
   • step4에서 a4(4번째 수) 직전 값을 모른다. 따라서 탐색을 해야만 하는데, 가장 긴 길이를 기억하는 수열을 정렬한 상태로 기억한다면 이진 탐색을 통하여 탐색 소요시간을 줄일 수 있다.
   • 즉 Key 수열의 값, Value는 최적값이 된다. Key를 이진탐색하여 Value를 찾는 방식
2. 지나왔던 수를 모두 탐색하는 방법
   • i번째에서 최적값을 찾는다면 1~i-1 까지의 수 중에서 i보다 작은 값 중 최적값이 가장 큰 값을 찾는 방식이다. 위와 달리 코드가 직관적이고 간결해진다. f(i) = max(f(1),f(2), ... , f(i-1)) + 1 (단 f(k)는 a_i>a_k, a_i<=a_k일 경우엔 f(k)의 값은 0.)

코드를 간결하게 작성하기 위해 2번 방법으로 접근했다.

시간 복잡도는 위에서 보는 바와 같이 i번째일 경우 1~i-1까지 비교해야하기 때문에 시간 복잡도는 1+2+...+n = O(n^2) 이 된다.

구현

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

dp = [0 for _ in range(n)]
dp[0] = 1

rst = 1
for i in range(1,n):
    maxVal = 0
    for j in range(i):
        if nums[i]>nums[j] and maxVal < dp[j]:
            maxVal = dp[j]
    dp[i] = maxVal + 1
    if rst<dp[i]:
        rst = dp[i]

print(rst)