DP 재 개념

DP가 너무 어려워 개념을 재정리하겠다. 

 

DP는 기본적으로, 모든 조합을 만들때, 계산을 줄이기 위함이다. 

 

73824, 73875 등등 DFS의 모든 총합을 구하는 문제일때는 

 

원하는 배열의 DP[I][J]의 값이 DP[I-1][J]에 입력받은 배열 array[i][j]를 더한값을 담으면 최대의 값을 구할 수 있다. 

 

이렇게 구하면, 이전 행만 활용해 이번행을 연산할 수 있고, 그 시작점은 구하지 않아도 된다.

*즉, 다음 행이 이전 행의 값 계산을 포함한다. 

 

연산을 기억해놓고 푸는 것이다 

 

<DP문제인지 구분되는 방법> 

 

1) DFS/BFS로 풀 수 있지만 N이 너무 크다 

2) 중복적인 연산이 일어났을때

3) 시간제약이 많을때 

 

<접근방법> 

 

DP는 정말 많은 풀이를 해야 한다. 

 

특히, DP와 같은 나만의 연산 정보를 담을 것을 담아서 , 풀이를 진행하는 것이 유리하다. 

 

백준 11053

 

해당문제는, 어째서 dp인지를 인지하는 것 부터 난관이 있었다.

 

*문제의 접근 방법 : Nlist의 해당 숫자가 부분 수열에 포함되었을때, 최대 길이를 찾아보자 .

 

import sys

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

Nlist = [0]+list(map(int,sys.stdin.readline().split()))

dp = [0]*(N+1)

for i in range(1,N+1) :

    mx= 0

    for j in range(0,i) :

        if Nlist[i]>Nlist[j] :

            #새로들어갈

            mx = max(mx,dp[j])

    dp[i]=mx+1

print(max(dp))

 

 

 

1. 10 20 30 50처럼, 정보가 기억되는 것을 주의하자 .

2. 입력받은 list들을 보고, list의 index중에서 자기보다 앞에 있던 index들 중에 자기보다 값이 작은게 있나 확인한다.

3. 있으면, max를 그떄의 기록(총 몇개인지)(dp)를 통해 확인한다

 

4. 최종적으로 , max에 하나를 더해 이를 dp에 기록한다. 

 

*또다시, 반대로 생각하는 문제에서 어려움을 겪었다. 들어가는 숫자 앞에 자기보다 작은것이 몇개인지를 계산하는 형태!

 

++ 문제를 풀다보면, 직접 손으로 풀다보니 그 답이 피보나치인 경우도 있다.

그런 경우든, dfs든, 혹은 문제가 dp의 형태를 따르는 형태이든

 

일단은 손으로 풀어봐야 한다.