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

지난 포스팅에서 동적 프로그래밍(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이 커질수록 소요시간이 증가되는 것을 볼 수 있습니다.

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

import random
import time
 
# Init price table 
def Initprice():
    Initprice = [0,2,5,8,9,10] # n이 0~5일때까지를 미리 입력
    for i in range(6,2001): # n이 2000일때 까지의 값을 설정
        k=random.randrange(1,4) # 1부터 3중 하나의 정수 값을 랜덤으로 얻음
        r=k*random.random() # 1~3중 랜덤으로 얻은 정수 값에 0~1 중 하나의 값과 곱함 
        while( Initprice[i-1] > i*r ): # 단조증가형태로 price table이 구현되어야 함
            k=random.randrange(1,4) 
            r=k*random.random()
        Initprice.append(int(i*r)) # 랜덤으로 얻은 값을 table에 추가
    file_price = open("price_table.txt",'w') # 파일로 저장하는 코드
    for i in range(0,2000):
        file_price.write(str(Initprice[i])+",")
    file_price.write(str(Initprice[2000]))
 
def readPriceTable(): # 작성된 price table를 읽는 함수
    file_price = open("price_table.txt",'r')
    data = file_price.read()
    temp = data.split(',')
    price = list(map(int,temp))
    return price
 
def BottomUP(p,n): #Bottom-UP 방식으로 Rod-Cutting problem 해결
    r = []
    for i in range(0,n+1): # n의 크기만큼의 사이즈를 갖는 r-table 초기화
        r.append(0)
    for j in range(1,n+1): # n이 1일때부터의 최적의 값을 조사하여 r-table에 저장
        q = float('-inf') # q의 초기값은 음의 무한대
        for i in range(1,j+1):
            q = max([q,p[i]+r[j-i]])
        r[j] = q
    return r[n] # r-table은 각각의 n의 크기에서 최적의 값을 갖는 값을 저장중.
                # 따라서 r[n]을 반환 
 
def BruteForce(p,n): #Brute-force 방식으로 Rod-Cutting problem 해결
    if n==0:
        return 0
    q = float('-inf')
    for i in range(1,n+1):
        q = max([q,p[i]+BruteForce(p,n-i)]) # 단순 재귀호출
    return q
 
def check(n,price): # Bottom-UP 방식과 Brute-force 방식을 동시에 확인
    file1 = open("BottomUP_1.txt",'a') # 확인 결과는 파일로 기록
    file2 = open("Bf_1.txt",'a')
    # n 일때 Bottom-UP 방식 시간 측정
    start_time1 = time.time() 
    price1 = BottomUP(price,n)
    time1 = time.time() - start_time1
    # n 일때 Brute-force 방식 시간 측정
    start_time2 = time.time()
    price2 = BruteForce(price,n)
    time2 = time.time() - start_time2
    print("| n = %-6d |  %17f s 소요 / 결과 = %4d  ||  %17f s 소요 / 결과 = %4d  |" %(n,time1,price1,time2,price2))
    print("-----------------------------------------------------------------------------------------------------")
    file1.write(str(time1)+"\n")
    file2.write(str(time2)+"\n")
 
def checkBtUP(n,price): # Bottom-UP 방식만 확인
    file1 = open("BottomUP_1_1.txt",'a')
    # n 일때 Bottom-UP 방식 시간 측정
    start_time1 = time.time() 
    price1 = BottomUP(price,n)
    time1 = time.time() - start_time1
    print("| n = %-6d |  %17f s 소요 / 결과 = %4d  ||     --------------------------------     |" %(n,time1,price1))
    print("-----------------------------------------------------------------------------------------------------")
    file1.write(str(time1)+"\n")
 
 
 
# main
# Initprice()
print("=====================================================================================================")
print("||                            Tigercow.Door 문범우_ 알고리즘 programming 2                         ||")
price = readPriceTable()
print("=====================================================================================================")
print("|            |              Bottom-UP 방식              ||             Brute-force 방식             |")
print("=====================================================================================================")
 
for i in range(4,31):
    check(i,price)
for i in range(31,1001):
    checkBtUP(i,price)

---

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

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