코딩 테스트 DP 정리 (파이썬)

DP(동적 계획법, 다이나믹 프로그래밍)

• 복잡한 문제를 한 번에 해결하는 것이 아닌, 조금씩 점차적으로 풀이하는 유형이다. (점화식을 떠올리면 이해하기 쉬움)
• 동일한 작은 문제가 여러 번 반복해서 나타나는 경우, (Optimal Substructure): 문제의 최적해가 하위 문제의 최적해로 구성되는 경우 사용

접근방식

bottom-up접근 -(접근이 쉬움) - 이거 쓰자

• 작은 문제부터 차례대로 해결합니다.
• 점화식을 구하고 for문으로 작은것부터 구해서 메모이제이션한다
  1. dp이름 배열 생성(메모이제이션)
     • 1차원, 2차원, 3차원으로 dp를 만든다..
  2. 초기값설정
  3. 점화식 구하기

top-down (큰 문제를 작은 문제로 나눈다)

• 큰 문제를 작은 문제로 나누고, 재귀적으로 문제를 해결,
• 이미 계산한 결과를 저장하여 중복 계산을 방지(메모이제이션)

피보나치 https://www.acmicpc.net/problem/2579

#피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.
#그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
# 이를 점화식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다
n = int(input())
dp = [0 for _ in range(n+1)]
dp[0], dp[1] = 0,1
if n <= 1 :
    print(n)
else:
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2] # 점화식으로 메모이제이션 
    print(dp[n])

유형

(계단 오르기) 유형

• 순서대로 한 칸씩 나아가는 문제
• 경로 최적화 문제
• 순서 중요 (계단 순서대로 이동)
• 다음 위치로 이동할 때 이전 위치가 뭔지에 따라 상태가 달라짐.

계단 오르기 https://www.acmicpc.net/problem/2579

# 1,2,3층은 초기값 설정, 누적합, 투포인 
# 점화식은 dp[i] = max(dp[i-2], dp[i-3] + score[i-1]) + score[i]
def climb_stairs(scores):
    n = len(scores)
    if n == 0:
        return 0
    if n == 1:
        return scores[0]
    if n == 2:
        return scores[0] + scores[1]

    dp = [0] * n
    dp[0] = scores[0]
    dp[1] = scores[0] + scores[1]
    dp[2] = max(scores[0] + scores[2], scores[1] + scores[2])

    for i in range(3, n):
            dp[i] = max(dp[i - 2], dp[i - 3] + scores[i - 1]) + scores[i]
    return dp[-1]
n = int(input())
scores = [int(input()) for _ in range(n)]
print(climb_stairs(scores))

예) 프로그래머스 - 정수 삼각형

n으로 표현

• i는 현재 N을 사용한 횟수 (1부터 8까지), j는 그 중 앞에 사용할 횟수 (1부터 i-1까지)를 의미합니다
• a, b는 각각 j번과 (i - j)번 N을 사용해 만들 수 있는 수
  • dp[i] 를 dp[j] + dp[i-j]로

def solution(N, number):
    if N == number:
        return 1

    dp = [set() for _ in range(9)]  # 인덱스 1~8까지 사용

    for i in range(1, 9):
        # 숫자 이어붙이기: 5, 55, 555 ...
        dp[i].add(int(str(N) * i))

        for j in range(1, i):
            for a in dp[j]:
                for b in dp[i - j]:
                    dp[i].add(a + b)
                    dp[i].add(a - b)
                    dp[i].add(a * b)
                    if b != 0:
                        dp[i].add(a // b)

        if number in dp[i]:
            return i

    return -1

(knapsack(배낭)) 유형

• 제한된 리소스(예: 무게, 가치) 안에서 조합을 골라 최적 결과를 낼 때 사용
• 제한된 용량의 배낭에 최대 가치를 가지도록 물건을 담는 방법을 찾는 것(순서 상관 x)
• 같은 요소를 중복으로 사용하지 않기 위해서
  • 정순 + dp[:] 복사 → 이전 상태 기준으로 갱신하여 중복 사용 방지
  • 역순 순회 → 현재 상태에서도 안전하게 갱신되므로 복사 없이 중복 사용 방지(빠르고 쉬움)

문제

백준 완벽한 배낭

"""
4 7
6 13
4 8
3 6
5 12
K 무게 내에서 최대의 가치
dp[무게] = 가치
"""

# 정순 + dp[:] 복사 → 이전 상태 기준으로 갱신하여 중복 사용 방지
n, k = map(int, input().split())  # 물건 수, 배낭 용량
items = [tuple(map(int, input().split())) for _ in range(n)]  # (무게, 가치)

dp = [0] * (k + 1)

for weight, value in items:
    new_dp = dp[:]  # 복사! 현재 상태 기준으로만 갱신
    for i in range(k + 1):
        if i + weight <= k:
            new_dp[i + weight] = max(new_dp[i + weight], dp[i] + value)
    dp = new_dp
print(max(dp))

# 역순 순회 → 현재 상태에서도 안전하게 갱신되므로 복사 없이 중복 사용 방지
N, K = list(map(int,input().split()))
pack  = []
for _ in range(N):
    pack.append(list(map(int,input().split())))

b = [0] * (K+1)

for w,v in pack:
    for i in range(K,w-1,-1):
        b[i] = max(b[i],b[i-w]+v)
        # 현재 항목의 칼로리를 제외한 나머지 칼로리에 대해 이전에 계산된 최대 점수

print(b)

• 예제백준 배낭
• swea 햄버거