다이나믹 프로그래밍 정리

다이나믹 프로그래밍 문제풀이

 

첫 문제

https://velog.io/@0_hun/프로그래머스-코딩-테스트-공부-2022-KAKAO-TECH-INTERNSHIP-Level-3-Python

프로그래머스 - 코딩 테스트 공부 (2022 KAKAO TECH INTERNSHIP) / Level 3 / Python

https://school.programmers.co.kr/learn/courses/30/lessons/118668

프로그래머스

 

잘못된 첫 코드

 

def solution(start_alp, start_cop, problems):
    INF = int(1e9)
    max_alp = max(problems, key=lambda x: x[0])[0]
    max_cop = max(problems, key=lambda x: x[1])[1]
    
    dp = [[INF] * (max_cop+1) for _ in range(max_alp+1)]
    dp[start_alp][start_cop] = 0
                                                
    for r in range(start_alp, max_alp):
        for c in range(start_cop, max_cop):
            dp[r+1][c] = min(dp[r][c] + 1, dp[r+1][c])
            dp[r][c+1] = min(dp[r][c] + 1, dp[r][c+1])
            
            for alp_req, cop_req, alp_rwd, cop_rwd, cost in problems:
                if alp_req <= r and cop_req <= c:
                    next_alp = min(max_alp, r+alp_rwd)
                    next_cop = min(max_cop, c+cop_rwd)
                    dp[next_alp][next_cop] = min(dp[r][c] + cost, dp[next_alp][next_cop])
    
    print(*dp, sep="\n")
    return dp[max_alp][max_cop]

out of index를 방지하기 위해서 마지막 반복문 원소를 제외해서 문제가 됐다.

 

def solution(alp, cop, problems):
    max_alp = max(max(problems, key=lambda x: x[0])[0], alp)
    max_cop = max(max(problems, key=lambda x: x[1])[1], cop)
    
    INF = int(1e9)
    dp = [[INF] * (max_cop+1) for _ in range(max_alp+1)]
    for r in range(alp+1):
        for c in range(cop+1):
            dp[r][c] = 0
    
    for r in range(alp, max_alp+1):
        for c in range(cop, max_cop+1):
            nr, nc = min(r+1, max_alp), min(c+1, max_cop)
            dp[nr][c] = min(dp[nr][c], dp[r][c]+1)
            dp[r][nc] = min(dp[r][nc], dp[r][c]+1)
            
            for problem in problems:
                alp_req, cop_req, alp_rwd, cop_rwd, cost = problem
                if alp_req <= r and cop_req <= c:
                    n_alp, n_cop = min(r+alp_rwd, max_alp), min(c+cop_rwd, max_cop)
                    dp[n_alp][n_cop] = min(dp[n_alp][n_cop], dp[r][c] + cost)
    return dp[max_alp][max_cop]

이 문제의 핵심은

2차원 배열에서의 dp를 적용하는 것과

알고력과 코딩력이 한계를 넘어가지 않게 조건을 따져가며 구현을 이어가야한다는 점이다.

재밌는 문제였다.

 

문제를 통해

무한정 풀 수 있는 문제 -> 각 인덱스에서 반복문 호출

공부하는 순서가 상관없다 -> 각 인덱스에서 반복문으로 호출해 min으로 대입

 

 

두 번째

 

https://www.acmicpc.net/problem/2293

2293번: 동전 1

https://velog.io/@jxlhe46/백준-2293번.-동전-1-bfi120m5

[백준] 2293번. 동전 1

 

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
coins = [coin for coin in coins if coin <= 10000]

dp = [0] * (10001)
for coin in coins:
    dp[coin] = 1

for idx in range(10001):
    for coin in coins:
        if idx - coin >= 0:
            dp[idx] += dp[idx-coin]

잘못된 접근으로 시도한 첫 문제풀이이다.

dp 테이블을 idx로 접근하면 순서에 따라 경우의 수를 다르게 계산하기 때문이다.

동전의 순서를 반복문으로 고정해서 시도해야한다.

 

import sys
input = lambda: sys.stdin.readline().rstrip()

n, k = map(int, input().split())
coins = {int(input()) for _ in range(n)}
coins = [coin for coin in coins if coin <= k]

dp = [0] * (k+1)
for coin in coins:
    dp[coin] += 1
    for idx in range(1, k+1-coin):
        if dp[idx]:
            dp[idx+coin] += dp[idx]
print(dp[k])

 

문제를 통해

첫 번째 문제와 동일하게 무한정 반복할 수 있고, 순서도 상관없다.

하지만 최소값을 묻는 것과 경우의 수를 묻는 것의 차이가 있다.

인덱스에 접근하는 반복문보다 앞서서 동전을 반복하면 동전의 순서를 고정시킬 수 있다.

 

정리하면 둘은 비슷해 보이나

순서는 상관없이 최소값을 구하는 문제와 순서가 같으면 하나로 처리하는 경우의 수 문제의 차이가 있다.

 

세 번째

 

각 선택에서 아이템을 무한정 고를 수 없을 때는 어떻게 할까?

https://www.acmicpc.net/problem/5557

5557번: 1학년

 

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

1학년 문제풀이

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
numbers = list(map(int, input().split()))

dp = [[0] * (N-1) for _ in range(21)]
dp[numbers[0]][0] = 1

for c in range(1, N-1):
    for r in range(21):
        if r+numbers[c] < 21:
            dp[r+numbers[c]][c] += dp[r][c-1]
        if 0 <= r-numbers[c]:
            dp[r-numbers[c]][c] += dp[r][c-1]

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

 

퇴사 문제풀이

import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
sche = [list(map(int, input().split())) for _ in range(N)]

max_value = 0
dp = [0] * (N+1)
for idx in range(N-1, -1, -1):
    t, p = sche[idx]
    if idx + t <= N:
        max_value = max(max_value, dp[idx+t] + p)
    dp[idx] = max_value
print(max_value)

 

각 선택지에서 정해진 아이템들 중에 골라서 최댓값 혹은 제시된 값을 찾는 문제이다.

문제를 상상 속에서 그려보면, 분기가 마구 뻗치는 그림이 그려진다.

 

첫 번째와 두 번째 문제와의 차이는

아이템을 꺼내는 반복문이 index 반복문이 내,외부에 존재하지 않고 각 아이템의 index로 접근하는 것이다.

결국 dp는 점화식으로 표현하는 것을 목표로 두고,

최대 최소의 경우 min, max를,

경우의 수는 이전 상태에서 누적시키는 것을 구현하면 그만이다.

 

1학년과 퇴사 사이의 차이는

퇴사의 아이템은 index로 정한 d-day와 관련이 있는 반면,

1학년은 각 연산의 값과 상관없기 때문에 2차원으로 표현해야했다.