User Tools

Site Tools


lecture:4clojure:word_chains_82번_문제_풀이

Differences

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

Link to this comparison view

lecture:4clojure:word_chains_82번_문제_풀이 [2019/02/04 14:26] (current)
Line 1: Line 1:
 +====== 실전 문제 풀이 ======
 +----
 +===== 풀이 활동 기술 =====
 +
 +;;; #82. Word Chains, 2013.01.18 20:59 ~ 2013.01.
 +
 +===== 문제 서술에 정확한 파악 =====
 +
 +; 먼저 문제 서술을 정확하게 이해한다. \\
 +
 +===== 테스트를 머리속에서 먼저 진행해 본다. =====
 +
 +; 각 테스트를 둘러본다.
 +; 종이 노트를 적극 활용한다.
 +
 +==== Test1 ====
 +<​code>​
 +  ___________ ​
 + ​| ​          |
 +hat - cat - oat    1. dog-hog-hot-cot-cat-hat-oat-coat
 + ​\ ​    ​| ​ \  /     2. dog-hog-hot-cot-cat-coat-oat-hat
 +  \   cot- coat    3. dog-hog-hot-hat-oat-coat-cat-cot
 +   ​\ ​  ​| ​          4. hat-oat-coat-cat-cot-hot-hog-dog  ​
 +      hot               ....
 +       |
 +      hog
 +       |
 +      dog
 +</​code> ​      
 +
 +==== Test2 ====
 +<​code>​
 +   ​cot-hot
 +   ​bat-fat
 +</​code>​
 +
 +==== Test3 ====
 +<​code>​
 +   ​to-top-stop
 +       |
 +      tops-toss
 +</​code>​
 +
 +==== Test4 ====
 +<​code>​
 +
 +     ​--------------
 +    |              |
 +  spout-pout-pot-spot ​  1. pout-spout-spot-pot-dot-do
 +              |         2. spot-spout-pout-pot-dot-do
 +             ​dot ​       3. do-dot-pot-pout-spout-spot ​
 +              |         4. do-dot-pot-spot-spout-pout
 +             do
 +</​code>​
 +
 +==== Test5 ====
 +<​code>​
 +    share-shares-hares ​ 1. are-hare-share-shares-hares
 +      |            |
 +    hare-----------
 +      |
 +     are
 +</​code>​
 +
 +==== Test6 ====
 +<​code>​
 +    share       ​hares  ​
 +      |            |
 +    hare-----------
 +      |
 +     are
 +</​code>​
 +
 +===== 전략 구상 =====
 +
 +==== 작은 전투 ====
 +
 +일단 이 문제를 풀기 위해서는 2 단어가 chain이 될 수 있는지 판단하는 함수가 필요하다는 것을 알 수 있다. 그 함수 이름을 chainable?​이라고 하고 이를 먼저 구현해보는 것은 전혀 낭비가 될 수 없다. 즉 이 함수가 반드시 있어야 하는 함수이지 나중에 풀이가 진행되면서 없어져도 될 수 있는 함수는 아니다.
 +
 +이렇게 큰 전투를 위해서는 반드시 해야 하는 작은 전투들이 있다. 불필요한 전투로 아군의 희생을 치르지 말아야 할 것이다. 반드시 그 전투는 해야 한다는 생각이 들 때까지는 하지 않는 것이 좋다. Laziness~~~
 +
 +여기서 적절한 함수 이름이 떠오르면 아주 좋다. 하지만 특정 기능을 하는 함수의 적절한 이름이 떠오르지 않는다면 그냥 f, f1, f'​등으로 하고 함수 구현으로 바로 들어가는 것이 좋다. 하지만 나중에 읽다 보면 이 함수가 무슨 일을 하는지 함수 이름만으로는 잘 생각 생각이 나지 않을 수 있으니 나중에라도 꼭 이름을 붙여주자.
 +
 +자 그런데 일단 chainable? 함수가 있다고 치자. 아주 잘 작동한다. 그 다음은 어떻게 해야 하는 지를 먼저 고민해 볼 수 있다. 코딩에 들어가기 전에...
 +
 +==== 큰 전투 ====
 +결국 큰 전투를 위한 전략에 대한 구체적인 착상에 들어가야 한다. 다시 위에서 우리가 Test들을 해봤던 것을 관찰해 보자. 우리 인간이 했던 것을 컴퓨터가 똑같이 할 수 있도록 만들 수 있다면(믿어라. 클로저는 그게 가능하다. 미로 생성기를 기억해 보라.) 우리가 했던 것을 자세히 관찰하고 그것을 절차적 방식으로 풀어낼 수만 있다면, 그것을 클로저로 구현할 수 있다.
 +
 +Peter Norvig'​s Rule of English Translation.
 +
 +To insure that you say what you mean:
 +
 +  - Start with an English description of the algorithm
 +  - Write the code from the description
 +  - Translate the code back to english
 +  - Compare 3 to 1
 +
 +==== 1 단계 ====
 +
 +먼저 Test1을 살펴보자.
 +
 +우리는 임의 단어로부터 시작해서 chainable? 단어를 따라 갔다. 따라 가면서 각 단어를 한 번만 거쳐야 한다. 그러면서 모든 단어를 거칠 수 있어야 한다. 이것은 모든 단어가 chainable? 관계로 순서지어졌다는 얘기다(whole-chainable-sequence?​ 이거 이름이 좋다. 이거 쓰자. 하지만 넘 길다. 일단 잠시 작업하는 동안은 줄여서 chainable? 은 c?로, whole-chainable-sequence?​는 wcs?로 하자.). 따라 가다 보면 갈림길에서는 한 쪽 길로 가게 된다. 끝에 도달하지 않으면 다시 갈림길로 돌아와서 다른 쪽 길로 가서 끝에 도달하는지 확인해야 한다. ​
 +
 +자 원래 문제를 보자. 입력이 #​{"​hat"​ "​coat"​ "​dog"​ "​cat"​ "​oat"​ "​cot"​ "​hot"​ "​hog"​} 로 되어 있다. 8개의 단어를 갖는 집합이다. ​
 +
 +다음과 같은 절차를 만들어 볼 수 있다.
 +
 +  - 임의의 단어를 선택한다.
 +  - 그 단어와 c?인 단어를 임의로 찾는다.
 +  - 2에서 c?인 단어가 없으면 1로 돌아간다
 +  - 2에서 c?인 단어가 있으면 2로 돌아간다.
 +
 +대충 이렇게 문장으로 절차적 표현한다. 이걸 우리가 머리속에서 돌려보자.
 +
 +==== 2 단계 ====
 +
 +hat으로 시작하자. c2인 단어를 찾으니 oat와 hot 2개가 나온다. 이런 하나가 아니라 여러 개 나올 수 있다... 그래서 절차는 다음과 같이 바뀌어야 한다.
 +
 +  - 처음 집합에서 임의의 단어를 선택한다.
 +  - 그 단어와 c?인 단어들의 집합을 찾는다.
 +  - 2에서 구한 집합이 공집합이면 1로 돌아간다.
 +  - 2에서 구한 집합에서 임의 단어를 취하고 2로 돌아간다.
 +
 +처음 집합에서 hat을 선택하면 c2인 단어들 #{hot oat}를 구하게 될 것이다. 여기서 hot를 취한다. 다시 c2인 단어들 #{cot hog}을 구하게 된다. hog를 취하면 #{dog}를 구하게 된다. dog를 취하면 #{}이다. 하지만 아직 단어를 다 거친 것이 아니기 때문에 cs?가 아니다.
 +
 +==== 3 단계 ====
 +
 +이 과정을 값들만 나열해 보자.
 +
 +hat-#{hot oat}-hot-#​{cot hog}-hog-#​{dog}-dog-#​{},​ link:​hat-hot-hog-dog,​ 4개 단어 남음, cs->​false
 +
 +두 번째에서 hot이 아닌 oat를 선택하면 다음과 같다.
 +
 +hat-#{hot oat}-oat-#​{coat}-coat-#​{cat,​cot}-cat-#​{cot}-cot-#​{hot}-hot-#​{hog}-hog-#​{dog}-dog-#​{},​ link:​hat-oat-coat-cat-cot-hot-hog-dog,​ 0개 단어 남음, cs?​->​true
 +
 +  - 처음 집합에서 임의의 단어를 선택한다.
 +  - 그 단어와 c?인 단어들의 집합을 찾는다.
 +  - 2에서 구한 집합이 공집합이면 1로 돌아간다.
 +  - 2에서 구한 집합에서 임의 단어를 취하고 2로 돌아간다.
 +
 +
 +==== 최종 함수 ====
 +
 +c? 함수
 +<code clojure>
 +(defn m? [s1 s2]
 +  (= 1 (count (filter false? (map = (seq s1) (seq s2))))))
 +
 +(defn n? [s1 s2]
 + ​(count (take-while #(apply = %) (map #(list % %2) (seq s1) (seq s2)))))
 +
 +(defn omit [n s]
 +  (concat (take n s) (drop (inc n) s)))
 +
 +(defn l? [s1 s2]
 +  (let [[s b] (if (< (count s1) (count s2)) [s1 s2] [s2 s1])]
 +    (= (seq s) (omit (n? s1 s2) b))))
 +
 +(defn c? [s1 s2]
 +  (let [l1 (count s1)
 +        l2 (count s2)
 +        f (if (= l1 l2) m? l?)]
 +    (f s1 s2)))
 +</​code>​
 +
 +c? by [[http://​www.4clojure.com/​user/​maximental|maximental]]
 +<code clojure>
 +(fn [s t] 
 +  (let [g (fn [x y]  ​
 +            (some 
 +              #(= (seq x) `(~@(take % y) ~@(drop (+ % 1) y))) 
 +              (range (count y))))]
 +    (condp = (- (count s) (count t)) 
 +       0 (= 1 (apply + (map #(if (= % %2) 0 1) s t)))
 +       1 (g t s)
 +      -1 (g s t)
 +         ​false)))
 +</​code>​
 +
 +c? 함수 by [[http://​www.4clojure.com/​user/​chouser|chouser]]
 +<code clojure>
 +(defn c2? [s1 s2]
 +  (loop [[a & b :as c] (seq s1) [d & e :as g] (seq s2)]
 +    (if (= a d) (recur b e)
 +        (or (= b e) (= b g) (= c e)))))
 +</​code>​
 +
 +cs? 함수
 +<code clojure>
 +(defn g [e s]
 +  (if (empty? s) true
 +    (some #(g % (disj s %)) (filter #(ch? e %) s))))
 +
 +(defn cs? [s]
 +  (if (some #(g % (disj s %)) s) true false))
 +</​code>​
 +
 +cs? 함수 by [[http://​www.4clojure.com/​user/​maximental|maximental]]
 +<code clojure>
 +(fn [f c]
 +  ((fn h [w] 
 +     (let [r (reduce  ​
 +               #(if (f (last %) %2)  ​
 +                 `[~@% ~%2]  ​
 +                 (if (f (first %) %2) 
 +                   `[~%2 ~@%] 
 +                   ​%)) ​
 +               ​w ​
 +               ​(remove (set w) c))]
 +         (if (= r w) (= (set r) c) (h r)))) 
 +   ​[(first c)]))
 +</​code>​
 +
 +
 +====== 코드 읽기 ======
 +
 +"​사람들은 내가 쉽게 작곡한다고 생각하지만 이건 실수라네. 단언컨대 친구여, 나만큼 작곡에 많은 시간과 생각을 바치는 사람은 없을 걸세. //​**유명한 작곡가의 음악 치고 내가 수십 번에 걸쳐 꼼꼼하게 연구하지 않은 작품은 하나도 없으니 말이야.**//"​ - 모짜르트가 친구에게 보낸 어느 편지에서
 + 
 +
  
lecture/4clojure/word_chains_82번_문제_풀이.txt · Last modified: 2019/02/04 14:26 (external edit)