User Tools

Site Tools


4clojure_문제풀이

Differences

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

Link to this comparison view

4clojure_문제풀이 [2013/01/18 17:16]
psk810 [코드 읽기]
4clojure_문제풀이 [2019/02/04 14:26]
Line 1: Line 1:
-====== 4Clojure가 Clojure 공부에 좋은 이유 ====== 
-\\ 
- 
-  - Learn By Doing : 코딩을 하면서 코딩을 배운다. 
-  - 문제를 풀고 나면 다른 사람이 푼 것을 볼 수 있다. 이것은 특히 함수형 프로그래밍에 아직 익숙하지 않은 사람들에게 좋다. 다음 사람들을 Follow하면 좋은 코드를 볼 수 있다 : [[http://​www.4clojure.com/​user/​maximental|maximental]],​ [[http://​www.4clojure.com/​user/​hypirion|hypirion]],​ [[http://​www.4clojure.com/​user/​jafingerhut|jafingerhut]],​ [[http://​www.4clojure.com/​user/​chouser|chouser]] 
-  - 잘 정의된 테스트 케이스 : 테스트 케이스가 잘 정의되어 있어, 단순히 문제의 해설에 대한 오해를 차단한다. 또한 생각하지 못한 경우에 대해 코드가 대비하도록 한다. 
-  - Timeout이 걸려 있다. 그래서 간단한 방식으로 풀다 보면 시간 초과가 되어 테스트에 통과하지 못한다. 좀 더 전략적인 방법을 고안해야 한다. 
-  - Clojure.core의 함수들에 익숙해 진다 : map, map-indexed,​ keep, keep-indexed,​some,​ reduce,​frequencies,​merge-with,​condp 등 Clojure.core 함수들의 용법에 대해 적응하게 한다. 
-  - 인수 분해(Destructuring) 기법을 배우게 된다. 
-  - RDD에 대해 익숙하게 한다 : REPL Driven Development 
-  - HDD의 맛을 느끼게 한다 : Hammock Driven Development 
-\\ 
- 
- 
-====== 4Clojure 문제들 ====== 
- 
-^ Elementary |  32| 
-^ Easy       ​| ​ 53| 
-^ Medium ​    ​| ​ 45| 
-^ Hard       ​| ​ 23| 
-^ Total      |  153| 
- 
-\\ 
-====== 실전 문제 풀이 ====== 
----- 
-===== 풀이 활동 기술 ===== 
- 
-;;; #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>​ 
- 
- 
-====== 코드 읽기 ====== 
- 
-"​사람들은 내가 쉽게 작곡한다고 생각하지만 이건 실수라네. 단언컨대 친구여, 나만큼 작곡에 많은 시간과 생각을 바치는 사람은 없을 걸세. //​**유명한 작곡가의 음악 치고 내가 수십 번에 걸쳐 꼼꼼하게 연구하지 않은 작품은 하나도 없으니 말이야.**//"​ - 모짜르트가 친구에게 보낸 어느 편지에서 
-  
- 
- 
  
4clojure_문제풀이.txt · Last modified: 2019/02/04 14:26 (external edit)