TigerCow.Door


이번 포스팅에서는 동적 프로그래밍의 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)에 대해서 알아보도록 하겠습니다.


1. 행렬 체인 곱셈(Matrix-chain Multiplication)


이번 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)문제는 n개의 행렬을 곱하는 것에 대한 문제입니다.

먼저 행렬의 곱은 아래의 수도코드와 같은 방식으로 진행됩니다.



위의 수도코드를 보면 A행렬이 p*q이고 B행렬이 q*r일때, 이 두 행렬의 곱을 통한 새로운 행렬 C를 계산하는데 걸리는 시간은 수도코드의 8행에 따른 곱셈의 횟수, pqr번에 의해서 결정됩니다.

예를들어, 아래와 같은 세개의 행렬이 있을 때, 두가지 방법의 곱셈이 가능할 것입니다.



A1와 A2를 먼저 계산한다면 총 840번의 곱을 수행해야 합니다.

하지만 A2와 A3를 먼저 계산한다면 총 460번의 곱을 수행하면 됩니다.


따라서 행렬 체인 곱셈 문제에서는 행렬을 곱할 때 비용이 가장 적은 순서를 찾아내는 것이 목표입니다.



2. Brute-force 방식


지난 두 예제에서 알아본 것과 같이, 동적 프로그래밍을 적용한 해결 방법을 살펴보기전에 모든 경우의 수를 조사하는 brute-force방식을 살펴보도록 하겠습니다.

n개의 행렬을 괄호로 묶는 서로 다른 방법의 수를 P(n)이라고 함ㄴ다면, n이 1일 때에는 행렬이 한 개뿐인 것이므로 괄호를 묶는 방법은 단 한가지 입니다. n이 2보다 크거나 같을 때, 행렬 전체를 완전하게 괄호로 묶는 방법의 수는 두개의 완전하게 괄호로 묶인 두 부분 곱들의 곱이고, 두 개의 부분 곱 사이를 나누는 것은 1과 n-1의 값, k번째와 k+1번째 행렬의 사이가 됩니다. 이를 통해 아래의 점화식을 얻을 수 있습니다.



위의 식을 분석해보면 점화식의 해가 대략 개를 가지는 것을 알 수 있습니다.



3. 동적 프로그래밍으로 행렬 체인 곱셈 문제 해결하기


먼저 행렬 체인 곱셈 문제의 최적 부분 구조를 생각해보면 다음과 같습니다.

를 괄호로 최적으로 묶기 위해 와 의 사이에서 나눈다고 생각해보겠습니다. 그렇다면 앞의 부분 곱, 을 확인하였을 때, 의 괄호 묶는 방법은 의 최적의 괄호 묶는 방법으로 되어야 할 것 입니다.


즉, 최적의 괄호를 묶기 위해서 부분 곱에서 또한 같은 특징이 성립되어 부분 곱도 괄호 묶기에 대해 서로 최적이어야 합니다.


따라서 m[i,j]는 다음과 같이 정의됩니다.



그리고 m[i,j]는 다음과 같은 점화식을 통해 값이 구성됩니다.



이렇게 구한 m은 행렬 곱셈을 계산하는데 필요한 최적의 계산 수를 저장합니다.

하지만 행렬을 곱하는 방법을 제공하지는 않기에 우리는 s라는 배열을 사용하여 필요한 정보를 저장합니다.


s[i,j] 에는 Ai행렬부터 Aj까지의 행렬을 곱할 때 마지막으로 괄호 묶기가 되는 와  의 k값을 저장합니다.


이러한 테이블과 점화식을 토대로 행렬 체인 곱셈문제를 해결하는 알고리즘은 다음과 같습니다.




위의 수도코드에서 4번라인까지는 테이블 m을 초기화하는 과정입니다.(길이가 1인 행렬 곱셈에 대한 최소비용은 0이므로)

이후 5번 라인에서 반복문이 시작되며 처음엔, i가 1부터 n-1까지 증가하는 동안 길이가 2인 행렬에 대한 최소 비용을 구하며, 두번째 반복에서는 i가 1부터 n-2까지 증가하는 동안 길이가 3인 행렬에 대한 최소비용을 구합니다. 이런식으로 반복문이 진행되고 이를 통해 수도코드의 총 시간복잡도는 이며, 테이블 m과 s를 저장하기 위해 필요한 공간 복잡도는 입니다.


A1부터 A6행렬까지 있는 곱셈을 계산하였을때 작성되는 테이블 m과 s는 아래와 같으며 중간 계산 중 일부가 아래에 나와 있으니 확인하시고 확실히 이해 하시길 바랍니다.




이렇게 해서 동적 프로그래밍의 세번째 예제, 행렬 체인 곱셈(Matrix-chain Multiplication)에 대해서도 알아보았습니다.

특히나 저는 행렬 체인 곱셈이 많이 헷갈리고 어려웠기에 추가적으로 확인하면서 더 간단하게 설명이 되는 부분은 수정하도록 하겠습니다.

이해가 잘 안되거나 궁금한 점은 언제든 댓글을 남겨주세요 :)


블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

안녕하세요.

이번 포스팅에서는 동적 프로그래밍(Dynamic Programming)의 예제인 Assembly Line Scheduling과 Matrix-chain Multiplication에 대해서 알아보도록 하겠습니다. 동적 프로그래밍과 막대자르기(Rod-Cutting)예제에 대한 내용은 지난포스트를 확인해주시길 바랍니다.


1. Assembly Line Scheduling


먼저 Assembly Line Scheduling 예제에 대한 설명을 하겠습니다.



위와 같은 사진을 참고하여 어느 특정 공장에 두 개의 라인이 있습니다.

그림에서는 위의 라인이 S1, 아래의 라인이 S2입니다.

그리고 각각의 라인에서 진행되는 1부터 n까지의 공정이 있습니다.

이때 같은 열에 있는 공정은 같은 공정이지만 라인에 따른 시간차이가 있습니다.

또한, 위 또는 아래의 라인에서 다른 라인으로 넘어 가는데 소요되는 시간 t가 존재합니다.

이때, 같은 라인에서 넘어가는 시간은 0이라고 가정합니다.

즉, S1,1에서 S2,2로 넘어가는 시간은 t1,2 입니다. 또한 S1,1에서 S1,2로 넘어가는 시간은 0입니다.


각각의 기호에 대한 개념을 정리하면 아래와 같습니다.

 : i라인에서의 j번쨰 공정(j-th station on line i)

 : 에서 공정에 소요되는 시간(assembly time required at station )

 : i 라인으로 들어가는데 소요되는 시간(time to enter line i)

 : i 라인에서 나오는데 소요되는 시간(time to exit line i)

 : j 번째 공정을 하고 i 라인에서 다른 라인으로 교체되는 시간(time to transfer from line i after station j)



예들 들어 보겠습니다.

먼저, 위의 라인으로 들어가는 시간 e1은 0.5초, 아래의 라인으로 들어가는 시간 e2는 1초로 가정합니다.

그리고 위의 라인에서 진행되는 첫번째 공정은 S1,1로 표현하며 여기서 진행되는 공정 a1,1는 1초가 걸린다고 가정하겠습니다.

그리고 아래의 라인에서 진행되는 첫번째 공정은 S2,1로 표현하며 여기서 진행되는 공정 a2,1는 2초가 걸린다고 가정하겠습니다.

같은 방식으로 a1,2는 4초, a2,2는 3초가 걸린다고 가정하겠습니다. 또한 t1,2는 0.5초이며 t2,2는 3초라고 가정하겠습니다.

정리해보면 아래와 같습니다.

e1 = 0.5s

e2 = 1s

a1,1 = 1s

a2,1 = 2s

a1,2 = 4s

a2,2 = 3s

t1,2 = 0.5s

t2,2 = 3s

위와 같은 조건이 있을때 두번째 공정까지 진행하는 최단시간과 그 과정은 어떻게 될까요?

이러한 문제를 해결하는 것이, Assembly Line Scheduling 입니다.


위의 예제를 하나씩 확인해보겠습니다.

먼저 첫번째 공정을 마무리하는 시점을 생각해보면 S1,1 는 e1+a1,1 = 1.5s 이며 S2,1는 e2+a2,1 = 3s 입니다.

그리고 두번째 공정에 대해서 생각해보겠습니다.

만약 S1,2에서 공정을 진행한다고 가정하면, e1+a1,1+a1,2 = 5.5s 또는 e2+a2,1+t2,2+a1,2 = 10s 입니다.

그리고 S2,2에서 공정을 진행한다고 가정하면, e1+a1,1+t1,2+a2,2 = 5s 또는 e2+a2,1+a2,2 = 6s 입니다.

가장 최단시간이 걸리는 것은 5초의 과정을 가진 e1 + a1,1 + t1,2 + a2,2 입니다.



2. Brute-force


Assembly Line Scheduling에 대한 알고리즘을 고민해봅시다.

최적의 답을 찾기 위해서 전체의 경우의 수를 고려해보면 어떨까요?

n개의 공정이 존재할 때, 2개의 라인이 존재하므로 총 개의 경우의 수를 고려해야 합니다.

쉽게 말해서, S1,4의 공정을 수행하는데 오는 경로는 S1,3과 S2,3이 있는 것을 통해 특정 위치의 공정을 위한 경로를 확인하면 2개씩 존재하고, 공정의 개수는 총 n개이므로 총 개를 확인해야 하는 것 입니다.

즉, 이러한 모든 경우의 수를 탐색하는 Brute-force Approach로는 다음과 같은 시간복잡도를 가집니다.


In Brute-force Approach, 


이러한 Brute-force 방식은 상당히 많은 소요시간을 가지는 것을 지난 막대자르기 예제에서 확인 할 수 있었습니다.

뒤에서 수도코드를 확인하면서 설명드리겠지만,

동적 프로그래밍을 통해 해당 Assembly Line Scheduling 문제를 선형시간에 탐색할 수 있습니다.

따라서 동적 프로그래밍으로 알고리즘을 구현해보도록 합니다.



3. 동적 프로그래밍에 의한 Assembly Line Scheduling 해결


지난 포스팅에서 이야기 했던 것 처럼, 동적 프로그래밍의 기본 핵심은 테이블을 사용하는 것 입니다.

따라서 우리는 모든 경우에 수에 대해 탐색하는 것이 아니라, 탐색한 경우에 대해서는 테이블에 저장하여 필요할 때 값을 참조하도록 합니다.



위의 사진에 나와있듯이, 사용하는 테이블 의 의미는, i라인에서 진행하는 j 공정(=Si,j)을 시작지점으로 했을 때 가장 빠른 시간입니다.

즉 우리는 다룬 위의 예제에서는 2개의 라인을 이용하므로 f1과 f2가 테이블로 존재할 것입니다.

그리고 f*는 최종적으로 가장 빠른 시간을 저장하는 변수 입니다.

이때 f*는 다음과 같은 식으로 결정 됩니다.



그리고 각각의 테이블을 구성하는 방법은 다음과 같습니다.



또한 이후 수도코드에서 보게될 L테이블이 있습니다.

이는 최종적으로 Assembly Line Scheduling의 과정을 보여주기 위한 테이블입니다.

즉, l1[3]에 입력되는 값은, S1,3에 오는데 어떠한 라인에서 오는 것이 최적인지를 구분한 라인의 번호입니다.


이를 통해 최종적으로 구성되는 수도코드는 아래와 같습니다.



위의 수도코드를 확인해보면,

f1[1]과 f2[1]에 enter하는데 필요한 소요시간과 1번 공정을 하는데 소요되는 시간을 더해서 입력합니다.

이후, 2번 공정부터 n번째 공정까지 f1과 f2의 테이블에 적절한 값을 입력할 수 있도록 if문을 통한 처리를 진행합니다.

내부에서는 추가적인 반복문 없이 진행됩니다.

그리고 최종적으로 n번째 공정까지 마무리가 되면 라인에서 빠져나오는 시간을 고려하여 가장 소요시간이 적은 값을 f*에 저장합니다.

이를 통해서 해당 수도코드의 시간 복잡도는 선형시간을 가진다는 것을 알 수 있습니다.

 

또한 최종 과정을 보기위한 출력함수는 아래와 같습니다.



위의 수도코드들을 통해 아래 사진을 보고 그 과정을 하나씩 확인해보시면 이해가 빠를 것 입니다.




이렇게 해서 동적 프로그래밍, 동적 계획법의 두번째 예제인 Assembly Line Scheduling에 대해서 알아보았습니다.

다음 포스팅에서는 동적 프로그래밍의 세번째 예제인 Matrix-chain Multiplication에 대해서 알아보도록 하겠습니다.

블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc


지난 포스팅에서 동적 프로그래밍(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) 문제의 알고리즘 시간비교를 진행하였습니다.

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

블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc



안녕하세요. 문범우입니다.

이번 포스팅부터 Introduction to Algorithm (3rd Edition) 책의 15장. 동적 프로그래밍(ch15, dynamic programming)에 대해서 이야기하려 합니다.

매주 1~2번 정도 포스팅 될 예정이며, 공부를 하면서 내용을 정리해서 올리기 때문에 잘못된 정보나 지식이 포함되어 있을 수 있으니 참고용으로 확인해주시고, 잘못된 내용에 대해서는 피드백 주시면 감사하겠습니다.

오늘은 동적 프로그래밍에 대한 개요와 동적 프로그래밍의 막대 자르기(Rod Cut)에 대해서 알아보겠습니다.


1. 동적 프로그래밍(Dynamic programming)


동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합하여 문제를 해결합니다.

이때, 프로그래밍이란 것은 코딩을 하는 것이 아니라 테이블을 이용하여 문제를 해결하는 방법을 말합니다.

동적 프로그래밍은, 동적 계획법, Dynamic programming, DP 등으로 부르기도 합니다.


분할정복 알고리즘은 기본적으로, 하나의 문제를 겹치지 않는 부분 문제들로 분할(divide)하여 해당 부분 문제들을 재귀적으로 해결한 후, 각각의 결과를 다시 결합하여 원래의 문제를 해결합니다.

반면, 동적 프로그래밍에서는 부분 문제가 서로 중복될 떄, 즉 부분 문제가 다시 부분 문제를 공유할 때 적용됩니다.

동적 프로그래밍 알고리즘을 이용하여 부분 문제를 한번만 해결하고 그 해를 테이블에 저장함으로써 각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있습니다.


일반적으로 최적화 문제(Optimization problem)에서 동적 프로그래밍을 적용합니다.

최적화 문제에서는 대체적으로 다양한 해를 가질 수 있는데 우리는 다양한 해들 중에서 최적(최소 또는 최대)의 해를 찾기를 원합니다. 이러한 해를 그 문제에 대한 유일한 최적해라고 하지 않고, 한 개의 최적해라 합니다. 최적의 값을 가지는 해가 여러개 존재할 수 있기 때문이죠.

동적 프로그래밍 알고리즘을 개발할 때는 아래의 4단계를 따릅니다.


1. 최적해의 구조의 특징을 찾는다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산한다.

4. 계산된 정보들로부터 최적해를 구성한다.


1~3 단계는 주어진 문제에 대한 동적 프로그래밍 해의 기초가 됩니다.

이어서 4 단계에서는 최적해의 값만 필요한 것이 아니라 최적해 자체가 필요할 때 수행하는 것으로써 값만 필요할때에는 생략할 수 있습니다.


2. 막대 자르기


막대 자르기 문제는 다음과 같습니다.

길이가 n인 막대와 i = 1,2,3,...,n에 대한 가격 p_i의 표가 주어지면 해당 막대를 잘라서 판매했을떄 얻을 수 있는 최대수익 r_n을 결정하는 것 입니다. 길이가 n인 막대의 가격 p_n이 충분히 비싸면 최적해는 자르지 않은 것일 수도 있습니다.


아래 표와 그림을 통해 확인해보겠습니다.


표에는 막대의 길이가 얼마일 때, 얼마의 가격인지가 나와 있습니다.

그리고 아래 그림에서 막대를 다양한 방법으로 잘라, 그 가격을 나타내고 있습니다.

(a) ~ (h)를 봤을 때 어떤 경우가 최적의 해 인가요?

막대를 2의 길이, 두 개로 자른 (c)의 경우의 수익이 10으로써 가장 최적의 해를 나타내고 있습니다.


위와 같이, 길이가 n인 막대는 개의 다른 방법으로 자를 수 있습니다.

제일 좌측에서 부터 i = 1,2,3,...,n-1 에 대한 모든 i길이마다 자르거나 자르지 않거나 하는 독립적인 선택이 가능하기 때문입니다.

만약 최적해가 막대를 에 대해 k의 조각으로 나누면,

막대를 조각 길이 로 나누는 다음의 최적의 분해는

 이며,

다음과 같은 최대의 해당 수익을 제공합니다.


좀 더 일반적으로 말하면, 에 대한  값을 더 작은 막대로부터의 최대 수익을 이용해 나타낼 수 있습니다.



첫 번째 인자 은 자르지 않고 길이가 n인 막대를 그대로 파는 것에 해당합니다.()

max 함수에 대한 다른 인자는 막대를 처음에 i와 n-i의 길이가 되도록 둘로 나누고 두 조각을 더 최적으로 잘라서 두 조각으로부터 최적의 이익을 얻습니다. 그런데 어떤 i의 값이 최대의 수익을 가져오는지 미리 알 수 없기 때문에 i에 대한 모든 가능한 값을 고려해야 합니다.


다시말해서, 크기가 n인 원래 문제를 풀기 위해서 종류가 같은 더 작은 크기의 문제를 풉니다.

처음에 자르기를 진행하여 도출된 두 가지의 문제는 서로 독립적인 예로 생각해도 됩니다.

전체적인 최적해는 두 부분 문제의 각각에 대해 수익을 최대화하는 해를 이용합니다.

이에 따라 막대 자르기 문제는 최적 부분구조(Optimal substructure)를 가졌다고 말합니다.

따라서 길이가 n인 막대의 모든 분해를 첫 번째 조각과 나머지 조각의 어떤 분해로 볼 수 있습니다. 그렇게 할 때는 막대를 전혀 자르지 않는 방법의 해를 포함하여 좀 더 간단한, 아래와 같은 식을 얻을 수 있습니다.



우리는 위의 식을 토대로 몇 가지 알고리즘을 구현해보도록 하겠습니다.


2-1. 하향식 재귀의 표현


알고리즘의 의사코드는 아래와 같습니다.



위의 CUT-ROD 의사코드에 대해 간략히 확인해볼까요?

길이 n이 0인 막대기는 당연히 0을 반환합니다.

그리고 그것이 아닐때에, 최대 수익 q를 음의 무한대로 초기화를 진행하고 i가 1부터 n까지 값으로 재귀 함수를 호출합니다.

이러한 알고리즘의 총 수행시간은,

   

입니다.


CUT-ROD 알고리즘이 위와 같은 수행시간을 보이듯, 비효율적인 이유는 무엇일까요?

그것은 CUT-ROD 알고리즘이 같은 인자를 똑같이 반복해서 계산하려고 하기 때문입니다.

아래의 트리를 보면 이해하기 쉬울 것 입니다.

n=4 일때를 보여주는 위의 트리에서, 재귀적으로 호출되는 함수 때문에 n=1 일때, n=2일때의 경우가 반복되서 호출되고 있습니다. 

즉 CUT-ROD 함수에서는 길이가 n인 막대를 자르는 데 가능한 개의 경우의 수를 모두 고려하고 있는 것 입니다.



3. 동적 프로그래밍을 이용한 최적의 막대 자르기


이제 1에서 알아보았던 동적 프로그래밍을 이용하여 막대 자르기 문제를 효율적으로 해결해보록 하겠습니다.

동적 프로그래밍은 위에서 알아본 바와 같이, 각 부분 문제를 단 한번만 풀고 그 해를 저장하도록 처리합니다.

그렇게 함으로써 반복되는 부분 문제의 해를 구할 떄 다시 계산하지 않고 저장된 값을 참조만 함으로써 시간소요를 줄일 수 있습니다. 하지만 이렇게 동적 프로그래밍은 시간을 절약하기 위해 부가적인 메모리를 사용합니다.

이것은 시간-메모리 트레이드 오프(Time-memory trade-off)의 한가지 예로써 작용합니다.


막대자르기 문제를 동적 프로그래밍 방법으로 해결하는데 있어서 크게 두 가지 방법이 존재합니다.

하나는 메모하기를 이용한 하향식 방법, 다른 하나는 상향식 방법입니다.



3-1. 메모하기를 이용한 하향식


메모하기를 이용한 하향식의 기본 개념은 2-1에서 진행한 하향식 재귀와 비슷합니다.

하지만 특정 부분 문제를 해결하였을때 해당 부분 문제의 해를 배열이나 해시 테이블에 저장해놓도록 수정하여 이후 같은 부분 문제가 반복되었을때 다시 계산하지 않고 배열이나 해시 테이블을 참조하여 이용할 수 있도록 함으로써 시간을 절약합니다.

아래는 메모하기가 더해진 하향식 CUT-ROD 의 의사코드입니다.

메인 알고리즘, MEMOIZED-CUT-ROD는 새로운 배열 r[]을 선언하고 음의 무한대로 초기화 합니다.

배열 r의 구성은, 특정 길이 n'에 대한 최적의 해를 r[n']에 저장합니다.

그리고 길이 n에 대해서 MEMOIZED-CUT-ROD-AUX 함수가 호출이 됩니다.

그리고 1행에서 길이 n에 대한 최적의 해가 존재하다면 그것을 리턴하게 됩니다.

(초기에 배열 r[]을 음의 무한대로 초기화 하였으니 특정 길이 n'에 대하여 r[n']의 값이 0보다 크거나 같다면 길이 n'에 대한 최적의 해가 저장되어 있다는 것을 알 수 있습니다.)

계산되어 있지 않다면 이후 3행부터는 2-1에서 진행한 하향식 재귀함수와 동일합니다.



3-2. 상향식 방법


상향식 방법은 보다 간단합니다.

상향식 방법에서는 동적 프로그래밍 방법에서 부분 문제의 자연스러운 순서를 사용합니다.

만약 i > j 이라면 크기 i의 부분 문제는 크기 j 의 부분 문제보다 작습니다. 그러므로 해당 상향식 방법에서는 크기가 0부터 n으로 커지는 부분 문제의 크기 순으로 해결합니다.


수도코드의 1행에서 배열 r[]에 대해서 선언하고 이후 우리는 r[] 배열에 부분 문제의 결과를 저장할 것 입니다.

그리고 길이가 0인 막대에 대한 최대 수익은 0 이므로 2행에서 r[0]=0 으로 저장합니다.

3행에서부터는 길이가 1부터 j까지 하나씩 증가하는 각 부분 문제를 해결하여 값을 구하고 그것의 값을 7행에서 배열 r[]에 저장합니다.

마지막 8행에서 우리가 얻고자 하는 길이 n에 대한 최대 수익값을 리턴하게 됩니다.

이러한 상향식 방법의 수행시간은 을 가집니다.



3-3. 해의 재구성


우리가 위에서 공부한 두가지 알고리즘에서는 최적 해의 대한 값만 도출합니다.

즉, 길이가 n에 대한 막대를 통해 얻을 수 있는 최대 수익만을 반환할 뿐이지 해당 막대를 어떻게 잘라야 하는지는 리턴하지 않습니다.

이러한 동적 프로그래밍 방법을 각각의 부분 문제에 대한 계산된 최적 값 뿐만 아니라, 그 최적 값에 이르는 선택도 기록하도록 확장할 수 있습니다. 즉 이러한 정보와 함께 최적 값 뿐 아니라 최적해 자체를 쉽게 출력할 수 있습니다.



위의 수도코드에서는 그 전과 다르게 1행에서 배열 s[]를 선언합니다. 그리고 8행을 확인하시면 잘라내는 첫번째 조각의 최적크기 i를 보관하는 것을 알 수 있습니다.

그리고 최적 해를 가지는 r과 최적의 첫 번째 막대 크기들의 배열 s[]을 반환합니다.

아래 수도코드는 길이 n의 막대의 최적 분할에서의 모든 조각 크기의 리스트를 함께 출력합니다.





이렇게 해서 동적프로그래밍에 대한 개요와 하나의 예제인 막대 자르기(Rod-cutting) 에 대해서 공부해보았습니다.

추가적으로 궁금하신 점이나 피드백해주실 점은 댓글 또는 이메일(doorbw@outlook.com)을 이용해주세요 :)



블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc