그리디 알고리즘(Greedy Algorithm)이란?

 

개념

그리디 알고리즘은 "탐욕 알고리즘" 또는 "욕심쟁이 알고리즘" 이라고도 불린다.

말 그래도 탐욕스러운 욕심쟁이이기 때문에 선택의 순간마다 최적의 선택을 하여 전체적으로도 최적이길 바라는 방법이다.

 

선택의 순간마다 최적의 선택을 하여 해답을 만들었다고 해서 그것이 최적의 해답이라는 보장은 없다.

하지만 탐욕 알고리즘을 적용하는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

 

 

 

탐욕 알고리즘을 적용하기 위한 2가지 조건

1. 탐욕스러운 선택 조건 (Greedy Choice Property)

    => 앞의 선택이 이후의 선택에 영향을 주지 않는 것

2. 최적 부분 구조 조건 (Optimal Substructure)

    => 문제에 대한 최적해가 부분 문제에 대해서도 최적해라는 것

 

• 위 조건이 성립하지 않는 경우 탐욕 알고리즘은 최적해를 구하지 못한다.
• 하지만 이런 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.
• 이 경우 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.
• 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이런 구조를 매트로이드라 한다.
• 매트로이드는 모든 문제에서 나타나진 않지만, 여러 곳에서 발견되기에 탐욕 알고리즘의 활용도를 높여준다.

 

🧐 근사 알고리즘(Approximation Algorithm)이란?
어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘이다.
이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하여 어느 정도 보장된 근사해를 계산할 수 있다.

 

 

 

 

구현

정렬과는 달리 정해진 것이 없으므로 탐욕 알고리즘을 사용한 문제를 가져와서 설명해보자.

더블릿 사이트 - knapsack 문제 를 설명해보겠다.

 

🖥 문제 내용
도둑이 보석상에 침입하여 보석을 훔쳐가려고 한다.
그런데 도둑이 가져갈 수 있는 보석의 무게(n)은 한정되어 있다.
각각의 보석의 무게(weight)와 값(value)을 가지고 있다.
무게 n으로 어떤 보석을 가져가는게 가장 많은 이윤을 취할 수 있는가를 구하는 문제이다.
단, 보석을 쪼갤 수 있고 종류당 하나씩 있다고 하자.

🖥 입력 방법
입력의 첫 줄에는 도둑이 가져갈 수 있는 무게를, 다음 줄에는 보석의 개수, 다음 줄부터는 각 보석의 무게와 값이 한 줄에 하나씩 입력된다.

🖥 출력 방법
첫 줄에는 최대 이윤을 출력한다.
보석의 개수는 최대 1000개까지이고 무게와 가치는 모두 정수값이다.
출력은 소수 3번째 자리에서 반올림하여 2자리까지 출력한다.

🖥 입출력 예
입력
30
3
5 50
10 60
20 140
출력
220.00

 

문제 해결 과정

1. 도둑이 가져갈 수 있는 가치가 가장 높은 보석을 선택한다.

    => 이 때 가장 비싼 보석이 아닌, 무게당 값이 비싼 보석으로 선택해야한다.

2. 보석의 무게가 도둑이 가져갈 수 있는 무게보다 작을 때, 보석을 챙긴 뒤 1번으로 이동하여 반복한다.

3. 보석의 무게가 도둑이 가져갈 수 있는 무게보다 클 때, 보석을 쪼갠 뒤 챙겨서 반복을 끝낸다.

    => 이 때는 도둑이 가져갈 수 있는 무게를 끝까지 채웠으므로 끝내는 것

4. 만약 가져갈 수 있는 보석이 없을 때도 끝낸다.

 

#include <stdio.h>
#define M 1010
#include <algorithm>
using namespace std;
 
struct temp
{
    int w, v;   // 무게, 가격
    double avg; // 무게당 가격
} a[M];
 
int chk(temp i, temp j) // sort 정렬 기준
{
    return (i.avg > j.avg);
}
 
int main()
{
    int i, n, m;
    double sum = 0;
 
    // 입력을 받는다.
    scanf("%d", &m); // 도둑이 가져갈 수 있는 무게
    scanf("%d", &n); // 보석의 개수
    for (i = 0; i < n; i++)
    {
        scanf("%d %d", &a[i].w, &a[i].v);   // temp 객체를 만들어서 무게와 가격을 입력받는다.
        a[i].avg = (double)a[i].v / a[i].w; // 현재 temp[i] 객체의 avg에 무게당 가격을 넣는다.
    }
 
    // 정렬한다.
    sort(a, a + n, chk);
    i = 0;
 
    // 도둑이 가져갈 수 있는 최대 이윤을 구한다.
    while (true)
    {
        // 만약 보석의 개수만큼 인덱스가 돌려졌다면 도둑이 가져갈 수 있는 무게는 많지만 보석이 없는 경우이므로 멈춘다.
        if (i == n)
            break;
        // 도둑이 가져갈 수 있는 무게가 현재 보석의 무게보다 많을 때
        if (m >= a[i].w)
        {
            m -= a[i].w;   // 도둑이 가져갈 수 있는 무게를 뺀다.
            sum += a[i].v; // 최대 이윤에 현재 보석의 가격을 더한다.
        }
        // 도둑이 가져갈 수 있는 무게가 현재 보석의 무게보다 적을 때
        else
        {
            // 보석을 쪼개서 남은 무게만큼만 가져가기 때문에 (도둑이 가져갈 수 있는 무게 * 보석의 무게당 가격) 으로 가격을 정해 최대이윤에 더한다.
            sum += (m * a[i].avg);
            // 여기까지 왔다면 도둑이 가져갈 수 있는 무게는 0이므로 멈춘다.
            break;
        }
        i++;
    }
 
    // 출력한다.
    printf("%.2lf", sum);
    return 0;
}

 

 

---

참고

https://ko.wikipedia.org/wiki/탐욕_알고리즘