[CLRS] [14-1] Dynamic Programming - rod cutting

1. Intro

- dynamic programming은 특정한 알고리즘이라기 보단, 기법이라고 하는게 맞다.

- DP는 복잡한 문제를 재귀적인 문제로 간단한 subproblems로 나누어 해결하는 기법이다.

- 마치 divide-and-conquer(분할-정복)과 유사해보인다.

- 하지만, 그 과정에서 subproblem이 중복이 되는 경우가 많기에, 이전에 수행한 연산결과를 재활용한다.

- 즉, Dynamic Programming은 "저장하며 풀기"정도로 기억하면 좋다.

 

2. Rod Cutting Problem

- Rod Cutting 문제에 대해서 알아보자.

- Rod Cutting은 다음과 같은 문제를 의미한다.

 

Q) 어떤 가치를 지닌 통나무(Rod)를 판다. 이 통나무는 길이에 따라 매기는 값이 달라진다.

이 때 주어진 길이 n의 통나무와 값이 담겨있는 배열 p에 대해 이 Rod의 max price를 구하시오.

2.1. Basic approach(Bruteforce)

- 막대의 최적의 분할 방식을 찾기 위해 문제를 다음과 같이 재귀적으로 정의해보자.

"""

- r_i : 길이가 i인 막대를최적으로 잘라서 얻을 수 있는 최대 금액 

- 막대를 자르는 방법은 다음 두 가지 단계로 나뉜다:

i) 막대의 왼쪽 끝에서 일정한 길이의 조각을 잘라내고 이를 판매한다.

ii) 남은 막대에 대해 최적의 자르기 방법을 찾는다.

"""

 

- 이를 모든 경우를 시도하여 생각해보자.

- 막대를 어떻게 자를지 모르니, 가능한 모든 길이로 자르는 경우를 다 시도해보자.

'''

1. 길이가 1인 조각을 잘라낸 후, 남은 길이 n-1인 막대를 최적으로 자르는 방법을 계산

2. 길이가 2인 조각을 잘라낸 후, 남은 길이 n-2인 막대를 최적으로 자르는 방법을 계산

3. ...(이 과정을 길이 n 까지 반복)

'''

- 이 과정을 통해 모든 가능한 길이로 잘라서 얻을 수 있는 결과 중 최대값을 선택한다.

- 최종적으로 우리는 다음과 같은 점화식을 얻을 수 있다.

 

- 이를 코드로 나타내면 다음과 같다.

def rod_cutting(rod):
    if len(rod) == 0 :
        return 0
    q = 0
    for i in range(len(rod)):
        q = max(q,rod[i]+rod_cutting(rod[:-(i+1)]))
    return q

 

2.2. Memoization (top down approach)

- BruteForce방식으로 구현한 코드에서의 문제점은 중복된 값을 또 다시 계산한다는 것이다.

- 이를 어느한 특정 배열에 저장을 하고, 나올때마다 쓸 수 있도록 생각해보자.

def bottom_up_rod_cutting(rod):
    l = [0] * (len(rod)+1)
    for i in range(1,len(rod)+1):
        q = -1
        for j in range(i):
            q = max(q,rod[j] + l[i-j-1])
        l[i] = q
    return l[-1]