Greedy Algorithm

Greedy Algorithm

동빈나님의 블로그와 위키피디아를 참고해서 정리했음을 밝힙니다.
링크: https://blog.naver.com/ndb796/221242106787

 

그리디 알고리즘: 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘

 

특징

• 항상 최적의 결과를 도출하는 것은 아니지만 어느정도 최적의 해에 근사한 값을 빠르게 구할 수 있다.
• '특정한 상황'에 있어서 최적의 해를 보장할 수도 있다.

 

---

언제 쓰는가?

• 탐욕스러운 선택조건, 최적 부분 구조 조건 두 가지 조건이 만족할 경우
  • 탐욕스러운 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것
  • 최적 부분 구조 조건: 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해이다.

• 매트로이드: 일차 독립의 성질을 공리화하여 얻은 주합론적 구조

  • 매트로이드가 있는 문제에 대해서는 항상 최적해를 도출할 수 있다.

• 예제: 거스름돈 문제, 분할가능 배낭문제 등

  • 560원을 거슬러 줄 때, 동전의 수가 가장 적은 경우는
    • 500원 1개, 50원 1개, 10원 1개
  • 이때 순간의 최선의 선택을 보자.
    • 500원 하나를 고른 후 60원이 남는다.
    • 50원 하나를 고른 후 10원이 남는다.
    • 10원 하나를 고른 후 0원이 남는다.
      • 순간의 선택이 이후에 영향을 주지 않는다.
      • 순간의 최적 선택이 문제 최적해와 일치한다.
  • 따라서, 이 문제는 탐욕 알고리즘으로 해결이 가능하다.

 

---

알고리즘

1. 해 선택(Selection Procedure): 지금 순간의 최적인 해를 구한 뒤, 이를 부분 해집합에 추가한다.
2. 적절성 검사(Feasibility Check): 새로운 부분 해집합이 적절한지 검사한다.
3. 해 검사(Solution Check): 새로운 부분 해집합이 문제의 해가 되는지 검사. 문제의 해가 완성되지 않았다면 1번부터 다시 시작.

위 거스름돈 문제를 적용해 보자.

1. 해 선택: 가장 높은 동전을 우선으로 구성한다.
   • 현재 고를 수 있는 가장 큰 금액의 동전을 골라 부분 해집합에 추가한다.
2. 적절성 검사: 부분 해집합이 거슬러 줄 금액을 초과하는지 검사한다.
   • 초과할 경우 최근에 추가한 동전 삭제, 1번으로 돌아간다.
   • 최근에 고른 동전보다 아래의 금액을 고른다.
3. 해 검사: 부분 해집합이 거슬러 줄 금액과 일치하는지 검사한다.
   • 금액이 거슬러줄 돈보다 작을 경우 1번부터 다시 부분 해집합에 동전을 추가한다.

 

---

가장 최근에 그리디 알고리즘으로 열심히 풀었으나 이 알고리즘으로는 해결이 불가한 문제가 있었다.
이런 경우에 동적 계획법이나 기타 알고리즘 기법을 적용해야 한다.

 

https://www.acmicpc.net/problem/1106
그리디 알고리즘 적용 풀이

1106번: 호텔

 

이 코드는 정답코드가 아님을 밝힌다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    int Ashare = a.first / a.second; // 1인당 드는 비용
    int Amod = a.first % a.second;
    int Bshare = b.first / b.second;
    int Bmod = b.first % b.second;

    if (Ashare == Bshare)
        return Amod < Bmod;
    return Ashare < Bshare;
}

int main() {
    int c, n;
    vector<pair<int, int>> list;
    cin >> c >> n;
    while (n--) {
        pair<int, int> info;
        cin >> info.first >> info.second;
        list.push_back(info);
    }
    sort(list.begin(), list.end(), compare);

    int cost = 0;
    for (int i = 0; i < list.size(); i++) {
        while (list[i].second <= c) {
            int temp = c - list[i].second;
            if (temp >= 0) {
                c = temp;
                cost += list[i].first;
            }
            else
                break;
        }
    }
    cout << cost << endl;

    return 0;
}