- Learn about Wiki
- Lectures
- Study
- Tips
- study:algorithms:greedy
탐욕법(그리디 알고리즘)
- 탐욕적 선택(국소적 선택, 그리디 선택)으로 문제의 해를 구하는 방법
- 주로 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++ 구현
const double pi = 2.0 * acos(0) int n; double y[100], x[100], r[100]; void convertToRange() { for (int i = 0; i < n; ++ i) { double loc = fmod(2*pi + atan2(y[i], x[i]), 2*pi); double range = 2.0 * asin(r[i] / 2.0 / 8.0); ranges[i] = make_pair(loc - range, loc + range); } //각 구간을 시작 위치가 작은 것부터 오게끔 정렬한다. sort(ranges, ranges+n); }
Clojure 구현
study/algorithms/greedy.txt · Last modified: 2019/02/04 14:26 (external edit)