[26일차] TIL - Dynamic Programming

동적 계획법(Dynamic Programming)

동적계획법이란 복잡한 문제를 간단한 여러개의 문제로 나눠푸는 방법을 말합니다. 이것은 부분 문제반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용합니다.

 

재귀 알고리즘과 비슷해보이지만 결과를 매번 기록하여 연산을 중복하지 않기에 속도가 더 빠릅니다.

 

1. 퇴사

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

"""
dp(n번째 날, 여태까지 번 돈)
    -> 근무를 한다면 dp(n + t, 여태까지번돈, + n번쨰날에 번돈)
    -> 근무를 안한다면 dp(n + 1, 여태까지번돈)
"""

n = int(input())
lst = []
for _ in range(n):
    # 소요일수, 돈
    a, b = map(int, input().split())
    lst.append((a, b))

# lst = [(3, 10), (5, 20), (1, 10), (1, 20), (2, 15), (4, 40), (2, 200)]
max_pay = 0

def dp(idx, pay):
    global max_pay
    if idx >= n:
        if pay > max_pay:
            max_pay = pay
        return

    t, p = lst[idx]

    for i in range(2):
        if i == 1:
            if idx + t > n:
                return
            dp(idx + t, pay + p)
        else:
            dp(idx + 1, pay)


dp(0, 0)
print(max_pay)

 

 

 

 

2. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

전형적인 DP문제로 이전 원소까지의 합이 0보다 크다면 다음 값에 이전값을 더해서 갱신하는 방법입니다. 

직관적으로 풀이가 이해가 되지않았고 처음에 이 풀이를 봤을 때 '이렇게 하면 답이 나온다고?' 라고 의심했습니다.

사실 아직까지도 잘 이해가 가지 않습니다. 

아마 이렇게 풀이를 하는 이유는 단순히 subarray의 최대합을 구하기 때문에 이렇게 짧게 나올 수 있지 않았나 생각해봅니다.

class Solution:
    def maxSubArray(self, nums):
        for i in range(1, len(nums)):
            if nums[i - 1] > 0:
                nums[i] += nums[i - 1]
                
        return max(nums)