2022. 10. 24. 22:25ㆍAlgorithm
본 포스팅을 한양대학교 박희진 교수님의 알고리즘 및 문제해결을 정리한 포스팅이다. 교수님이 만든 ppt... 올려도 되는 거겠지...? 교수님 사랑합니다 사랑합니다 사랑합니다. 3번 외쳤으니 됨.
1. Assembly - line scheduling 이란?
Assembly line은 말 그대로 조립라인을 말한다.

하나의 조립과정에 n개의 단계(Si)가 있고 각 단계에서 ai 의 조립시간이 걸린다. 수많은 조립라인 중 가장 빠른 조립시간을 결정하는 것이 assembly - line scheduling의 문제이다.
2. Brute - force approach
Brute : 무식한 / 짐승같은 & force : 힘 & approach : 접근
말 그대로 무식하게 가능한 경우의 수 하나하나 열거한 후 가장 좋은/빠른 경우를 찾아내는 방법이다.
위에 제시된 Assembly - line 문제에는 Input 에서 다음 단계로 넘어갈 때 / n-1번째 단계에서 n번째 단계로 넘어갈 때 모두 2가지 방법이 있다.
EX ) a[1][n-1] => a[1][n] 혹은 a[2][n]으로 가느냐
그렇기 때문에 전체 계산해야 하는 possible ways 가 2^n이기 때문에 너무 많이진다.
이때 동적 프로그래밍 (Dynamic Programming)을 사용할 수 있다. 하나의 큰 문제를 풀기 위해서 작은 여러개의 문제를 풀어 합쳐야 하는 경우가 있다. 그런데 작은 여러개의 문제를 풀 때 중복되는 계산이 있다면, 중복되는 계산을 저장해 둔다면 훨씬 빨리 계산할 수 있을 것 이다. 이게 동적 프로그래밍이다.
3. Assembly - line 문제를 동적 프로그래밍으로 푸는 방법

- 우선 S[1][1]을 보자. S[1][1]에 도달하는 방법은 enters에서 바로 오는 방법 밖에 없다.
- 2 + 7 = 9 가 S[1][1]에 저장된다.
- 같은 방식으로 S[2][1]에는 4 + 8 = 12가 저장된다.
- 다음으로 S[1][2]를 보자. a[1][2]에 올 수 있는 방법은 2가지이다. 바로 a[1][1]에서 오는 방법과 a[2][1]에서 오는 방법이다. 이 2가지 방법을 모두 계산해서 가장 빠른 방법을 S[1][2]에 저장하면 된다.
- a[1][1]에서 오는 방법 : 9 + 9 = 18
- a[2][1]에서 오는 방법 : 12 + 2 + 9 = 23
- 두가지 방법 중 더 빠른 18을 S[1][2]에 저장한다.
- 이런 식으로 S[1 or 2][n-1] 에 최소의 값을 저장해두고, S[1 or 2][n]의 값을 계산하여, 중복되는 계산을 하지 않고 빨리 답을 찾아낼 수 있다.

- 다음과 같이 그림 위에 그리면 알아보기 힘드니, 다음과 같이 S표를 그릴 수 있다. 다만 이 표만을 가지고는 fastest way를 찾기 힘들기 때문에 L표도 함께 그린다.
- L표는 해당 S[1 or 2][n]의 전 값이 a[1][n-1]인지 a[2][n1]인지 알려주는 표이다.


- L표를 읽으면 fastest way를 찾을 수 있고, S표를 통해 그 값이 무엇인지 계산할 수 있다.

4. Assembly - line scheduling 수도코드



- 수도코드는 알아서 이해하자!
- FASTEST- WAY
- a : a번째 time
- t : transfer time
- e : entry time
- x : output time
- n : number of steps
- l : L표
- s : S표
- FASTEST- WAY
5. Assembly - line schedulint Space consumption & Running time
- Space Consumption

- Running Time

5. Assembly - line schedulint - fastest time만 구할 때 Space consumption & Running time
- Space Consumption


- Running Time
- can not reduce
'Algorithm' 카테고리의 다른 글
[Algorithm] Sorting Problem - Insertion sort, Merge sort (0) | 2022.10.26 |
---|---|
[Algorithm] Dynamic Programming (2) - Rod Cutting (0) | 2022.10.25 |