DokuWiki

탐욕법(그리디 알고리즘)

• 탐욕적 선택(국소적 선택, 그리디 선택)으로 문제의 해를 구하는 방법
• 주로 2가지 사용
• - 탐욕법으로 최적해를 구할 수 있을경우는 효율성이 더 높아서 좋다.
• - 또는 최적해가 아니더라도 적당한 해를 구하려고 할 경우.
• 탐욕법이 어떤 특별한 최적화 문제를 풀 수 있는지 알 수 있는 일반적인 방법은 없다.
• 그리디 선택특성, 최적 부분 구조 라는 두가지 요소가 탐욕법을 적용하기 알맞다.

그리디 선택특성

• 국지적 최적 선택(=그리디 선택)으로 전체적인 최적해를 찾을 수 있다.
• 동적 계획법에서는 매 단계마다 선택을 해야하고 이 선택은 부분문제의 해에 의존하게 된다. 이렇게 더 작은 부분문제에서 더 큰 문제로 풀어가나가는 상향식 접근법이다.
• 탐욕법은 현재 가장 좋아보이는 것을 선택 후, 그 부분문제를 푼다. 이처럼 주어진 문제를 더 작은 문제로 만들기 때문에 하향식 접근법이다.
• 이를 위해, 매 단계에서 그리디 선택이 전체적인 최적해를 만들어 낼 수 있음을 증명해야 하는데, 이부분에서 총명, 경험, 노련미(?)가 필요하다.

<탐욕적 선택속성 증명하기 : 패턴 찾기> 탐욕법 알고리즘 설계의 좋은 방법은 패턴을 찾는 것.

1. 우리가 선택한 경우와 다른 경우에 최적해가 있다고 가정하고,
2. 그 최적해보다 선택한 경우가 같거나 더 나은 것을 증명한다.

최적부분구조

• 어떤 문제의 최적해가 그 부분문제의 최적해를 포함하고 있는 것
• 동적계획법, 그리디 알고리즘을 적용할 수 있을지 판단하는 중요 요소.

<동적 계획법 vs 그리디 알고리즘> 비교해보기

'0-1 배낭문제' 와 '분할가능 배낭문제' 를 살펴보자. (0-1배낭문제는 쪼갤수 없는 물건을 담는 문제)

둘다 최적 부분구조 특성을 가진다. 최적한 상태에서 가방에서 어떤 물건을 빼냈을 때, 그 공간과 물건을 뺀 나머지부분을 채울 수 있는 최적의 상태(또는 상태들 중 하나)는 지금이다.

하지만, 0-1문제는 그리디 방법은 불가하다.(최적해를 찾기 부적절하다) 즉 국소적인 어떤 선택 - 어떤 물건을 선택했을때, 그것이 최적인지 아닌지는 선택 했을때와 안했을때를 비교해봐야하기 때문이다.

그리디 방법의 이론적 기반

• 매트로이드

<스케쥴 문제>

C++ 구현

  int n;
  int begin[100], end[100];
  int schedule() {
      // 일찍 끝나는 순서대로 정렬한다. 
      vector<pair<int,int> > order;
      for(int i = 0; i < n; ++i)
          order.push_back(make_pair(end[i], begin[i]));
      sort(order.begin(), order.end());
      // earliest: 다음 회의가 시작할 수 있는 가장 빠른 시간
      // selected: 지금까지 선택한 회의의 수
      int earliest = 0, selected = 0;
      for(int i = 0; i < order.size(); ++i){
          int meetingBegin = order[i].second, meetingEnd = order[i].first;
 
          if(earliest <= meetingBegin) {
              // earliest 를 마지막 회의가 끝난 시간 이후로 갱신한다. 
              earliest = meetingEnd;
              ++selected;
          }
      }
      return selected;
  }

Clojure 구현

  (defn schedule [pair-lst]
    (let [ordered (sort-by first pair-lst)
          earliest (atom 0)
          selected (atom 0)]
      (loop [o ordered]
        (if (not (seq o))
          @selected
          (let [pair (first o)
                meetingBegin (second pair)
                meetingEnd (first pair)]
            (if (<= @earliest meetingBegin)
              (do (swap! earliest (fn [_] meetingEnd))
                  (swap! selected inc)
                  (recur (rest o)))
              (recur (rest o))))))))
 
  (defn schedule2 [pair-lst]
    (let [ordered (sort pair-lst)
          f (fn [[c fi] [fj sj]]
              (if (<= fi sj)
                [(inc c) fj]
                [c fi]))]
      (first (reduce f [0 0] ordered))))

<출전 순서 정하기>

C++ 구현

  int order(const vector<int>& russian,
            const vector<int>& korean) {
      int n = russian.size(), wins = 0;
      // 아직 남아있는 선수들의 레이팅
      multiset<int> ratings(korean.begin(), korean.end());
      for(int rus = 0; rus < n; ++rus) {
          // 가장 레이팅이 높은 한국 선수가 이길 수 없는 경우 
          // 가장 레이팅이 낮은 선수와 경기시킨다.
          if(*raings.rbegin() < russian[rus])
              ratings.erase(ratings.begin());
          // 이 외의 경우 이길 수 있는 선수 중 가장 레이팅이 낮은 선수와 경기시킨다.
          else {
              ratings.erase(ratings.lower_bound(russian[rus]));
              ++wins;
          }
      }
      return wins;
  }

Clojure 구현

(defn order [rus kor]
  (let [wins (atom 0)
        rating (atom (sort kor))
        erase-lower-bound (fn [l n] (concat (take-while #(< % n) l)
                                           (rest (drop-while #(< % n) l))))]
    (loop [r rus]
      (if (not (seq r))
        @wins
        (if (< (last @rating) (first r))
          (do (swap! rating rest) ; 무조건 지는 경우, 최약체 제거 
              (recur (rest r)))
          (do (swap! rating #(erase-lower-bound % (first r))) ; 이기는 경우, 그중에서
                                        ; 최약체 제거 
              (swap! wins inc)
              (recur (rest r))))))))
 
(defn order2 [rus kor]
  (let [rating (sort kor)
        f (fn [[wins rating] r]
            (if (< (last rating) r)
              [wins (rest rating)]
              [(inc wins) (concat (take-while #(< % r) rating)
                                  (rest (drop-while #(< % r) rating)))]))]
    (first (reduce f [0 rating] rus))))
 
 

<도시락 뎁히기>

  int n, e[MAX_N], m[MAX_N];
  int heat() {
      // 어느 순서로 데워야 할지를 정한다.
      vector<pair<int,int> > order;
      for (int i = 0; i < n; ++i)
          order.push_back(make_pair(=e[i], i));
      sort(order.begin(), order.end());
      //해당 순서대로 데워먹는 과정을 시뮬레이션한다.
      int ret = 0, beginEat = 0;
      for (int i = 0; i < n; ++i) {
          int box = order[i].second;
          beginEat += m[box];
          ret = max(ret, beginEat + e[box]);
      }
      return ret;
  }

clojure

(defn heat [dosirocks]
  (let [begin-eat (atom 0)
        sorted (reverse (sort-by second dosirocks))
        ret (for [[e m] sorted]
              (do
                (swap! begin-eat + e)
                (+ @begin-eat m)))]
    (apply max ret)))
 
(= (heat [[2 2] [2 2] [2 2]]) 8)
(= (heat [[1 2] [2 2] [3 1]]) 7)

<미나스 아노르>

C++ 구현