User Tools

Site Tools


4clojure_문제풀이

4Clojure가 Clojure 공부에 좋은 이유


  1. Learn By Doing : 코딩을 하면서 코딩을 배운다.
  2. 문제를 풀고 나면 다른 사람이 푼 것을 볼 수 있다. 이것은 특히 함수형 프로그래밍에 아직 익숙하지 않은 사람들에게 좋다. 다음 사람들을 Follow하면 좋은 코드를 볼 수 있다 : maximental, hypirion, jafingerhut, chouser
  3. 잘 정의된 테스트 케이스 : 테스트 케이스가 잘 정의되어 있어, 단순히 문제의 해설에 대한 오해를 차단한다. 또한 생각하지 못한 경우에 대해 코드가 대비하도록 한다.
  4. Timeout이 걸려 있다. 그래서 간단한 방식으로 풀다 보면 시간 초과가 되어 테스트에 통과하지 못한다. 좀 더 전략적인 방법을 고안해야 한다.
  5. Clojure.core의 함수들에 익숙해 진다 : map, map-indexed, keep, keep-indexed,some, reduce,frequencies,merge-with,condp 등 Clojure.core 함수들의 용법에 대해 적응하게 한다.
  6. 인수 분해(Destructuring) 기법을 배우게 된다.
  7. RDD에 대해 익숙하게 한다 : REPL Driven Development
  8. 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

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

Test2

   cot-hot
   bat-fat

Test3

   to-top-stop
       |
      tops-toss

Test4

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

Test5

    share-shares-hares  1. are-hare-share-shares-hares
      |            |
    hare-----------
      |
     are

Test6

    share       hares  
      |            |
    hare-----------
      |
     are

전략 구상

작은 전투

일단 이 문제를 풀기 위해서는 2 단어가 chain이 될 수 있는지 판단하는 함수가 필요하다는 것을 알 수 있다. 그 함수 이름을 chainable?이라고 하고 이를 먼저 구현해보는 것은 전혀 낭비가 될 수 없다. 즉 이 함수가 반드시 있어야 하는 함수이지 나중에 풀이가 진행되면서 없어져도 될 수 있는 함수는 아니다.

이렇게 큰 전투를 위해서는 반드시 해야 하는 작은 전투들이 있다. 불필요한 전투로 아군의 희생을 치르지 말아야 할 것이다. 반드시 그 전투는 해야 한다는 생각이 들 때까지는 하지 않는 것이 좋다. Laziness~~~

여기서 적절한 함수 이름이 떠오르면 아주 좋다. 하지만 특정 기능을 하는 함수의 적절한 이름이 떠오르지 않는다면 그냥 f, f1, f'등으로 하고 함수 구현으로 바로 들어가는 것이 좋다. 하지만 나중에 읽다 보면 이 함수가 무슨 일을 하는지 함수 이름만으로는 잘 생각 생각이 나지 않을 수 있으니 나중에라도 꼭 이름을 붙여주자.

자 그런데 일단 chainable? 함수가 있다고 치자. 아주 잘 작동한다. 그 다음은 어떻게 해야 하는 지를 먼저 고민해 볼 수 있다. 코딩에 들어가기 전에…

큰 전투

결국 큰 전투를 위한 전략에 대한 구체적인 착상에 들어가야 한다. 다시 위에서 우리가 Test들을 해봤던 것을 관찰해 보자. 우리 인간이 했던 것을 컴퓨터가 똑같이 할 수 있도록 만들 수 있다면(믿어라. 클로저는 그게 가능하다. 미로 생성기를 기억해 보라.) 우리가 했던 것을 자세히 관찰하고 그것을 절차적 방식으로 풀어낼 수만 있다면, 그것을 클로저로 구현할 수 있다.

Peter Norvig's Rule of English Translation.

To insure that you say what you mean:

  1. Start with an English description of the algorithm
  2. Write the code from the description
  3. Translate the code back to english
  4. 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개의 단어를 갖는 집합이다.

다음과 같은 절차를 만들어 볼 수 있다.

  1. 임의의 단어를 선택한다.
  2. 그 단어와 c?인 단어를 임의로 찾는다.
  3. 2에서 c?인 단어가 없으면 1로 돌아간다
  4. 2에서 c?인 단어가 있으면 2로 돌아간다.

대충 이렇게 문장으로 절차적 표현한다. 이걸 우리가 머리속에서 돌려보자.

2 단계

hat으로 시작하자. c2인 단어를 찾으니 oat와 hot 2개가 나온다. 이런 하나가 아니라 여러 개 나올 수 있다… 그래서 절차는 다음과 같이 바뀌어야 한다.

  1. 처음 집합에서 임의의 단어를 선택한다.
  2. 그 단어와 c?인 단어들의 집합을 찾는다.
  3. 2에서 구한 집합이 공집합이면 1로 돌아간다.
  4. 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

  1. 처음 집합에서 임의의 단어를 선택한다.
  2. 그 단어와 c?인 단어들의 집합을 찾는다.
  3. 2에서 구한 집합이 공집합이면 1로 돌아간다.
  4. 2에서 구한 집합에서 임의 단어를 취하고 2로 돌아간다.

최종 함수

c? 함수

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

c? by maximental

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

c? 함수 by chouser

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

cs? 함수

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

cs? 함수 by maximental

(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)]))

코드 읽기

“사람들은 내가 쉽게 작곡한다고 생각하지만 이건 실수라네. 단언컨대 친구여, 나만큼 작곡에 많은 시간과 생각을 바치는 사람은 없을 걸세. 유명한 작곡가의 음악 치고 내가 수십 번에 걸쳐 꼼꼼하게 연구하지 않은 작품은 하나도 없으니 말이야.” - 모짜르트가 친구에게 보낸 어느 편지에서

4clojure_문제풀이.txt · Last modified: 2019/02/04 14:26 (external edit)