User Tools

Site Tools


study:algorithms:dynamic_plan

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
study:algorithms:dynamic_plan [2013/06/14 05:26]
netpyoung
study:algorithms:dynamic_plan [2019/02/04 14:26] (current)
Line 733: Line 733:
 (defn get-max-path1 (defn get-max-path1
   [path]   [path]
-  (letfn [(get-path2 +  (let [len (count path)
-            [path n x y+    (letfn [(get-path2 [path y] 
-            (let [val (get-in path [x])+              (if (= y (dec len)) 
-              (if (= y (- n 1)) +                ​(get-in path [y x]) 
-                ​val +                (if-let [ret (get-cached [y x])] 
-                (let [ret (get-cached [y x])] +                  ret 
-                  ​(if (not (nil? ret)) +                  (caching [y x] (+ (get-in path [y x]) 
-                    ret +                                    ​(max (get-path2 path x       (+ y 1)) 
-                    ​(caching [y x] (+ val (max (get-path2 path x       (+ y 1)) +                                         ​(get-path2 path (+ x 1) (+ y 1))))))))]
-                                               ​(get-path2 path (+ x 1) (+ y 1))))))))))] +
-    (let [len (count path)]+
       (reset-cache (vec (repeat len       (reset-cache (vec (repeat len
                                 (vec (repeat len nil)))))                                 (vec (repeat len nil)))))
-      (get-path2 path len 0 0))))+      (get-path2 path 0 0))))
  
 (= (get-max-path1 a-path) 28) (= (get-max-path1 a-path) 28)
 +(= (get-max-path1 b-path) 341)
 (= (get-max-path1 b-path) 341) (= (get-max-path1 b-path) 341)
 </​code><​markdown>​ </​code><​markdown>​
Line 920: Line 919:
 -------------------------------------------------------------------------------- --------------------------------------------------------------------------------
  
-## 8.05 문제: 합친LIS(문제 ID JLIS, 난이도: 하)+## 8.05 문제: 합친LIS(문제 ID JLIS, 난이도: 하) - 일단 패스. 집중력이 부족해 문제 이해를 못함 -_-;
 * 합친 LIS (JLIS, Joined Longest Incresing Subsequence) * 합친 LIS (JLIS, Joined Longest Incresing Subsequence)
 * 두 개의 정수 수열 A와 B에서 각각 길이 0이상의 증가 부분 수열을 얻은 뒤, 이들을 크기 순서대로 합친 것을 합친 증가수열이라 부름. * 두 개의 정수 수열 A와 B에서 각각 길이 0이상의 증가 부분 수열을 얻은 뒤, 이들을 크기 순서대로 합친 것을 합친 증가수열이라 부름.
Line 933: Line 932:
  
 ## 8.07 문제: 원주율 외우기 (문제ID:​PI,​ 난이도: 하) ## 8.07 문제: 원주율 외우기 (문제ID:​PI,​ 난이도: 하)
 +
 +* 원주율 외우기.
 + - __원주율의 일부__가 입력으로 주어짐
 + - 난이도의 합을 최소화 하도록 숫자들을 __세 자리에서 다섯 자리__ 까지 끊어 읽음.
 + - __최소 난이도__는?​
 +
 +
 +| 난이도 | 경우 ​                          | 예          |
 +| ------ |--------------------------------| ------------|
 +| 1      | 모든 숫자가 같음. ​             | 3333, 5555  |
 +| 2      | 모든 숫자가 1씩 단조증가/​감소. | 23456, 3210 |
 +| 4      | 두 수가 번갈아 가며 나타남. ​   | 323, 54545  |
 +| 5      | 등차 수열을 이룸. ​             | 147, 8642   |
 +| 10     | 이 외의 모든 경우. ​            | 17912, 331  |
 +
 +
 +* ex) `12673939` => `[1267 3939]` or `[12673 939]` = `10 + 4`
 +
 +get-difficulty 함수.
 +
 +</​markdown><​code clojure>
 +;; phase 1
 +(defn is-same-numbers?​ [[h & t]]
 +  (every? #(= h %) t))
 +
 +;; phase 2
 +(defn is-inc-or-dec-1?​ [coll]
 +  (let [pairs (map list (butlast coll) (rest coll))]
 +    (or (every? (fn [[x y]] (= 1 (- y x))) pairs)
 +        (every? (fn [[x y]] (= 1 (- x y))) pairs))))
 +
 +;; phase 3
 +(defn is-repeat-fist-second?​ [coll]
 +  (let [[f s & _] coll]
 +    (every? true? (map = coll (interleave (repeat f) (repeat s))))))
 +
 +;; phase 4
 +(defn is-arithmetic-sequence?​ [coll]
 +  (let [common-difference (- (first coll) (second coll))
 +        pairs (map list (butlast coll) (rest coll))]
 +    (or (every? (fn [[x y]] (= common-difference (- y x))) pairs)
 +        (every? (fn [[x y]] (= common-difference (- x y))) pairs))))
 +
 +(defn get-difficulty [coll]
 +  (cond (is-same-numbers?​ coll)        1
 +        (is-inc-or-dec-1?​ coll)        2
 +        (is-repeat-fist-second?​ coll)  4
 +        (is-arithmetic-sequence?​ coll) 5
 +        :​otherwise ​                    10))
 +</​code><​markdown>​
  
 ## 8.08 풀이: 원주율 외우기 ## 8.08 풀이: 원주율 외우기
  
---------------------------------------------------------------------------------+</​code><​markdown>​ 
 +get-min-difficulty-from-pi'​(begin) 
 + = min (L from 3 to 5) (get-min-difficulty-from-pi' (begin + L) + classify(N begin L)) 
 +</​code><​markdown>​
  
-## 8.09 문제: Quatization (문제 ID: QUANTIZE, 난이도: 중) 
-## 8.10 풀이: Quatization 
  
 +;; 코드 8.14 원주율 외우기 문제를 해결하는 동적계획법 알고리즘. - C
 +</​markdown><​code c>
 +int memorize(int begin) {
 +  if (begin == N.size()) return 0;
 +
 +  int& ret = cache[begin];​
 +  if (ret != -1) return ret;
 +
 +  ret = INF;
 +
 +  for (int L = 3; L <= 5; ++L) {
 +    if (begin + L <= N.size())
 +      ret = min(ret, (memorize(begin + L) + classify(begin,​ begin + L - 1)));
 +  }
 +
 +  return ret;
 +}
 +</​code><​markdown>​
 +
 +
 +;; 코드 8.14 원주율 외우기 문제를 해결하는 동적계획법 알고리즘. - Clojure
 +
 +</​markdown><​code clojure>
 +;; 코드 8.14 원주율 외우기 문제를 해결하는 동적계획법 알고리즘.
 +(defn take-from-to [coll from to]
 +  (take to (drop from coll)))
 +
 +(take-from-to [10 20 30 40 50] 1 2) ;=> (20 30)
 +
 +(def ^:dynamic *cache* ​ (atom nil))
 +(defn reset-cache [r]   ​(reset! *cache* r))
 +(defn get-cached ​ [k]   (get @*cache* k))
 +(defn caching ​    [k v] (swap! *cache* assoc k v) v)
 +
 +(defn get-min-difficulty-from-pi [coll]
 +  (letfn [(get-min-difficulty-from-pi'​ [begin]
 +            (if (> begin (count coll))
 +              0
 +              (if-let [ret (get-cached begin)]
 +                ret
 +                (caching begin (apply min (for [L (range 3 (inc 5))]
 +                                            (+ (get-min-difficulty-from-pi'​ (+ begin L))
 +                                               ​(get-difficulty (take-from-to coll begin L)))))))))]
 +    (reset-cache (vec (repeat (count coll) nil)))
 +    (get-min-difficulty-from-pi'​ 0)))
 +
 +(get-min-difficulty-from-pi [1 2 3 4 1 2 3 4]) ;=> 4
 +(get-min-difficulty-from-pi [1 1 1 1 1 2 2 2]) ;=> 2
 +(get-min-difficulty-from-pi [1 2 1 2 2 2 2 2]) ;=> 5
 +(get-min-difficulty-from-pi [2 2 2 2 2 2 2 2]) ;=> 2
 +(get-min-difficulty-from-pi [1 2 6 7 3 9 3 9]) ;=> 14
 +</​code><​markdown>​
 -------------------------------------------------------------------------------- --------------------------------------------------------------------------------
  
-==== 여기까지 ​1차 목표. =======+==== 여기까지 ​2차 목표. =======
  
 +
 +## 8.09 문제: Quatization (문제 ID: QUANTIZE, 난이도: 중)
 +## 8.10 풀이: Quatization
 +--------------------------------------------------------------------------------
  
 ## 8.11 경우의 수와 확률 ## 8.11 경우의 수와 확률
Line 954: Line 1060:
  
 -------------------------------------------------------------------------------- --------------------------------------------------------------------------------
 +
 +==== 여기까지 3차 목표. =======
  
 ## 8.14 문제: 폴리오미노 (문제 ID: POLY, 난이도: 중) ## 8.14 문제: 폴리오미노 (문제 ID: POLY, 난이도: 중)
Line 963: Line 1071:
 ## 8.17 풀이: 두니발 박사의 탈옥 ## 8.17 풀이: 두니발 박사의 탈옥
  
-==== 여기까지 ​2차 목표. =======+ 
 +==== 여기까지 ​4차 목표. =======
  
  
study/algorithms/dynamic_plan.txt · Last modified: 2019/02/04 14:26 (external edit)