[알고리즘] 동적프로그래밍: 막대자르기(Rod Cutting) 시간비교 레포트

목차

1. 개요
2. 알고리즘 및 고려사항
3. 소스코드

본문내용

1. 개요
수업시간에 이론으로 학습한 Dynamic Programming 기초를 연습합니다.
또한 연습내용으로는, Textbook에 있는 Rod-Cutting Problem으로 진행하겠습니다.
Rod-Cutting Problem은 길이가 n인 막대와 각각의 길이에 대한 가격표가 주어져있을 때, 막대를 어떻게 잘랐을 때 최고의 수익을 낼 수 있는지에 대한 문제입니다.
기본적인 내용과 알고리즘의 이론에 관한 것은 개인블로그(http://doorbw.tistory.com/28)에 정리되어있습니다.
본 과제에서 진행할 Rod-Cutting Problem에 대한 조건은 아래와 같습니다.
- P-table의 값은 임의의 단조증가 형태
- Rod의 최초 길이의 값을 4 ~ N으로 변화시키면서 DP 방법과 Brute-force방법의 계산시간을 비교
- 비교는 표+차트로 진행
- DP방법으로는 Bottom-up 방식을 사용

참고 자료

없음