DP 개념정리하기 (1)

 

Dynamic Programming 이란

완전탐색의 비효율성을 해결하기 위해 동적으로 계획해서 계산하는, 알고리즘

---

1. Subproblem을 그대로 합치면 되는 DP

N번째 원소 구하기 - Backtracking  

N번째 원소 구하기 - DP 구현 1 - Memoization

점화식을 쭉 계산할 때 같은 계산이 반복될 수 있다.

아래 그림에서 F(4)가 왼쪽 트리에도 있고 오른쪽 트리에도 있는 것을 확인할 수 있듯이 같은 계산이 반복될 수 있어서,

모든 노드를 보는 계산은 비효율적이다.

따라서, 같은 계산 반복됨을 피하기 위해 나온 방식이 Memoization

계산한 적이 있으면 기억하기

 

1. Memo라는 기억배열을 생성한다. + 초기화 -1값으로 (계산에서 절대 나올 수 없는 값인 -1로 초기화)

2. n=1, n=2인 경우는 수열에 따라 2와 7임을 알 고 있으므로 조건문 작성

3. 그 외인 경우는 점화식 작성

int n = 6;
int memo[7];

void InitializeMemo(){
	for(int i = 1; i <= n; i++)
    	memo[i] = -1;
}

int f(int n){
	if(memo[n] != -1)
    	return memo[n];
    if(n==1)
    	memo[n] = 2;
    if(n==2)
    	memo[n] = 7;
    else
    	memo[n] = f(n-1) + 2 * f(n-2)
    
    return memo[n];
}

N번째 원소 구하기 - DP 구현 2 - Table

int n = 6;
int dp[7];

int main(){
	dp[1] = 2; dp[2] = 7;
    
    for(int i = 3; i <= n; i++)
    	dp[i] = dp[i-1] + 2 * dp[i-2]
        
    cout << dp[i] << endl;
    return 0;
 }

N번째 원소 구하기 - 실습

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

dp[1] = 1
dp[2] = 1

for i in range(3,n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[4])

---

2. 격자 안에서 한 칸씩 전진하는 DP

 

1. 테이블 정의

2. 초기값

3. 점화식

이 방식으로 DP 풀기

1. 테이블 정의

1. " 마지막으로 방문하는 위치가 같다면" "이동한 경로의 숫자 합"은 클수록 더 좋다!

3번째 줄에서 도착하는 위치가 4인 경우가 되는 여러가지 경우 중에서,

3번째 줄에 도착하기 전까지의 이동한 경로의 숫자 합을 비교하는 것.

 

이 문제의 경우, 어느 지점에 오는 방법은 두가지이다.

2. 두가지에서 오는 경우 중 max값을 선택하면 된다.

3. 점화식 정의

 

2. 초기값

import sys

INT_MIN = -sys.maxsize

n = 4
a = [
    [4],
    [6,2],
    [3,7,9],
    [3,4,9,9]
]

dp = [
    [0 for _ in range(4)]
    for _ in range(4)
]

def initialize():
    dp[0][0] = a[0][0]
    for i in range(1,n):
        dp[i][0] = dp[i-1][0] + a[i][0]

    for i in range(1,n):
        dp[i][i] = dp[i-1][i-1] + a[i][i]

initialize()

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

ans = INT_MIN
for j in range(n):
    ans = max(ans, dp[n-1][j])

print(ans)

정수 사각형 최대합 - 실습

n = int(input())
graph = [ list(map(int, input().split())) for _ in range(n)]
dp = [ [0 for _ in range(n)] for _ in range(n)]

# 오른쪽 이나 밑으로 이동한다.

def initialize(dp):
    
    dp[0][0] = graph[0][0]
    for i in range(1,n):
        dp[i][0] = dp[i-1][0] + graph[i][0]
        dp[0][i] = dp[0][i-1] + graph[0][i]

initialize(dp)

for i in range(1, n):
    for j in range(1,n):
        dp[i][j] = max((dp[i-1][j] + graph[i][j]) , (dp[i][j-1] + graph[i][j]))

print(dp[n-1][n-1])