이 글에서는 막대 자르기(Rod Cutting) 문제를 파이썬으로 해결하는 방법을 단계별로 살펴보겠습니다.
문제 정의
문제: 길이가 n인 하나의 막대와, n보다 작은 각 크기 조각들의 판매 가격이 담긴 배열이 주어집니다. 이때 막대를 여러 조각으로 잘라 판매함으로써 얻을 수 있는 최대 수익을 구하는 것이 목표입니다.
접근 방법: 동적 프로그래밍
막대 자르기 문제는 부분 문제들이 서로 겹치는 특징이 있어 동적 프로그래밍(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 길이 i인 막대의 최대 수익은 다음과 같이 정의됩니다.
val[i] = max(price[j] + val[i-j-1]) (단, j = 0 ~ i-1)
즉, 첫 번째 조각의 길이를 j로 잘랐을 때의 가격과 남은 부분(i-j-1)의 최대 수익을 더한 값들 중 가장 큰 값을 선택하는 방식입니다. 이를 바텀업(Bottom-Up) 방식으로 구현하면 다음과 같습니다.
구현 예제
# 막대 자르기 문제의 동적 프로그래밍 솔루션
INT_MIN = -32767
# cut 함수
def cutRod(price, n):
val = [0 for x in range(n + 1)]
val[0] = 0
# 바텀업(bottom-up) 방식으로 계산
for i in range(1, n + 1):
max_val = INT_MIN
for j in range(i):
max_val = max(max_val, price[j] + val[i-j-1])
val[i] = max_val
return val[n]
# 메인
arr = [2, 4, 7, 9, 11, 16, 16, 21]
size = len(arr)
print("Maximum Obtainable Value is " + str(cutRod(arr, size)))
실행 결과
Maximum Obtainable Value is 21
코드 설명
위 코드에서 사용된 주요 변수들은 다음과 같습니다.
- price: 각 길이별 조각의 판매 가격이 담긴 입력 배열
- n: 막대의 전체 길이 (배열의 길이와 동일)
- val: 길이 i인 막대를 잘라 얻을 수 있는 최대 수익을 저장하는 DP 테이블
- max_val: 현재 길이 i에서 가능한 최대 수익을 임시로 저장하는 변수
모든 변수는 지역 범위(local scope) 내에서 선언되며, 함수가 호출될 때마다 독립적으로 생성됩니다.
시간 복잡도 및 공간 복잡도
- 시간 복잡도: O(n²) — 두 개의 중첩 반복문을 사용하기 때문입니다.
- 공간 복잡도: O(n) — 길이 n+1 크기의 DP 테이블 하나만 필요합니다.
단순 재귀로 풀 경우 지수 시간(Exponential Time)이 걸리지만, 동적 프로그래밍을 활용하면 다항 시간 안에 효율적으로 답을 구할 수 있습니다.
결론
이 글에서는 파이썬으로 막대 자르기 문제를 해결하는 프로그램을 만드는 방법을 배웠습니다. 동적 프로그래밍의 핵심인 '부분 문제의 최적해를 저장하고 재활용한다'는 개념을 익히면, 이와 유사한 다양한 최적화 문제(예: 배낭 문제, 최장 공통 부분 수열 등)에도 같은 접근법을 적용할 수 있습니다.