dynamic programming

dynamic programming

= big problem을 smaller prob로 쪼개는 것, 이때 각 정보를 re-use한다 (저장해두고 나중에 다시 사용함) 캐시한다 ~.~

(divide and conquer은 쪼개고 아래 정보들 다시 사용 xx. revisit안함)

---

Assembly-line scheduling

given: 두개(이상)의 assembly lines

goal: fastest assembly time and path 구하기

-> 가장 빠른 path와 그때의 time을 찾는다 !

-> 이전 노드들에서 다음 노드로 가는 가장 빠른 웨이를 찾는 방식

 

알고리즘 설명

슈도코드

 

space constumption

-> s: 2n, l:2n -> Θ(n)

 

running time

: 각 테이블에 한 요소를 채우는건 Θ(1) 인데  이걸 2n번, 2n번 하기때문에 Θ(n)

 

fastest time only

: path 구할 필요가 없으면 테이블 s에서 해당 i의 정보랑, 그 전 i의 정보만 저장하면 됨 -> 4개만 저장해서 쓰면 됨

(i의 값구할 때 그전 i의 정보만 쓰고, 구한 후에는 그 전i들의 정보 지운당 그리고 i애들 정보를 바탕으로 i+1의 값을 구한당. 2->4->2->4)

-> Θ(1) space만 필요 !! 

 

---

Rod Cutting

rod-cutting problem 

given: 길이가 n인 통나무, 통나무 길이에 따른 해당 통나무의 price 표

goal: 어캐 잘라야 최대의 수익을 낼 수 있는가!!

-> 통나무 자르는 경우의수는 2^(n-1) (머 통나무길이 4면 자를 곳은 3군데니까 2^3 = 8가지 경우의수가 있다 !)

algorithm

 

슈도코드

 

 

space consumption 

: r[i]는 n개, s[i]도 n개 !!

-> Θ(n)

running time

: 그 하나하나에서 최대 r[i]구할 때, i가 1이면 1번, i가 2면 2번, ... 7이면 7번 ... -> 1+2+3+4+..+n이 된다-> n(n+1)/2 = Θ(n^2)