Algorithm/알고리즘 이론

알고리즘 #4_ 파이썬을 통한 막대자르기(Rod cut) 시간비교

Tigercow.Door 2017. 11. 7. 10:56


지난 포스팅에서 동적 프로그래밍(Dynamic Programming)에 대해서 알아보고 그에 대한 예제로 막대자르기(Rod Cut)에 대해서 공부하였습니다.

이번 포스트에서는 막대자르기 예제에서 단순 하향식 재귀표현법과 상향식 방법을 실제로 python코드로 작성해보고 시간을 비교해보도록 하겠습니다.


1. 개요


먼저 이번 포스팅에서 진행할 막대자르기문제에 대한 몇 가지 조건은 아래와 같습니다.


ㄱ. P-table(price table)의 값은 임의의 단조증가 형태

ㄴ. Rod의 길이 값을 4부터 N으로 변화시키면서 Brute-force방법(하향식 재귀 표현)과 DP방법(상향식 방법)으로 최적의 값과 해결 소요 시간을 비교

ㄷ. 소요 시간 비교는 최종적으로 표와 그래프를 이용하여 시각적으로 표현


위의 조건들을 가지고 코드를 작성하는데, 이때 참고하는 수도코드는 각각 아래와 같습니다.


#Brute-force(하향식 재귀 표현)


#DP(상향식 방법)




2. Price table 구성


먼저 조건 ㄱ을 구현하기 위해 P-table(Price table)을 구성하는 함수를 작성합니다.

P-table은 임의의 단조증가 형태를 띄어야 합니다.

먼저 P-table를 알맞게 구성하는 Initprice()라는 함수를 작성하여 값을 price_table.txt 파일로 저장한 다음 이후 해당 파일을 읽어서 사용할 수 있도록 readPriceTable()함수를 구현하겠습니다.


2-1. Initprice()


단조증가 형태를 띄는 P-table은 아래 코드를 통해 구성됩니다.




위의 코드를 통해 생성된 price_table.txt 파일의 일부는 아래와 같습니다.




2-2. readPriceTable()


위에서 작성한 price_table.txt를 이후 코드에서 사용하기 위해 해당 파일을 읽어서 배열로써 반환하는 함수는 아래와 같습니다.




3. Brute-force, 하향식 재귀 표현


위와 같은 수도코드를 통해 Cut-Rod 방법을 구현한 함수는 아래와 같습니다.




위의 코드는 이론상으로 의 시간복잡도를 가집니다.




4. DP, 상향식 방법



위와 같은 수도코드를 통해 Bottom-UP 방법을 구현한 함수는 아래와 같습니다.



위의 코드는 이론상으로 의 시간복잡도를 가집니다.



5. 결과 출력


먼저 위에서 구현한 하향식 재귀 방법과 상향식 방법을 동시에 실행시키면서 각각을 통한 최적의 값과 실행 소요시간을 출력하는 함수를 작성하여 결과를 한눈에 보기 편하도록 하겠습니다.

check(n,price)함수를 구현하였고 매개변수 n은 최대 수익 값을 구하고자 하는 막대의 길이이며 price는 P-table입니다.

또한, n이 값이 증가하였을때 하샹식 재귀방법은 이론적으로 큰 시간 소요를 가질 것으로 예상 되므로 n이 커질때 상향식 방법만 확인하기 위한 checkBtUP(n,price) 함수를 구현하였습니다.

각각의 코드는 아래와 같습니다.



위와 같은 코드를 통해 최종적으로 아래 코드를 실행시킵니다.



이에 따른 결과의 일부는 아래 사진과  같습니다.






6. 시간비교


각각의 값을 txt파일로 기록하여 이를 excel에 옮겨서 표를 구성한 사진과 이를 그래프로 나타낸 결과는 아래 사진들과 같습니다.



위의 표는 n이 4부터 30까지의 대한 각각의 값을 나타냅니다.

두가지 알고리즘에 의한 최적의 값을 비교했을 때, 두 알고리즘 모두 같은 값을 도출하였습니다.

또한 각각의 값은 자르지 않았을 때의 값보다 크거나 같습니다.

아래 첫번째 그래프는 하향식 재귀표현 알고리즘과 상향식 방법 알고리즘에 대한 시간비교를 진행한 것 입니다. 파란색 선은 하향식 재귀 방법의 소요시간을 나타내며 주황색 선은 상향식 방법의 소요시간을 나타냅니다.

이론에서 배운 것과 같이 하향식 재귀 방법이 상향식 방법보다 n이 커질수록 큰 소요시간을 가지는 것을 확인할 수 있습니다.

그 아래 두번째 그래프는 n이 31부터 1000까지의 상향식 방법의 소요시간을 측정한 그래프 입니다.

n이 커질수록 소요시간이 증가되는 것을 볼 수 있습니다.




실습에서 진행되었던 코드 전문은 아래와 같습니다.





이렇게 해서 파이썬을 통한 막대자르기(Rod Cut) 문제의 알고리즘 시간비교를 진행하였습니다.

궁금한 점이나 내용에 대한 피드백은 언제든지 댓글을 이용해주세요 :)

728x90