User Tools

Site Tools


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)