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

실버 II

💡문제 분석 요약

동적 계획을 사용한 문제 풀이

💡알고리즘 설계

현재 위치(i) 의 값과 그 전에 있던 값(1~j)들을 모두 비교한다.

이때 그 전에 있던 값이 작으면, 이전 값의 인덱스를 가진 dp에서의 최댓값에 1을 더한 것을 dp[i] 값으로 설정한다.

💡코드

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().strip().split()))
dp=[1 for i in range(n)]

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

print(dp[n-1])

💡시간복잡도

i의 N과 j 의 N O(n^2)

💡 틀린 이유

이전에 배열로 확정된 최소값과 앞으로의 값을 비교하기만 했다. 이런 저런 예시를 보며 답이 얼추나와 이걸 구현해봐야지 했지만 구현력이 부족했다.

예를 들어, 1 2 1 2 인 경우, 1과 2를 비교했을 때 더 작으므로 dp[1]에 dp[0]=1에 +1한 값을 저장하고, 그 다음 값을 비교하려면 min을 2값으로 설정한 뒤 값을 구하려고 했다.

9 4 2 8 9 3 에서도 2와 8에서 8이 더 커지니 2, min값인 8보다 9가 더 커지니 +1해서 3, 총 3이라고 나왔다.

그러나 이러면 min값을 언제 비교 해야하는 지 설정하기 어렵고, 그 전에 이미 큰 값이 나와버렸을 때 제일 큰값이 min으로 설정되어 295678에서 2값으로 나오게 된다. 따라서 아무리 그 다음 값이 커져서 값을 넣었다고 해도 이전 값과 비교하면서 체크하는 과정이 필요하다.

이 과정을 bisect로 비교하여 실제로 만들었던 수열을 재 교정하거나 그 전의 수를 다 돌아가며 큰 경우 (수열을 만들 수 있는 경우) 그 dp값에 +1을 하여 수열을 길이를 dp에 저장하는 방법을 활용해야 한다.

💡 다른 코드

0으로 초기화한 dp, array의 첫 값을 가진 list

list는 증가하는 부분 수열을 나타낸다.

array 를 돌면서, list 마지막 값과 arry값을 비교한다. 만약, array값이 더 크다면, list에 array값을 더해준다.

array값이 더 작다면(즉, array[i]가 수열에 들어갈 수 없으면), 만든 수열을 돌면서 array[i]보다 큰 값을 찾고, 거기에 수열 array 값을 넣어준다.

더 작은 값을 넣어야 길어지기 때문에 큰 값을 그나마 작은 array현재 값으로 변경하고, 그 뒤에 받을 값의 범위를 확장하기 위함이다. ← 이것을 biscet으로 구현하면 이진탐색을 쓰기에 더 빠르고 쉽게 구할 수 있다.

그리고 list의 길이를 print()한다.

for i in range(x):
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bisect.bisect_left(dp, arr[i])#대
        dp[idx] = arr[i]

💡 기억할정보

bisect에서 bisect_left,bisect_right와 같이 이분 탐색을 활용하여 정렬된 상태를 유지하면서 요소를 추가할 수 있다. bisect_left(arr,number)
직접 그런 수열을 만들면서 답을 구해도 괜찮다. 또한 dp의 배열을 이전보다 무조건 값이 더해지거나 이전 값을 계승하는 형태가 아닌, 다른 값과 비교하며 업데이트 하는 형태도 존재한다.