[0210 TIL]HUFS 겨울방학 코테대비 캠프(DP)

• [0 for _ in range(n)]과 [0] * n 의 차이점은 없다.
• 단순히 0을 n번 복사하는 것을 for문으로 반복하기 때문에 새로운 것을 지정해주는 것
• 하지만 [0, 0, 0] * 3 은 주소를 공유하기 때문에? 위험하다.

 

• ⭐️방향성⭐️이 없으면 DP를 사용할 수 없다.
• 상태에 대한 정의, 뭘 최대로 해야하나 뭘 최소로해야 문제가 풀리나를 잘 훈련해야함(like 횟수와 도달한 수만 중요하지 경로는 중요하지 않다?!)

 

 

최대 증가 부분 수열

| 문제

N개의 숫자가 주어졌을 때, 가장 긴 증가 부분 수열의 길이를 구하는 프로그램을 작성해보세요

부분 수열이란 수열의 원소들 중 임의로 몇 개를 골라 순서대로 나열한 수열을 의미하고, 이때 순서대로 나열했을 때 원소들이 계속 증가한다면 이 수열을 증가 부분 수열이라고 합니다.

예를 들어, N=6, 주어진 수열이 1,6,4,3,9,3 이라 했을 때

1,3,6은 순서대로 나열해 만들 수 없으므로 부분 수열이라 할 수 없습니다.

1,6,3은 부분 수열 이지만 계속 증가하는 수열이 아니므로 증가 부분 수열은 아닙니다.

1,3,3은 부분 수열 이지만 역시 마찬자기로 계속 증가하는 수열이 아니므로 증가 부분 수열은 아닙니다.

1,4,9는 계속 증가하는 부분 수열이므로 증가 부분 수열 입니다.

import sys
INT_MIN = -sys.maxsize

n = int(input())
dp = [0] * (n + 1)
arr = [0] + list(map(int, input().split()))

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

print(max(dp))

• 모든 곳에서 시작할 수 있는 DP면 dp[0]에 0을 넣어두고 시작하면 된다.
• 즉, 4 , 1, 2, 3 이라는 배열에서 수열을 뽑아내야할 때, 1에서 시작할 때 1로 시작할 수 있다.
• 그러니깐 처음부터 dp[0] 의 값을 1로 지정할 수 없기 때문에(4부터 시작하지 않을 수 있기 때문에) dp[0]을 0으로 시작하여서 처음으로 시작하는 수열을 dp[j] = 1 로 넣을 수 있게 해주는 테크닉.
• 그리고 저 for i range(1, n + 1) 과 for j in range(i)를 잘 기억하자. 해당 i의 뒤를 검사하는 이중 for문이다.