[Algorithm] Dynamic Programming (1) - Assembly - line scheduling

2022. 10. 24. 22:25Algorithm

본 포스팅을 한양대학교 박희진 교수님의 알고리즘 및 문제해결을 정리한 포스팅이다. 교수님이 만든 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표

 

5.  Assembly - line schedulint Space consumption & Running time

 

  • Space Consumption

4n = Θ(n)

  • Running Time

Θ(1) * Θ(n) = Θ(n)

 

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

 

  • Space Consumption

오른쪽 그림처럼 4개의 element만 저장하면 되기 때문에 Θ(1)임

  • Running Time
    • can not reduce