- Learn about Wiki
- Lectures
- Study
- Tips
Elementary | 32 |
---|---|
Easy | 53 |
Medium | 45 |
Hard | 23 |
Total | 153 |
;;; #82. Word Chains, 2013.01.18 20:59 ~ 2013.01.
; 먼저 문제 서술을 정확하게 이해한다.
; 각 테스트를 둘러본다. ; 종이 노트를 적극 활용한다.
___________ | | 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
cot-hot bat-fat
to-top-stop | tops-toss
-------------- | | 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
share-shares-hares 1. are-hare-share-shares-hares | | hare----------- | are
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:
먼저 Test1을 살펴보자.
우리는 임의 단어로부터 시작해서 chainable? 단어를 따라 갔다. 따라 가면서 각 단어를 한 번만 거쳐야 한다. 그러면서 모든 단어를 거칠 수 있어야 한다. 이것은 모든 단어가 chainable? 관계로 순서지어졌다는 얘기다(whole-chainable-sequence? 이거 이름이 좋다. 이거 쓰자. 하지만 넘 길다. 일단 잠시 작업하는 동안은 줄여서 chainable? 은 c?로, whole-chainable-sequence?는 wcs?로 하자.). 따라 가다 보면 갈림길에서는 한 쪽 길로 가게 된다. 끝에 도달하지 않으면 다시 갈림길로 돌아와서 다른 쪽 길로 가서 끝에 도달하는지 확인해야 한다.
자 원래 문제를 보자. 입력이 #{“hat” “coat” “dog” “cat” “oat” “cot” “hot” “hog”} 로 되어 있다. 8개의 단어를 갖는 집합이다.
다음과 같은 절차를 만들어 볼 수 있다.
대충 이렇게 문장으로 절차적 표현한다. 이걸 우리가 머리속에서 돌려보자.
hat으로 시작하자. c2인 단어를 찾으니 oat와 hot 2개가 나온다. 이런 하나가 아니라 여러 개 나올 수 있다… 그래서 절차는 다음과 같이 바뀌어야 한다.
처음 집합에서 hat을 선택하면 c2인 단어들 #{hot oat}를 구하게 될 것이다. 여기서 hot를 취한다. 다시 c2인 단어들 #{cot hog}을 구하게 된다. hog를 취하면 #{dog}를 구하게 된다. dog를 취하면 #{}이다. 하지만 아직 단어를 다 거친 것이 아니기 때문에 cs?가 아니다.
이 과정을 값들만 나열해 보자.
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? 함수
(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)]))
“사람들은 내가 쉽게 작곡한다고 생각하지만 이건 실수라네. 단언컨대 친구여, 나만큼 작곡에 많은 시간과 생각을 바치는 사람은 없을 걸세. 유명한 작곡가의 음악 치고 내가 수십 번에 걸쳐 꼼꼼하게 연구하지 않은 작품은 하나도 없으니 말이야.” - 모짜르트가 친구에게 보낸 어느 편지에서