TIL 005 DP 대표유형

DP는 유형을 많이 접하는게 중요하다고 한다.....😂

📕 Knapsack

👉 접근 방법

2차원 배열에 가방에 들어갈 수 있는 무게를 늘려가며 모든 경우의 수 비교.
물건을 가방에 넣을 수 없다면, 지금까지 물건 중 최대 가치
넣을 수 있다면, 지금 물건의 가치 + 전 행렬에서 지금 무게를 뺏을 때의 가치

👉 코드

def knapsack():
    dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,K+1):
            if A[i][0] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-A[i][0]]+A[i][1])
    print(dp[-1][-1])

📕 LCS

👉 접근 방법

2차원 배열에 한 단어씩 늘려가며 모든 경우의 수를 비교.
새로 입력되는 단어가 같다면, 전 배열의 +1
그렇지 않다면, 지금까지 만든 단어 중 최대

👉 코드

def max_lcs():
	N = len(s1)
	M = len(s2)

	lcs = [[0 for _ in range(M+1)] for _ in range(N+1)]

	for i in range(1,N+1):
		for j in range(1,M+1):
			if s1[i-1] == s2[j-1]:
				lcs[i][j] = lcs[i-1][j-1] + 1
			else:
				lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1])
	print(lcs[-1][-1])

📕 행렬곱셈순서

👉 접근 방법

모든 행렬곱셈의 경우의 수를 곱해준다.
양 끝은 고정이나 중간을 어떻게 쪼개느냐로 경우의 수가 나뉘는 것을 이용한다.
A,B,C,D,E,F 를 예로 들면,
(A)(B,C,D,E,F)
(A,B) (C,D,E,F)
(A,B,C)(D,E,F)
(A,B,C,D)(E,F)
(A,B,C,D,E)(F)
가 모든 경우의 수 일 것인다. 다만 묶인 연산의 최소값은 이미 구해져 있어야 할 것이다.
2차원 배열에서 계산되는 순서와 모양을 보면 모든의 경우의 수가 고려되고 있음을 좀더 직관적으로 볼 수 있다.
주석과 점화식을 잘보자

👉 코드

dp = [[0 for _ in range(N)] for _ in range(N)]
for d in range(1,N): # 얼마만큼의 크기로 쪼갤 것인가
    for i in range(N-d): # 시작점
        j = i+d # 끝점
        dp[i][j] = math.inf
        for k in range(i,i+d): # 나누는 점
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+A[i][0]*A[k][1]*A[j][1])
print(dp[0][N-1])

📕 TSP(외판원순환)

👉 접근 방법

DFS처럼 재귀로 완전탐색해 최소값을 취한다.
재귀 중에 구체적인 경로는 중요하지 않음으로 비트 연산을 사용
중복되지 않도록 재방문을 막는다
https://developmentdiary.tistory.com/406
https://shoark7.github.io/programming/algorithm/solve-tsp-with-dynamic-programming

👉 코드

dp = [[None]*(1<<N) for _ in range(N)]

def find_path(last,visited):
    if visited == (1<<N)-1 # 모두 방문 시
        return dp[last][0] or math.inf # 0일때는 math.inf
    if dp[last][visited] is not None: # 중복 방문 시
        return dp[last][visited]
    tmp = math.inf
    for i in range(N):
        # 방문한적이 없고 갈 수 있다면 그 중 최소값
        if visited & (1<<i) == 0 and A[last][i] != 0:
            tmp = min(tmp,find_path(i,visited | (1<<i)) + A[last][[i])
    dp[last][visted] = tmp
    return tmp
    

📕 계단오르기

👉 접근 방법

2차원 배열을 이용. 세 칸을 연속해서 점프할 수 없다. 즉, 한칸 뛰었다면 다음번에는 두 칸을 뛰어야한다.
그래서 N에 대해 두 개의 배열을 써서 A[N][0]은 두 칸 뛴 값 A[N][1]은 한 칸 뛴 값을 넣어준다.

👉 코드

dp = [[0,0] for _ in range(N)]
dp[0] = [A[0],0] # 초기값은 넣어줘야 
dp[1] = [A[1],A[1]+A[0]]
for i in range(2,N):
    dp[i][0] = max(dp[i-2][0],dp[i-2][1]) + A[i]
    dp[i][1] = dp[i-1][0] + A[i]
    
print(max(dp[N-1][0],dp[N-1][1]))
    

📕 RGB

👉 접근 방법

Nx3배열에 집씩 늘려가며 모든 경우의 수를 비교.
전에 사용된 색깔을 뺀 나머지 두 개의 색에 대해 최솟값을 연산

👉 코드

dp = [[0,0,0] for _ in range(N)]
dp[0] = [A[0][0],A[0][1],A[0][2]]
for i in range(1,N):
	dp[i][0] = min(dp[i-1][1]+A[i][0],dp[i-1][2]+A[i][0])
	dp[i][1] = min(dp[i-1][0]+A[i][1],dp[i-1][2]+A[i][1])
	dp[i][2] = min(dp[i-1][0]+A[i][2],dp[i-1][1]+A[i][2])
print(min(dp[N-1][0],dp[N-1][1],dp[N-1][2]))

📕 연속합

👉 접근 방법

정말 간단한 문제였는데 한참 고민한 문제.
1차원 dp 에 음수가 아닌 연속 수들만 모두 더함.

👉 코드

dp = [0 for _ in range(N)]
for i in range(0,N):
	dp[i]= max(0,dp[i-1])+A[i]
print(max(dp))

📕 2xn 타일

👉 접근 방법

피보나치 수열로 풀리는 문제가 꽤 있다.

👉 코드

dp = [0 for _ in range(N)]
dp[0], dp[1] = 1,2
for i in range(2,N):
    dp[i] = (dp[i-1] + dp[i-2])
print(dp[N-1])

📕 동전1

👉 접근 방법

knapsack 처럼 동전의 모든 동전의 가치에 대해 동전이 만들 수 있는 dp 를 만든다.
잘 보면 N 사이즈의 dp만으로 해결 가능하다.

👉 코드

dp = [0 for _ in range(K+1)]
dp[0] = 1
for i in range(0,N):
	for j in range(1,K+1):
		if j >= A[i]:
			dp[j] = dp[j-A[i]] + dp[j]
print(dp[K])