User Tools

Site Tools


study:algorithms:dynamic_plan

<markdown> ch08

# 08. 동적 계획법 ## 8.01 도입. - [wiki:Dynamic_programming] - In mathematics, computer science, and economics, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of [wiki:Overapping_subproblem] and [wiki:Optimal_substructure] (described below). When applicable, the method takes far less time than naive methods.

- [wiki:Overapping_subproblem] - In computer science, a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblem. - 동일한 방식을 여러번 적용해서 풀어낼 수 있는 문제들로 구성된 문제. (subproblem들이 중복)

- [wiki:Optimal_substructure] - In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem. - 하위 문제의 최적의 해로, 상위 문제의 최적의 해가 결정되는 구조.

- `동적 계획법(dynamic programming)` - 수학, 컴퓨터공학, 경제학에서, 동적계획법은 복잡한 문제를 단순한 하위문제로 나누어 풀어가는 방법을 예기한다.

* 장점 : - `memization`을 이용, 미리 저장해 놨다가 써먹으니 중복계산이 불필요. * 문제점 : - 정보를 저장해야 하는데 무얼 저장해야할지 정하는것. - 중복되는 부분 문제를 찾아내는것. - 저장해 놓은걸 해제할 시기를 정하는것.

[wiki:Dynamic_programming]: http://en.wikipedia.org/wiki/Dynamic_programming [wiki:Overapping_subproblem]: http://en.wikipedia.org/wiki/Overlapping_subproblem [wiki:Optimal_substructure]: http://en.wikipedia.org/wiki/Optimal_substructure


### 중복되는 부분 문제 - 이항갯수 (binomial coefficient) - n개의 서로 다른 원소 중에서 r개의 원소를 순서없이 골라내는 방법의 수.

;; 수학공식이용. </markdown>

;; 수학공식이용
;; 단, n!이나 r!은 계산량이 많음.
(defn factorial [n]
  (reduce * (range 1 (inc n))))
 
(defn bino-math
  [n r]
  (/ (factorial n)
     (* (factorial r) (factorial (- n r)))))
 
(= (bino-math 16 8) 12870)
(time (bino-math 16 8)) ; >> "Elapsed time: 0.205887 msecs"

<markdown>

;; 코드8.1 재귀 호출을 이용한 이항 계수의 계산. 209p </markdown>

;; 코드8.1 재귀 호출을 이용한 이항 계수의 계산. 209p
 
(defn bino
  "nCr을 반환한다"
  [n r]
  (if (or (zero? r) (= n r))
    1
    (+ (bino (- n 1) (- r 1)) (bino (- n 1) r))))
 
(= (bino 16 8) 12870)
(time (bino 16 8)) ; >> "Elapsed time: 1.270465 msecs"

<markdown>

;; 코드8.2 메모이제이션을 이용한 이항 계수의 계산. 211p </markdown>

;; 코드8.2 메모이제이션을 이용한 이항 계수의 계산. 211p
 
(def ^:dynamic *cache* (atom {}))
 
(defn string-nCr [n r] (str n "C" r))
 
(defn bino2
  [n r]
  (if (or (zero? r) (= n r))
    1
    ;; n, r로부터 string "nCr"을 얻어오고,
    (let [cache-key (string-nCr n r)]
 
      (if-let [cached-nCr (find @*cache* cache-key)]
        ;; cache["nCr"]이 있으면, cache["nCr"]을 반환하고,
        (val cached-nCr)
 
        ;; 아니면, nCr(n, r)을 계산해서, cache["nCr"] = nCr(n, r)을 넣고 반환한다.
        (let [nCr (+ (bino2 (- n 1) (- r 1)) (bino2 (- n 1) r))]
          (swap! *cache* assoc cache-key nCr)
          nCr)))))
 
 
(= (bino2 16 8) 12870)
(time (bino2 16 8)) ; >> "Elapsed time: 0.074019 msecs"
 
;; (def ^:dynamic *cache* (atom {}))
;; (bino2 4 2) ; => 6
;; *cache* ; => #<Atom@67ae2ffe: {"4C2" 6, "3C2" 3, "3C1" 3, "2C1" 2}>

<markdown>


### 메모이제이션을 적용할 수 있는 경우 * `memization`은 `referentail transparent`가 가능한 경우에 적용가능. - `memoization`: 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재사용하는 최적화 기법. - `cache`: 이미 계산한 값을 저장해 두는 메모리 장소. - `referentail transparent`: 함수의 반환 값이 입력 값만으로 결정되는것.

* 프로그래밍에서 주의점. - 전역변수. - 클래스 변수. - 입력객체(파일 등등) - 등등..


### 메모이제이션 구현 패턴 * 기저 사례 처리 * cache의 초기값 설정 * 배열일경우, ref이용. * memset을 이용 cache[]초기화


#### clojure에서는??

</markdown>

(time (bino-math 16 8)) ; >> "Elapsed time: 0.205887 msecs" - before
 
(def bino-math (memoize bino-math))
(time (bino-math 16 8)) ; >> "Elapsed time: 0.08024 msecs" - after

<markdown> clojure.core/memoize의 소스.

</markdown>

(defn memoize
  "Returns a memoized version of a referentially transparent function. The
  memoized version of the function keeps a cache of the mapping from arguments
  to results and, when calls with the same arguments are repeated often, has
  higher performance at the expense of higher memory use."
  {:added "1.0"
   :static true}
  [f]
  (let [mem (atom {})]
    (fn [& args]
      (if-let [e (find @mem args)]
        (val e)
        (let [ret (apply f args)]
          (swap! mem assoc args ret)
          ret)))))

<markdown>

atom dic에 args를 키로해서 캐슁하는것…

먼가 이상하다.

검색중 [projecteuler]를 근성으로 풀어가고 있는 [용자][blog:clojure-memoize]발견.

문제점을 확인할 수 있었음.

[projecteuler]: http://projecteuler.net/ [blog:clojure-memoize]: http://translate.google.com/translate?sl=ja&tl=ko&js=n&u=http://ypsilonbox.blogspot.kr/2011/06/clojure-memoize.html

</markdown>

;; ref: http://ypsilonbox.blogspot.kr/2011/06/clojure-memoize.html
(defn fib [n]
  (do
    (println "->"n)
    (if (<= n 1)
      n
      (+ (fib (dec n)) (fib (- n 2))))))
 
(def mem-fib (memoize fib)) ;; 예전에 문제됐던것.
(mem-fib 4)
(mem-fib 3)
(mem-fib 5)
 
(def fib (memoize fib)) ;; 현 1.5에선 문제없네?
(fib 4)
(fib 3)
(fib 5)

<markdown>

</markdown>

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; create memoised func
 
(defmacro defn-memo
  "Creates memoised function, and accessor of the memo which named -data,
   memo deletion function named -clear"
  [name arg-list & body]
  `(let [mem# (atom {})]
 
     (defn ~(symbol (str (str name) "-data")) []
       @mem#)
 
     (defn ~(symbol (str (str name) "-clear")) []
       (reset! mem# {}))
 
     (defn ~name ~arg-list
       (if-let [e# (find @mem# ~arg-list)]
          (val e#)
          (let [ret# ~@body]
              (swap! mem# assoc ~arg-list ret#)
              ret#)))))
;;
 
(defn-memo mem-fib [n]
  (do
     (println "-->" n)
     (if (<= n 1)
        n
        (+ (mem-fib (dec n)) (mem-fib (- n 2))))))
 
(mem-fib 4)
(mem-fib 3)
(mem-fib 5)
(mem-fib-data)
(mem-fib-clear)
(mem-fib-data)

<markdown>

물론 단순히 args에 의해 결정되는 memoize도 필요하나. clojure.core/memoize는 cache관리가 어렵다.

누가 해논건 없나? ⇒ [github:core.memoize](https://github.com/clojure/core.memoize) cache 정책 및 조작할 수 있는 api제공.


### 메모이제이션의 시간 복잡도 분석 * (존재하는 부분 문제의 수) x (한 부분 문제를 풀때 필요한 반복문의 수행 횟수)

</markdown>

bibo2를 보자면...
 
존재하는 부분 문제의 수. 최악의 경우는 다이아몬드를 이룰때임.
 
      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
 1 5 10 10 5 1
1 6 15 20 15 6 1
 
2C1 =>  4 - 중심이 (1 1)     - 2개
4C2 =>  9 - 중심이 (1 2 1)   - 3개
6C3 => 16 - 중심이 (1 3 3 1) - 4개
 
 
nCr의 n을 a라, 중심의 갯수를 n이라 하면
n = a/2 + 1
 
 
4C2를 예로들면
      1     - 1 * 2
     1 1    - 2 * 2
    1 2 1   - 3 * 1
     3 3 
      6
 
계산할 때 만날 수 있는 부분 문제의 수는
sigma(k = 1 ~ n) : (2 * k) - n - 1(이때 1은 자기자신)
 
 
2 * (n*(n+1)/2) - n = n^2
 
이제 n을 a/2+1로 치환하면
 
O(1/4a^2 + a + 1) = O(1/4a^2) = O(a^2).
 
캐쉬가 한번도 안된 최악의 경우이지, 됐다하면 수행시간은 더 짧아질것임.
 
nCr이 좌우 대칭인걸 생각하면 캐쉬 범위도 줄일 수 있음.

<markdown>


### 예제: 외발뛰기 (문제ID:JUMPGAME, 난이도: 하)

* n*n크기의 격자에 1에서 9까지의 정수를 쓴 게임판이 있다. * 각 칸에 적혀있는 숫자만큼, 오른쪽이나 아래로 움직일 수 있다. * (0,0)에서 (n-1, n-1)까지 도달하는 방법이 존재하는가?

#### 재귀 호출에서 시작하기

;; 코드8.4 외발 뛰기 문제를 해결하는 재귀 호출 알고리즘. 216p </markdown>

;; 예제: 외발 뛰기 (문제ID:JUMPGAME, 난이도:하)
;; 코드8.4 외발 뛰기 문제를 해결하는 재귀 호출 알고리즘. 216p
;; x: left-to-right
;; y: up-to-down
(defn try-jump
  [n board]
 
  (defn board-xy [x y] (get-in board [y x]))
 
  (defn jump
    [x y]
    (cond (or (>= x n) (>= y n)) false
          (and (= x (- n 1)) (= y (- n 1))) true
          :else (let [jump-size (board-xy x y)
                      x-jump (jump (+ x jump-size) y)
                      y-jump (jump x (+ y jump-size))]
                  ;; (when (or x-jump y-jump)
                  (println (format "jump %d,%d (%d) : %s-%s" x y jump-size x-jump y-jump))
                  ;; )
                  (or x-jump y-jump))))
  (jump 0 0))
 
(def n 7)
 
(def board
  [[2 5 1 6 1 4 1]
   [6 1 1 2 2 9 3]
   [7 2 3 2 1 3 1]
   [1 1 3 1 7 1 2]
   [4 1 2 3 4 1 2]                      ; 2일때는 정상.
   [3 3 1 2 3 4 1]
   [1 5 2 9 4 7 '*]])
 
(def wrong-board
  [[2 5 1 6 1 4 1]
   [6 1 1 2 2 9 3]
   [7 2 3 2 1 3 1]
   [1 1 3 1 7 1 2]
   [4 1 2 3 4 1 3]                      ; 3일때는 안됨.
   [3 3 1 2 3 4 1]
   [1 5 2 9 4 7 '*]])
 
;; (try-jump n board)
;; jump 6,4 (2) : false-true
;; jump 3,4 (3) : true-false
;; jump 3,3 (1) : false-true
;; jump 3,1 (2) : false-true
;; jump 2,1 (1) : true-false
;; jump 2,0 (1) : false-true
;; jump 0,0 (2) : true-false
 
;; (try-jump n wrong-board) ; => false

<markdown>

;; 코드 8.5 외발 뛰기 문제를 해결하는 동적 계획법 알고리즘. 217p </markdown>

;; 코드 8.5 외발 뛰기 문제를 해결하는 동적 계획법 알고리즘. 217p
(defn try-jump2
  [n board]
 
  (defn make-empty-board [n]
    (vec (repeat n (vec (repeat n nil)))))
 
  (def ^:dynamic *cache* (atom (make-empty-board n)))
 
  (defn get-cached [x y] (get-in @*cache* [y x]))
 
  (defn caching [x y val] (swap! *cache* assoc-in [y x] val) val)
 
  (defn board-xy [x y] (get-in board [y x]))
 
  (defn jump2
    [x y]
    (cond (or (>= x n) (>= y n)) false
          (and (= x (- n 1)) (= y (- n 1))) true
          :else
          (let [ret (get-cached x y)]
            (if (not (nil? ret))
              ret
              (let [jump-size (board-xy x y)
                    x-jump (jump2 (+ x jump-size) y)
                    y-jump (jump2 x (+ y jump-size))
                    is-jumpable (or x-jump y-jump)]
                ;; (println (format "jump %d,%d (%d) : %s-%s" x y jump-size x-jump y-jump))
                (caching x y is-jumpable))))))
  (jump2 0 0))
 
(def worst-board
  [[1 1 1 1 1 1 1]
   [1 1 1 1 1 1 1]
   [1 1 1 1 1 1 1]
   [1 1 1 1 1 1 1]
   [1 1 1 1 1 1 1]
   [1 1 1 1 1 1 2]
   [1 1 1 1 1 2 '*]])
 
;; (try-jump n worst-board) ; printed 2500 lines.
;; (try-jump2 n worst-board) ; printed 50 lines.

<markdown>


## 8.02 문제: 와일드카드 (문제 ID:WILDCARD, 난이도: 중) * 와일드카드(`?`, `*`)를 지닌 문자열과 매칭되는 문자열 구하기. * 와일드카드패턴 : 알파뱃 소문자, 대문자, `?`, `*`, 공백포함하지않음. - `?`는 어떠한 글자 하나. - `*`는 0글자 이상. * 매칭될문자열 : 알파뱃 소문자, 대문자, 소문자, 공백포함하지않음.

;; 코드 8.6 와일드 카드 문제를 해결하는 완전 탐색 알고리즘. 222p </markdown>

;; 코드 8.6 와일드 카드 문제를 해결하는 완전 탐색 알고리즘. 222p
(defn wildcard-match
  [w s]
  (let [pos (atom 0)
        w-size (count w)
        s-size (count s)]
 
    ;; w[pos]와 s[pos]를 찾줘나간다.
    (while (and (< @pos s-size)
                (< @pos w-size)
                (or (= \? (nth w @pos)) (= (nth w @pos) (nth s @pos))))
      (swap! pos inc))
 
    ;; 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 대응.
    (cond (= @pos w-size) (= @pos s-size)
          (not= \* (nth w @pos)) false
          :else
          ;; *을 만나서 끝날경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인.
          (loop [skip 0]
            (if (> (+ @pos skip) s-size)
              false
              (if (wildcard-match (subs w (inc @pos)) (subs s (+ @pos skip)))
                true
                (recur (inc skip))))))))
 
(defn filter-wildcard-matchs
  [wildcard-str samples]
  (filter (fn [s] (wildcard-match wildcard-str s)) samples))
 
 
(= (filter-wildcard-matchs "he?p" '("help" "heap" "helpp"))
   '("help" "heap"))
 
(= (filter-wildcard-matchs "*p*" '("help"  "papa" "hello"))
   '("help" "papa"))
 
(= (filter-wildcard-matchs "*bb*" '("babbbc"))
   '("babbbc"))

<markdown>

;; glob→regex를 이용한버전. </markdown>

;; glob->regex를 이용한버전.
;; ref: https://github.com/jkk/clj-glob/blob/master/src/org/satta/glob.clj
(defn- glob->regex
  "Takes a glob-format string and returns a regex."
  [s]
  (loop [stream s
         re ""
         curly-depth 0]
    (let [[c j] stream]
      (cond
       ;; (nil? c) (re-pattern (str (if (= \. (first s)) "" "(?=[^\\.])") re))
       (nil? c) (re-pattern (str (if (= \. (first s)) "" "(?=[^\\.])") re "$")) ; fixed
       (= c \\) (recur (nnext stream) (str re c c) curly-depth)
       (= c \/) (recur (next stream) (str re (if (= \. j) c "/(?=[^\\.])"))
                       curly-depth)
       (= c \*) (recur (next stream) (str re "[^/]*") curly-depth)
       (= c \?) (recur (next stream) (str re "[^/]") curly-depth)
       (= c \{) (recur (next stream) (str re \() (inc curly-depth))
       (= c \}) (recur (next stream) (str re \)) (dec curly-depth))
       (and (= c \,) (< 0 curly-depth)) (recur (next stream) (str re \|)
                                               curly-depth)
       (#{\. \( \) \| \+ \^ \$ \@ \%} c) (recur (next stream) (str re \\ c)
                                                curly-depth)
       :else (recur (next stream) (str re c) curly-depth)))))
 
 
(defn filter-glob-matchs
  [wildcard-str samples]
  (let [pattern (glob->regex wildcard-str)]
    (filter (fn [s] (re-find pattern s)) samples)))
 
(= (filter-glob-matchs "he?p" '("help" "heap" "helpp"))
   '("help" "heap"))
 
(= (filter-glob-matchs "*p*" '("help"  "papa" "hello"))
   '("help" "papa"))
 
(= (filter-glob-matchs "*bb*" '("babbbc"))
   '("babbbc"))

<markdown>

## 8.03 풀이: 와일드카드 ;; 코드 8.7 와일드카드 문제를 해결하는 동적 계획법 알고리즘. 223p </markdown>

;; 코드 8.7 와일드카드 문제를 해결하는 동적 계획법 알고리즘. 223p
(defn memo-wildcard-match
  [^String W ^String S]
 
  (defn make-empty-cache
    [x y]
    (vec (repeat y
                 (vec (repeat x nil)))))
 
  (def ^:dynamic *cache* (atom (make-empty-cache (inc (count W)) (inc (count S)))))
  (defn get-cached [x y] (get-in @*cache* [y x]))
  (defn caching [x y val] (swap! *cache* assoc-in [y x] val) val)
 
  (defn -memo-wildcard-match
    [^String W ^String S ^Integer w ^Integer s]
    (let [ret (get-cached w s)]
      (if (not (nil? ret))
        ret
        (let [w-size (count W)
              s-size (count S)]
          (letfn [(posing [w s]
                    (loop [w w s s]
                      (if (not (and (< s s-size)
                                    (< w w-size)
                                    (or (= \? (nth W w))
                                        (= (nth W w) (nth S s)))))
                        (list w s)
                        (recur (inc w) (inc s)))))]
            (let [[w s] (posing w s)]
              (cond (= w w-size) (caching w s (= s s-size)) ;
                    (not= \* (nth W w)) (caching w s false) ;
                    :else
                    ;; *을 만나서 끝날경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인.
                    (loop [skip 0]
                      (if (> (+ s skip) s-size)
                        (caching w s false) ;
                        (if (-memo-wildcard-match W S (inc w) (+ s skip))
                          (caching w s true) ;
                          (recur (inc skip))))))))))))
  (-memo-wildcard-match W S 0 0))
 
(defn filter-memo-wildcard-matchs
  [wildcard-str samples]
  (filter (fn [s] (memo-wildcard-match wildcard-str s)) samples))
 
(= (filter-memo-wildcard-matchs "he?p" '("help" "heap" "helpp"))
   '("help" "heap"))
 
(= (filter-memo-wildcard-matchs "*p*" '("help"  "papa" "hello"))
   '("help" "papa"))
 
(= (filter-memo-wildcard-matchs "*bb*" '("babbbc"))
   '("babbbc"))

<markdown>

* 패턴의 길이 : a * 문자열의 길이 : b * 부분문제 갯수 : a*b * 한번 호출될때 최대 a번의 채귀 호출 * 전체 시간 복잡도는 O(a^2 * b)

### 다른 분해 방법 </markdown>

(defn memo-wildcard-match2
  [^String W ^String S]
 
  (defn make-empty-cache
    [x y]
    (vec (repeat y
                 (vec (repeat x nil)))))
 
  (def ^:dynamic *cache* (atom (make-empty-cache (inc (count W)) (inc (count S)))))
  (defn get-cached [x y] (get-in @*cache* [y x]))
  (defn caching [x y val] (swap! *cache* assoc-in [y x] val) val)
 
  (defn -memo-wildcard-match2
    [^String W ^String S ^Integer w ^Integer s]
    (let [ret (get-cached w s)]
      (if (not (nil? ret))
        ret
        (let [w-size (count W)
              s-size (count S)]
          (if (and (< s s-size)
                   (< w w-size)
                   (or (= \? (nth W w)) (= (nth W w) (nth S s))))
            (caching w s (-memo-wildcard-match2 W S (inc w) (inc s)))
 
            (cond (= w w-size) (caching w s (= s s-size))   ;
                  (= \* (nth W w)) (caching w s
                                            (or (-memo-wildcard-match2 W S (inc w) s)
                                                (and (< s s-size) (-memo-wildcard-match2 W S w (inc s)))))
                  :else
                  (caching w s false)   ;
                  ))))))
 
  (-memo-wildcard-match2 W S 0 0))
 
(defn filter-memo-wildcard-match2s
  [wildcard-str samples]
  (filter (fn [s] (memo-wildcard-match2 wildcard-str s)) samples))
 
(= (filter-memo-wildcard-match2s "he?p" '("help" "heap" "helpp"))
   '("help" "heap"))
 
(= (filter-memo-wildcard-match2s "*p*" '("help"  "papa" "hello"))
   '("help" "papa"))
 
(= (filter-memo-wildcard-match2s "*bb*" '("babbbc"))
   '("babbbc"))
 
;; (println "W:" (subs W w) "S:" (subs S s) 넣어본 결과.
;; (memo-wildcard-match "*****a" "aaaaaaaaaab") ; 108 false
;; (memo-wildcard-match2 "*****a" "aaaaaaaaaab") ; 84 false
 
;; (time (wildcard-match "*****a" "aaaaaaaaaab")) ; >> "Elapsed time: 4.664179 msecs"
;; (time (memo-wildcard-match "*****a" "aaaaaaaaaab")) ; >> "Elapsed time: 0.747039 msecs"
;; (time (memo-wildcard-match2 "*****a" "aaaaaaaaaab")) ; >> "Elapsed time: 0.325003 msecs"
;; (time (re-find (glob->regex "*****a") "aaaaaaaaaab")) ; >> "Elapsed time: 1.183073 msecs"

<markdown>


=⇒ 여기부터 할꺼임

## 8.04 전통적 최적화 문제들 * 최적화 문제 : 여러 개의 가능한 답 중 가장 좋은 답을 찾아내는 것. * 동적 계획법은 처음에 최적화 문제의 해답을 빨리 찾아내기 위해 노력하는 과정에서 고안되었으며, 때문에 많은 교과서 에서 동적 계획법을 논의할때 최적화 과정을 가장 부각시켜 설명함.

### 예제: 삼각형 위의 최대 경로 (문제 ID: TRIANGLEPATH, 난이도: 하)

* (0, 0)에서 시작해서, 하단 혹은 우하단으로 한칸씩 이동하며, 바닦에(?, y-1)에 도달했을때의 경로를 구하고, * 경로중 숫자의 합을 최대화하는 경로와, 최대합을 구하시오.

</markdown>

6
1 2
3 7 4
9 4 1 7
2 7 5 9 4
get-max-path ;=> [28  [[0 0] [1 1] [2 2] [3 3] [3 4]]]
 
 
1
2   4
8   16  8
32  64  32  64
128 256 128 256 128
get-max-path ;=> [341 [[0 0] [1 1] [1 2] [1 3] [1 4]]]

<markdown>

### 완전 탐색으로 시작하기

* pathSum(y, x, sum) : (y, x)와 현재까지의 합 sum을 인자로 받아, 앞으로의 경로의 최대합을 반환한다.

점화식 </markdown>

path1(y, x, sum) = 
    max(path1(y+1, x  , sum+triangle[y][x]),
        path1(y+1, x+1, sum+triangle[y][x]))

<markdown>

</markdown>

(def a-path
  [[6   nil nil nil nil]
   [1   2   nil nil nil]
   [3   7   4   nil nil]
   [9   4   1   7   nil]
   [2   7   5   9   4]])
 
(def b-path
  [[1   nil nil nil nil]
   [2   4   nil nil nil]
   [8   16  8   nil nil]
   [32  64  32  64  nil]
   [128 256 128 256 128]])

<markdown>

;; get-max-path0 </markdown>

;; get-max-path0
(defn get-path0
  [path n x y sum]
  (let [val (get-in path [y x])
        sum (+ sum val)]
    (if (= y (dec n))
      sum
      (max (get-path0 path n (+ x 1) (+ y 1) sum)
           (get-path0 path n x       (+ y 1) sum)))))
 
(defn get-max-path0
  [path]
  (get-path0 path (count path) 0 0 0))
 
(get-max-path0 a-path) ;=> 28
(get-max-path0 b-path) ;=> 341

<markdown>

;; get-max-path00 </markdown>

;; get-max-path00
(defn get-max-path00
  [path]
  (get-path00 path (count path) [0 0] 0 []))
 
(defn get-path00
  [path n [x y] sum best-path]
  (let [val (get-in path [y x])
        sum (+ sum val)
        best-path (conj best-path [x y])]
    (if (= y (- n 1))
      [sum best-path]
      (first
       (sort-by first > (list
                         (get-path00 path n [(+ x 1) (+ y 1)] sum best-path)
                         (get-path00 path n [x       (+ y 1)] sum best-path)))))))
 
 
(get-max-path00 a-path) ;=> [28  [[0 0] [1 1] [2 2] [3 3] [3 4]]]
(get-max-path00 b-path) ;=> [341 [[0 0] [1 1] [1 2] [1 3] [1 4]]]

<markdown>

?? 경로랑 sum을 구하는데… 뭐 더 좋은방식이 없을까?

### 입력 걸러내기

* path2(y, x) = (y, x)에서 시작해서 맨 아래줄 까지 내려가는 부분 경로의 최대 합을 반환한다.

점화식 </markdown>

path2(y, x) = 
    triangle[y][x]
    + max(path2(y+1, x  ),
          path2(y+1, x+1))

<markdown>

;; 코드 8.9 삼각형 위의 최대 경로 문제를 푸는 동적 계획법 알고리즘(2). 229p </markdown>

;; 코드 8.9 삼각형 위의 최대 경로 문제를 푸는 동적 계획법 알고리즘(2). 229p
 
(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-in k v) v)
 
(defn get-max-path1
  [path]
  (let [len (count path)]
    (letfn [(get-path2 [path x y]
              (if (= y (dec len))
                (get-in path [y x])
                (if-let [ret (get-cached [y x])]
                  ret
                  (caching [y x] (+ (get-in path [y x])
                                    (max (get-path2 path x       (+ y 1))
                                         (get-path2 path (+ x 1) (+ y 1))))))))]
      (reset-cache (vec (repeat len
                                (vec (repeat len nil)))))
      (get-path2 path 0 0))))
 
(= (get-max-path1 a-path) 28)
(= (get-max-path1 b-path) 341)
(= (get-max-path1 b-path) 341)

<markdown>

### 이론적 배경: 최적 부분 구조 * 최적부분구조(optimal substructure) - 어떤 문제와 분할방식 간에 성립하는 조건 - 각 부분 문제의 최적해만 있으면, 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우, 조건 성립.

단순 최단 경로 </markdown>

서울 - 대전 - 부산

<markdown>

최단 경로 - with 통행료 3만. </markdown>

서울 - 대전 =a통행시간:2h, 통행비:1만> 부산
서울 - 대전 =b통행시간:1h, 통행비:2만> 부산
 
서울 - 대전 사이의 통행비에 의해 경로 선택이 달라짐. - 최적 부분 구조가 존재하지 않음.

<markdown>

### 예제: 최대 증가 부분 수열(문제 ID: LIS, 난이도: 하) * 정수 수열 S의 부분 수열이란? - S에서 0개 이상의 숫자를 지우고 남은 수열. * 증가 부분 수열이란? - 부분 수열에 포함된 숫자들이 순증가하는 수열. * 최대 증가 부분 수열(LIS, Longest Increasing Subsequence)찾기 문제. - 주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 문제. - 매우 유명한 동적 계획법 연습문제 중 하나.

* http://en.wikipedia.org/wiki/Longest_increasing_subsequence - `a1, a2, …., an`이 주여졌을때, `i < j, ai < aj`인 하위집합중 가장 긴것을 찾는 것임. - A = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] , … - LIS(A) = [0, 2, 6, 9, 13, 15] || [0, 4, 6, 9, 11, 15] - len LIS(A) = 6

* 예) [1 8 2 7 3 4 1 6] ⇒ [1 2 3 4 6] ![-Longest-subsequence.png](http://www.stoimen.com/blog/wp-content/uploads/2012/12/4.-Longest-subsequence.png)

### 완전 탐색에서 시작하기 ;; 코드8.10 최대 증가 부분 수열 문제를 해결하는 완전 탐색 알고리즘. 232p

</markdown>

;; 코드8.10 최대 증가 부분 수열 문제를 해결하는 완전 탐색 알고리즘. 232p
 
;; ref: https://groups.google.com/d/msg/clojure/9bnpeURy-I8/JzUH2tyf0ecJ
(defn maplist
  ([s] (maplist identity s))
  ([f s] (when-let [s (seq s)] (lazy-seq (cons (f s) (maplist f (next s)))))))
 
(maplist [1 2 3])                   ;=> ((1 2 3) (2 3) (3))
(maplist (partial apply +) [1 2 3]) ;=> (6 5 3)
 
(defn tail-bigger-than-head
  [[h & t]]
  (filter #(> % h) t))
 
(tail-bigger-than-head [2 1 2 3 4]) ;=> (3 4)
 
(defn lis0
  [coll]
  (if (empty? coll)
    0
    (apply max
           (maplist (comp inc lis0 tail-bigger-than-head) coll))))
 
(= (lis0 [1 3 4 2 4]) 3)
(= (lis0 [3]) 1)
(= (lis0 [1 2 3]) 3)
(= (lis0 [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]) 6)

<markdown>

### 입력 손보기 * 인자를 콜렉션으로(`A`)받기에, 메모이제이션을 적용하기 까다로움.(느림)

</markdown>

lis(A)에서, A는
1. 원래 주어진 수열 S
2. 원래 주어진 수열의 원소 S[i]에 대해, S[i+1 ...] 부분 수열에서 S[i]보다 큰 수들만을 포함하는 부분 수열.

<markdown>

* 콜렉션을 넘기는 것이 아닌, 인덱스를 넘기는 방식으로 변경.

</markdown>

lis(start) = S[start]에서 시작하는 부분 증가 수열 중 최대의 길이

<markdown>

;; 코드8.11 최대 증가 부분 수열 문제를 해결하는 동적 계획법 알고리즘 (1) 233p </markdown>

int n;
int cache[100], S[100];
 
int lis2(int start) {
  int& ret = cache[start];
  if (ret != -1) return ret;
 
  ret = 1;
  for (int next = start + 1; next < n; ++next) {
    if (S[start] < S[next])
      ret = max(ret, lis2(next) + 1);
  }
  return ret;
}

<markdown>

</markdown>

;; 코드8.11 최대 증가 부분 수열 문제를 해결하는 동적 계획법 알고리즘 (1) 233p
 
;; ref: http://stackoverflow.com/questions/8641305/find-index-of-an-element-matching-a-predicate-in-clojure
(defn indices [pred coll]
  "coll에서 pred를 만족하는, index list를 반환."
  (keep-indexed #(when (pred %2) %1) coll))
 
(indices odd? [2 4 6 7 8 9]) ;=> (3 5)
 
(defn find-index [pred coll]
  (first (indices pred coll)))
 
(find-index odd? [2 4 6 7 8 9]) ;=> 3
 
(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-lis2
  [coll]
  (letfn [(lis2 [start]
            (if-let [ret (get-cached start)]
              ret
              (let [rest (nthrest coll start)
                    h    (first rest)]
                (if-let [idxs (indices #(> % h) rest)]
                  (let [lis2s (map #(+ (lis2 (+ start %)) 1) idxs)]
                    (caching start (apply max lis2s)))
                  1))))]
  (let [len (count coll)]
    (reset-cache (vec (repeat len nil)))
    (apply max (map lis2 (range len))))))
 
(= (get-lis2 [1 3 4 2 4]) 3)
(= (get-lis2 [1 2 3 4]) 4)
(= (get-lis2 [5 4 3 2 1 6 7 8]) 4)
(= (get-lis2 [5 6 7 8 1 2 3 4]) 4)
(= (get-lis2 [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]) 6)

<markdown>

### 더 빠른 해법 * O(nlgn)에 LIS를 찾을 수 있는 알고리즘이 있음. * 텅 빈 수열에서 시작해 숫자를 하나씩 추가해 나가며, 각 길이를 갖는 증가 수열 중 가장 마지막 수가 작은 것이 무엇인지 추적.

</markdown>

C[i] = 지금까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막 값.

<markdown> * C[]가 항상 순증가 한다는 성질을 이용, 이분검색으로 LIS를 O(nlgk) ⇐ O(nlgn)에 찾는 알고리즘을 만들 수 있음.

* ??? @_@?

### 최적화 문제동적 계획법 레시피

1. 모든 답을 만들어 보고 그 중 최젂해의 점수를 반환하는, 완전 탐색 알고리즘을 설계. 2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿈. 3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면, 꼭 필요한 것만 남기고 줄이기. 4. 입력이 배열이거나 문자열인경우, 가능하다면 적절한 변환을 통해 메모이제이션. 5. 메모이제이션 적용.


## 8.05 문제: 합친LIS(문제 ID JLIS, 난이도: 하) - 일단 패스. 집중력이 부족해 문제 이해를 못함 -_-; * 합친 LIS (JLIS, Joined Longest Incresing Subsequence) * 두 개의 정수 수열 A와 B에서 각각 길이 0이상의 증가 부분 수열을 얻은 뒤, 이들을 크기 순서대로 합친 것을 합친 증가수열이라 부름.

예) [1 9 4], [3 4 7] ⇒ [1 3 4 7 9]

## 8.06 풀이: 합친 LIS


## 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>

;; 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))

<markdown>

## 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.14 원주율 외우기 문제를 해결하는 동적계획법 알고리즘. - C </markdown>

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;
}

<markdown>

;; 코드 8.14 원주율 외우기 문제를 해결하는 동적계획법 알고리즘. - Clojure

</markdown>

;; 코드 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

<markdown>


여기까지 2차 목표.

## 8.09 문제: Quatization (문제 ID: QUANTIZE, 난이도: 중) ## 8.10 풀이: Quatization


## 8.11 경우의 수와 확률


## 8.12 문제: 비대칭 타일링 (문제 ID: ASYMTILING, 난이도: 하) ## 8.13 풀이: 비대칭 타일링


여기까지 3차 목표.

## 8.14 문제: 폴리오미노 (문제 ID: POLY, 난이도: 중) ## 8.15 풀이: 폴리오미노


## 8.16 문제: 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중) ## 8.17 풀이: 두니발 박사의 탈옥

여기까지 4차 목표.


# 기타. Dynamic Programming Approach - http://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence

* top-down approach

</markdown>

var m := map(0 → 0, 1 → 1)
function fib(n)
   if map m does not contain key n
       m[n] := fib(n ? 1) + fib(n ? 2)
   return m[n]
 
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

<markdown>

* bottom-up approach

</markdown>

function fib(n)
   if n = 0
       return 0
   var previousFib := 0, currentFib := 1
   else repeat n ? 1 times  // loop is skipped if n=1
       var newFib := previousFib + currentFib
       previousFib := currentFib
       currentFib  := newFib
   return currentFib
 
fib(0) + fib(1) = fib(2)
fib(1) + fib(2) = fib(3)
fib(2) + fib(3) = fib(4)
fib(3) + fib(4) = fib(5)

<markdown> # 기타. Van der Corput sequence * 네덜란드 수학자 J. G. van der Corput. * 진법을 역으로 표현

</markdown>

decimal van der Corput sequence
0.00, 0.10, 0.20, 0.30, 0.40, 0.50, 0.60, 0.70, 0.80, 0.90,
0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61, 0.71, 0.81, 0.91,
0.02, 0.12, 0.22, 0.32, …

<markdown>

</markdown>

binary van der Corput sequence
0
.1
.01
.11
.001
.101
.011
.111
.0001
.1001
.0101
....

<markdown>

</markdown>

8421
1    | 8
01   | 4
11   | 12
001  | 2
101  | 10
 
A = 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, … 

<markdown>

# 기타. [# 53. Longest Increasing Sub-Seq](http://www.4clojure.com/problem/53)

</markdown>

(defn maplist
  ([s] (maplist identity s))
  ([f s] (when-let [s (seq s)] (lazy-seq (cons (f s) (maplist f (next s)))))))
 
(maplist [1 2 3]) ;=> ((1 2 3) (2 3) (3))
 
(defn increment? [coll]
  (every? (fn [[x y]] (< x y)) (map list (butlast coll) (rest coll))))
 
(increment? [1 2 3]) ;=> true
(increment? [1 3 2]) ;=> false
 
(defn rmaplist
  ([s] (rmaplist identity s))
  ([f s] (when-let [s (seq s)]
              (map f (for [i (range 1 (inc (count s)))] (take i s))))))
 
(rmaplist [1 2 3]) ;=> ((1) (1 2) (1 2 3))
 
(defn get-longest-increasing-sub-seq [coll]
  (let [liss (first (sort #(> (count %1) (count %2))
                          (map (comp last
                                     (partial filter increment?))
                               (map rmaplist (maplist coll)))))]
    (if (< (count liss) 2) '() liss)))
 
(get-longest-increasing-sub-seq [1 0 1 2 3 0 4 5]) ;=> (0 1 2 3)
(get-longest-increasing-sub-seq [5 6 1 3 2 7])     ;=> (5 6)
(get-longest-increasing-sub-seq [2 3 3 4 5])       ;=> (3 4 5)
(get-longest-increasing-sub-seq [7 6 5 4])         ;=> '()

<markdown>

# 느낀점 - `동적 계획법`이란 단어가 생소해서 선택했는데… 과연.. - -

# 참고 - [ppt:동적 프로그래밍-강원대학교](http://cs.kangwon.ac.kr/~ysmoon/courses/2007_1/alg/06.ppt) </markdown>

study/algorithms/dynamic_plan.txt · Last modified: 2019/02/04 14:26 (external edit)