Greedy algorithm, 탐욕법

Greedy - 탐욕스러운, 욕심 많은

그리디 알고리즘은 이름 그대로 선택의 순간이 될때마다 당장 눈앞의 최적의 상황만을 선택하여 최종적인 답에 도달하는 방법이다.

 

최적의 상황이란?

최적의 상황의 예시를 들어보자

루트노드에서 가장 깊은 레벨의 노드까지의 최대합을 구하는 경로를 구해본다고 생각해보자.

 여기서 탐욕스러운 방법을 이용한다면 1부터 시작해서 12보다 큰 23을 선택한다 그리고 36 37 중 더 큰 37을 선택하여 잘못된 값을 선택하게 될것이다.

 그래서 실제로 그리디 알고리즘을 활용할 경우는 이러하게 간단히 선택할 수 없다.

 

그리디 알고리즘으로 문제를 해결하는 방법은 다음과 같다.

1. 선택 : 현재 상태에서 최적의 해답을 고른다.
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

그리디 알고리즘이 잘 작동하는 문제는 탐욕 선택 조건과 최적 부분 구조 조건이라는 두가지 조건을 만족한다.

탐욕 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주면 안된다.

최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대하여 최적 문제 해결 방법으로 구성

 

그리디 알고리즘을 이용하기 위한 조건은 탐욕적 선택은 항상 안전하다는 보장이 되어야 한다. 안전하다는 것은 선택했을때 반드시 최적해를 도출할 수 있어야 한다는 것이다.

또한 여러 선택들 중 각 선택들 모두 최적해가 도출이 되어야 한다.

 

위의 그림에서 탐욕 방법으로 도출한 최종 결과는 1 + 23 + 37 = 61이다. 이때 142라는 값은 23보다 작은 12의 아래에 있으므로 선택하지 않게 된다.

 

거스름돈 문제

그리디 알고리즘을 활용하는 일반적인 문제로 거스름돈 문제가 있다.

당신은 영화관 카운터에서 일하는 아르바이트생이다. 
카운터에는 거스름돈을 사용할 동전 500, 100, 50, 10원이 있다.
손님에게 거슬러주어야 할 돈이 N원일 경우 거슬러주어야 할 동전의 최소 개수를 구해라.
(한자리수 단위의 돈은 취급하지 않는다. ex 1원은 없다.)

이 문제에서 생각할 수 있는 것은 가장 큰 단위의 돈부터 생각하는 것이다.

만약 6720원이라는 돈을 거슬러주어야 한다고 해보자.

 

이 돈을 거슬러 줄 수 있는 방법은 매우 많다.

10원만 사용해서 거슬러주는 방법, 10원과 50원을 조합하는 방법 등 여러가지 방법이 있을것이다.

하지만 여기서 필요한 방법은 최소의 동전 갯수이므로 가장 큰 단위부터 거슬러 주면서 작은 단위로 거슬러 주면 될것이다.

class Solution {
private:
  int a[4] = { 500, 100, 50, 10 };
public:
  int change(int money) {
    int count = 0;
    int tmp1 = money;
    int tmp2 = money;

    int i = 0;
    while (tmp1 > 0) {
      while (tmp1 < a[i]) {
        i += 1;
      }
      tmp1 %= a[i];
      tmp2 = tmp2 - tmp1;
      count += tmp2 / a[i];
      tmp2 = tmp1;
    }

    return count;
  }
};

간단하게 작성해본 알고리즘이다.

위의 예시인 6720원을 거슬러 주어야 한다고 했을때 17이 결과로 나온다.

(5 * 13) + (100 * 2) + (10 * 2) -> 17개

 

활동 선택 문제

N개의 활동이 있고 각 활동에는 시작/종료 시간이 있을 때, 한 사람이 최대한 많이 할수 있는 활동의 수를 구하는 문제이다.

각각 활동에는 시간이 소요되므로 하나의 활동을 선택했다면 그 시간과 겹치는 다른 활동을 선택할 수 없다.

 따라서 종료시간을 기준으로 정렬하여, 제일먼저 끝나는 활동을 선택하고 그 다음 선택할 수 있는 활동을 찾아서 수행하도록 한다.

내일은 대학교 강의 수강신청기간이다. 
강의 0, 1, 2, 3, 4, 5가 있다.
각 수강의 시작시간과 종료시간은 다음과 같다.
0: 7 ~ 8
1: 5 ~ 7
2: 3 ~ 5
3: 1 ~ 2
4: 8 ~ 10
5: 9 ~ 11
각각의 수강의 시작시간과 종료시간이 겹치지 않고, 가장 많은 수강을 들을 수 있도록 수강신청을 하는 방법을 찾아보자.

종료시간 기준으로 정렬한다면 아래와 같다

3 : 1, 2
2 : 3, 5
1 : 5, 7
0 : 7, 8
4 : 8, 10
5 : 9, 11 

그리고 종료시간과 겹치지 않도록 강의를 선택하면 된다.

그러면 3번, 2번 1번 0번, 4번을 선택할 수 있다.

코드로 작성하면 아래가 된다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
using ii = pair<int, int>;
using iii = pair<int, ii>;

bool compare(const iii& a, const iii& b) {
  return a.second.second < b.second.second;
}

class Solution {
private:
vector<int> answer;
public:
  vector<int> subject(vector<iii>& classes) {
    greedy(classes);
    return answer;
  }

  void greedy(vector<iii>& classes) {
    sort(classes.begin(), classes.end(), compare);
    int prevTime = 0;
    for(iii value: classes) {
      int className = value.first;
      int nextTime = value.second.first;
      if (nextTime >= prevTime) {
        prevTime = value.second.second;
        answer.push_back(value.first);
      }
    }
  }
};

int main() {
  vector<iii> classes = {
    iii(0, ii(7, 8)),
    iii(1, ii(5, 7)),
    iii(2, ii(3, 5)),
    iii(3, ii(1, 2)),
    iii(4, ii(8, 10)),
    iii(5, ii(9, 11))
  };

  Solution s;
  s.subject(classes);

  return 0;
}