34. 동적 계획법 - 막대기 자르기(Rod cutting) [파이썬]

막대기 자르기(Rod cutting)

 

하나의 막대기가 있다.
막대기의 길이에 따라 가격이 다르다. 
최고의 수익을 얻도록 막대기를 자르라. 
이때 최고의 수익은?

파이프 전체의 길이, 잘랐을 때 길이에 따른 가격이 들어간 배열이 주어짐.  

length : i	1	2	3	4	5	6	7	8	9
price : Pi	1	5	8	9	10	17	17	20	24

 

재귀로 구현

def cut_rod(price, n):
    max_val = price[n]
    for i in range(1, n):
        max_val = max(max_val, price[i] + cut_rod(price, n - i))
    return max_val


print(cut_rod([0, 1, 5, 8, 9, 10, 17, 17, 20, 24], 8))  # 22

어렵게 느껴지던 재귀가 이제는 왠지 쉬워 보입니다. ~!

 

위 코드를 보면 cut_rod(n) = cut_rod(i) + cut_rod(n-i)을 과정을 반복하는 것을 보게 됩니다. 
동적 프로그래밍도 큰 문제를 작은 문제로 나누고 이를 다시 결합하는 과정을 가지게 되는데요.. 
재귀의 반복을 리스트를 이용해서 훨씬 효과적으로 처리합니다. 

 

동적계획법으로 구현

def cut_rod(price, n):
    max_values = [0]
    max_value = 0
    for j in range(1, n + 1):
        for i in range(j):
            max_value = max(max_value, price[j - i] + max_values[i])
        max_values.append(max_value)
    return max_values[n]


print(cut_rod([0, 1, 5, 8, 9, 10, 17, 17, 20, 24], 8))  # 22

0에서 시작해서 n까지 max_values를 완성해 갑니다. 

functools.cache

파이썬 3.9에 새로 추가된 함수.
파이썬 3.2에 추가된 lru_cache(maxsize=None) 와 같다. 
메모이제이션과 같은 효과가 있다. 

from functools import cache


@cache
def cut_rod(prices, length):
    max_val = 0
    for i in range(1, length + 1):
        max_val = max(max_val, prices[i] + cut_rod(prices, length - i))
    return max_val


print(cut_rod((0, 1, 5, 8, 9, 10, 17, 17, 20, 24), 8))  # 22
print(cut_rod((0, 1, 5, 8, 9, 10, 17, 17, 20, 24), 9))  # 25

 

 

파이썬에서 정수의 최댓값 / 최솟값은 'sys.maxint' / '-sys.maxint - 1'입니다.

(sys.maxint is always set to the maximum plain integer value for the current platform, the minimum value is -sys.maxint - 1)

그런데 라이브러리 불러오기가 애매합니다. 

라이브러리를 불러오지 않고 사용할 수 있는 최솟값은 float('-inf') 최대값은 float('inf')입니다.

https://docs.python.org/ko/3.7/library/stdtypes.html#numeric-types-int-float-long-complex

(float는 접두사 "+" 나 "-"가 선택적으로 붙을 수 있는 양 또는 음의 무한대를 나타내는 문자열 "inf"를 받아들입니다.)