정답을 보시기 전에 : 여기를 클릭해서 한번 연습해 보세요. 문제는 다르지만 더욱 쉬운 자르기 문제 입니다.
이 문제를 푸는 가장 기초적인 방법은 막대를 자르는 모든 방법을 나열한다음 그중에서 가장 최고의 값을 가진 방법을 찾는것입니다. 이 솔루션은 지수형의 시간복잡도를 가집니다. 별로 좋은 방법은 아닙니다. 동적 계획법이 활약할 차례라고 생각합니다.
1) 최적의 서브구조 : 우리는 막대기를 다른 여러 방법으로 자른 다음 그 값들을 비교하여 최고의 값을 찾아낼 수 있습니다. 잘라낸 막대는 다시 함수를 통해 재귀적으로 호출할 수 있구요.
cutRoad(n) 은 n 인치의 나무를 잘랐을때 얻을 수 있는 최고의 값이라고 가정하겠습니다. cutRod(n) 은 다음과 같이 작성됩니다.
$cutRod(n) = max(cutRod(n), price[i] + cutRod(n-i-1))$ for all i in {0, 1 ... n-1}
거꾸로 생각해보면 편합니다. $cutRod(n-i-1) = cutRod(n-(i+1))$, 즉, i+1 인치만큼 잘린 막대기에서 얻을 수 있는 최대 값에 i+1 인치 만큼 막대기를 붙여줬을때 n 인치가 됬을때 기존의 cutRod(n) 의 값보다 크냐? 작냐? 이것을 찾는 구문입니다.
처음에 cutRod(n) 은 0 보다 작은 값이 설정되어 있습니다. 그래서 위와같은 비교는 의미가 없다라고 생각하실 수 있습니다. 하지만 n-1 인치에서 1 인치를 붙여줘서 n 인치가 된 값과 n-2 인치에서 2 인치를 붙여줘서 n 인치가 된 값은 cutRod(n) 의 차이가 있기 때문에 분명 후에는 누가더 큰지 비교를 해야되는 상황이 옵니다. 이때 max 함수가 활약을 하게 됩니다.
2) 중복되는 서브 문제들 : 아래에 작성된 코드는 단순 재귀를 이용한 막대기 자르기 문제의 해결 코드 입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# A Naive recursive solution
# for Rod cutting problem
import sys
# 두개의 정수중에서 큰값을 찾는 함수
def max(a, b):
return a if (a > b) else b
# n 인치의 막대기에서 얻을 수 있는 최고의 값을 반환한다.
# 그리고 price[] 는 각각 다른 막대기의 값을 가지고 있다.
def cutRod(price, n):
if(n <=0):
return0
max_val =-sys.maxsize-1
# 재귀적으로 막대기를 다른 길이로 자른다.
# 그리고 나온 다른 값들을 비교한다.
for i inrange(0, n):
max_val = max(max_val, price[i] +
cutRod(price, n - i -1))
return max_val
# Driver code
arr = [1, 5, 8, 9, 10, 17, 17, 20]
size =len(arr)
print("Maximum Obtainable Value is", cutRod(arr, size))
막대기의 길이가 4 라고 가정하고 위의 코드를 실행했을때 재귀 트리의 생김새는 다음과 같습니다.
위의 재귀 트리를 보시면 cR(2) 의 함수가 두번 호출되는것을 볼 수 있습니다. 뿐만 아니라, 많은 cR 함수가 중복된 매개변수를 가지고 호출되고 있다는 사실을 볼 수 있습니다. 같은 서브문제들을 계속해서 호출하는 문제가 있기때문에 이 알고리즘 문제는 중복되는 서브문제 성질(Overlapping Subproblems property)를 가지고 있다고 말합니다. 결과적으로 막대기 자르기 문제는 DP 의 두가지 성질을 모두 가지고 있습니다. 다른 DP 문제를 푸는 방식처럼, 임시 배열 val[] 을 만들어줌으로써 bottom up 방식을 이용해 같은 서브 문제들을 재계산하는것을 방지할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 막대기 자르기의 Dynamic Programming 솔루션
INT_MIN =-32767
# n 인치의 막대기에서 얻을 수 있는 최고의 값을 반환한다.
# 그리고 price[] 는 각각 다른 막대기의 값을 가지고 있다.
def cutRod(price, n):
val = [0for x inrange(n+1)]
val[0] =0
# 테이블 val[] 을 만들고 bottom up 방식을 이용함.
# 테이블의 마지막 결과값을 반환함.
for i inrange(1, n+1):
max_val = INT_MIN
for j inrange(i):
max_val = max(max_val, price[j] + val[i-j-1])
val[i] = max_val
return val[n]
# Driver program to test above functions
arr = [1, 5, 8, 9, 10, 17, 17, 20]
size =len(arr)
print("Maximum Obtainable Value is "+str(cutRod(arr, size)))
