User Tools

Site Tools


Sidebar

  • Learn about Wiki
  • Lectures
  • Study
  • Tips
    • study:algorithms:bruteforce

      6장 무식하게 풀기(brute-force)

      • 가능한 경우를 일일이 나열하면서 답을 찾는 방법.
      • 완전 탐색(exhaustive search)이라고도 함.

      6.1. 재귀 호출과 완전탐색

      [반복문 사용]

      • 가능한 경우를 탐색하는 하나의 방법.

      <1부터 n까지의 합을 계산하는 반복함수>

      // 필수 조건: n >= 1
      // 결과: 1부터 n까지의 합을 반환한다.
      int sum(int n) {
        int ret = 0;
        for (int i = 1; i <= n; i++)
          ret += i;
        return ret;
      }

      [재귀 함수]

      • 자기 자신을 호출하는 함수.

      재귀함수의 구조

      기저 사례(base case)
      • 입력된 문제가 더 이상 줄일 수 없을 만큼 작을 때를 말한다.
      • 특정한 작업을 하고 리턴한다.
      재귀 호출 단계
      • 현재 단계에서 할 수 있는 작업을 수행하고, 입력된 문제를 더 작은 문제로 줄여서 푼다.
      • 더 작은 문제를 푼다는 것은 더 작은 입력으로 자신을 호출하는 것이다.
      • 이 때 재귀 호출에서 리턴되면 수행할 작업이 남아 있을 수도 있고(되도는 프로세스), 그렇지 않을 수도(반복하는 프로시저) 있다.

      재귀함수를 반복문으로 사용

      • 재귀함수의 입력을 하나의 조각과 나머지 조각으로 분리하여, 나머지 조각을 다시 입력으로 자신을 호출.

      <1부터 n까지의 합을 계산하는 재귀함수>

      C++
      // 필수 조건: n >= 1
      // 결과: 1부터 n까지의 합을 반환한다.
      int recursiveSum(int n) {
        if (n == 1) return 1; // 더이상 쪼개지지 않을 때 
        return n + recursiveSum(n-1);
      }
      Cojure
      ;;; 되도는 프로세스
      (defn sum [n]
        (if (<= n 0)
          0
          (+ n (sum (dec n)))))
      ;;; 반복하는 프로시저(꼬리 되돌기) #1
      (defn sum [n]
        (letfn [(sum-iter [x acc]
                  (if (<= x 0)
                    acc
                    (recur (dec x) (+ acc x))))]
          (sum-iter n 0)))
      ;;; 반복하는 프로시저(꼬리 되돌기) #2
      (defn sum [n]
        (loop [x n
               acc 0]
          (if (<= x 0)
            acc
            (recur (dec x) (+ acc x)))))

      <1부터 n까지의 합을 계산하는 또 다른 방법(Cojure)>

      ;;; 리스트와 반복하는 프로시저(꼬리 되돌기) 
      (defn sum [n]
        (loop [lst (range 1 (inc n))
               acc 0]
          (if (empty? lst)
            acc
            (recur (rest lst) (+ acc (first lst))))))
      ;;; 리스트와 reduce를 사용하는 방법
      (defn sum [n]
        (reduce #(+ % %2) (range 1 (inc n))))
      ;;; 리스트와 apply를 사용하는 방법
      (defn sum [n]
        (apply + (range 1 (inc n))))

      [예제: 중첩 반복문 대체하기]

      문제:

      • n개의 원소 중 네 개를 고르는 방법 나열하기

      C++

      // n:전체 원소의 수
      // picked: 지금까지 고른 원소들의 번호
      // toPick: 더 고를 원소의 수
      // 일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
      void pick(int n, vector<int>& picked, int toPick) {
        // 기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력한다.
        if (toPick == 0) { printPicked(picked); return; }
        // 고를 수 있는 가장 작은 번호를 계산한다.
        int smallest = picked.empty() ? 0 : picked.back() + 1;
        // 이 단계에서 원소 하나를 고른다.
        for (int next = smallest; next < n; ++next) {
          picked.push_back(next);
          pick(n, picked, toPick - 1);
          picked.pop_back();
        }
      }

      Clojure

      ;;; #1 기본 변환(C++ -> Clojure)
      (defn combination [n k]
        (letfn
            [(comb-iter [picked-lst n-to-pick] 
               (if (= n-to-pick 0)
                 (println picked-lst)
       
                 (let [smallest (if (empty? picked-lst)
                                  0
                                  (inc (last picked-lst)))]
       
                   (loop [next smallest]
                     (if (not (< next n))
                       nil
                       (do
                         (comb-iter (conj picked-lst next) (dec n-to-pick))
                         (recur (inc next))))))))
             ]
          (comb-iter [] k)))
       
      (combination 5 4)
      (combination 6 3)
      ;;; #2 리스트를 이용한 루프
      (defn combination [n k]
        (letfn
            [(comb-iter [picked-lst n-to-pick] 
               (if (= n-to-pick 0)
                 (println picked-lst)
       
                 (let [smallest (if (empty? picked-lst)
                                  0
                                  (inc (last picked-lst)))]
       
                   (loop [seq (range smallest n)]
                     (if (empty? seq)
                       nil
                       (let [next (first seq)]
                         (comb-iter (conj picked-lst next) (dec n-to-pick))
                         (recur (rest seq))))))))
             ]
          (comb-iter [] k)))
       
      (combination 5 4)
      ;;; #3 map으로 리스트 루프를 대체.(문제있음-클로저 버그?)
      (defn combination [n k]
        (letfn
            [(comb-iter [picked-lst n-to-pick] 
               (if (= n-to-pick 0)
                 (println picked-lst)
       
                 (let [smallest (if (empty? picked-lst)
                                  0
                                  (inc (last picked-lst)))]
       
                   (map (fn [next]
                          (comb-iter (conj picked-lst next) (dec n-to-pick)))
                        (range smallest n)))))
             ]
          (comb-iter [] k)))
       
      (combination 5 4)
      ;;; #4 값으로 리턴.(불완전)
      (defn combination [n k]
        (letfn
            [(comb-iter [picked-lst n-to-pick] 
               (if (= n-to-pick 0)
                 picked-lst
       
                 (let [smallest (if (empty? picked-lst)
                                  0
                                  (inc (last picked-lst)))]
       
                   (loop [seq (range smallest n)
                          acc []]
                     (if (empty? seq)
                       acc
                       (let [next (first seq)]
                         (let [res (comb-iter (conj picked-lst next) (dec n-to-pick))]
                           (recur (rest seq) (conj acc res)))))))))
             ]
          (comb-iter [] k)))
       
      (combination 5 4)
      ;;; #5 값으로 리턴.
      (defn combination [n k]
        (letfn
            [(comb-iter [picked-lst n-to-pick acc]
               (if (= n-to-pick 0)
                 (do
                   ;; (println n-to-pick "***" picked-lst "***")
                   (conj acc picked-lst))
       
                 (let [smallest (if (empty? picked-lst)
                                  0
                                  (inc (last picked-lst)))]
       
                   (loop [seq (range smallest n)
                          acc2 acc]
                     (if (empty? seq)
                       acc2
                       (let [next (first seq)]
                         (let [res (comb-iter (conj picked-lst next) (dec n-to-pick) acc2)]
                           ;; (println n-to-pick "---" res "---")
                           (recur (rest seq) res))))))))
             ]
          (comb-iter [] k [])))
       
      (combination 5 4)
      (combination 5 3)
      (combination 4 3)

      Scheme

      ;;; #3 map으로 리스트 루프를 대체.(map,recursive call 조합 정상동작.)
      (define (combination n k)
        (define (comb-iter picked-lst n-to-pick)
          (if (= n-to-pick 0)
      	(begin
      	  (display (reverse picked-lst))
      	  (newline))
       
      	(let ((smallest (if (null? picked-lst)
      			    0
      			    (+ (car picked-lst) 1)))) 
      	  (map (lambda (next)
      		 (comb-iter (cons next picked-lst) 
      			    (- n-to-pick 1)))
      	       (my-range smallest n)))))
        (comb-iter '() k)
        '())
       
      (combination 5 4)

      [예제: 보글 게임]

      문제

      • 지정된 5×5 크기의 알파벳 격자에서 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾는 것이 목표이다.
      • 입력: 시작 좌표(행,열), 찾는 문자열

      C++

      // 5x5의 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환
      bool hasWord(int y, int x, const string& word) {
        // 기저 사례 1: 시작 위치가 범위 밖이면 무조건 실패
        if (!inRange(y, x)) return false;
       
        // 기저 사례 2: 첫 글자가 일치하지 않으면 실패
        if (board[y][x] != word[9]) return false;
       
        // 기저 사례 3: 단어 길이가 1이면 성공
        if (word.size() == 1) return true;
       
        // 인접한 여덟 칸을 검사한다.
        for (int direction = 0; direction < 8; ++direction) {
          int nextY = y + dy[direction], nextX = x + dx[direction];
          // 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
          if (hasWord(nextY, nextX, word.substr(1)))
            return true;
        }
       
        return false;
      }

      Clojure

      (def dx [-1, -1, -1,  1,  1,  1,  0,  0])
      (def dy [-1,  0,  1, -1,  0,  1, -1,  1])
       
      (def board [ ['U, 'R, 'L, 'P, 'M]
                   ['X, 'P, 'R, 'E, 'T]
                   ['G, 'I, 'A, 'E, 'T]
                   ['X, 'T, 'N, 'Z, 'Y]
                   ['X, 'O, 'Q, 'R, 'S]])
       
      (defn in-range [y x]
        (if (or (< y 0) (< x 0))
          false
          (if (or (> y 5) (> x 5))
            false
            true)))
       
      (defn has-word [y x word]
        (cond (not (in-range y x)) false
              (not (= (str (get-in board [y x])) (str (first word)))) false
              (= (count word) 1) true
              :else
               (loop [direction 0]
                 (if (>= direction 8)
                   false
                   (let [ny (+ y (nth dy direction))
                         nx (+ x (nth dx direction))]
                     (if (has-word ny nx (apply str (rest word)))
                       true
                       (recur (inc direction))))))))
       
      (has-word 1 1 "PRETTY")
      study/algorithms/bruteforce.txt · Last modified: 2019/02/04 14:26 (external edit)