sk-choi

This is the place that record about something today I learned.

그리디(Greedy)

그리디란??

Untitled

강철의 연금술사라는 애니메이션을 보면 호문클루스라는 악역들이 나온다. 인간이 지닌 7개의 대죄를 바탕으로 만들어진 캐릭터들인데, 여기서 탐욕을 상징하는 캐릭터가 바로 그리드라는 캐릭터이다.

여기서 알 수 있듯이 그리디라는 말은 탐욕적인 알고리즘을 의미한다. 바로 현재 상황에서 가장 좋은 것만을 고르는 것이다.

거스름돈 문제

그리디 알고리즘의 대표적인 예시로는 바로 거스름돈 문제가 있을 것이다. 거스름돈 문제에서 당신은 최소 동전의 개수로 돈을 거슬러 줘야 한다. 이를 위해선 바로 가장 큰 화폐단위부터 거슬러주어야 한다. 즉 현재 상황에서 가장 큰 것을 골라야 하는 그리디 알고리즘이 이러한 문제를 해결하는데 안성 맞춤인 것이다.

한국의 동전은 500, 100, 50, 10원으로 이루어져 있다. 만약 거스름돈이 1340원이라면 우선 가장 큰 500원짜리를 통해 돈을 거슬러 준다. (500*2 = 1000)

그리고 나머지 340원을 백원짜리로 거슬러준다. (100*3 = 300)

남은 것은 40원이므로 10원짜리 4개로 거슬러준다.

그렇다면 결과적으로 2+3+4 = 9개로 동전을 거슬러 줄 수 있게 된다.

코드

exchange = 1340
coins = [500, 100, 50, 10]
count = 0

for coin in coins:
	count += exchange // coin
	exchange %= coin

print(count)

백준 5585번 문제인 ‘거스름돈’을 C++로 풀어보면 다음과 같다.

백준 5585 - 거스름돈

C++ 코드

#include <iostream>
using namespace std;

//500, 100, 50, 10, 5, 1

int main()
{
    int input; 
    cin >> input;
    int rest = 1000 - input;
    int count = 0;

    rest / 500;
    count += (rest / 500);
    rest = rest % 500;
    rest / 100;
    count += (rest / 100);
    rest = rest % 100;
    rest / 50;
    count += (rest / 50);
    rest = rest % 50;
    rest / 10;
    count += (rest / 10);
    rest = rest % 10;
    rest / 5;
    count += (rest / 5);
    rest = rest % 5;
    rest / 1;
    count += (rest / 1);
    rest = rest % 1;

    cout << count;
    return 0;

}

이산수학에서의 그리디 알고리즘

이산수학에서의 그리디 알고리즘은 어떨까? 사실 위에서 설명한 것과 크게 다르지 않다. 다만 이산수학에서는 그래프에서의 spanning tree를 찾기 위한 방법으로 제시된다.

Untitled

그래프 G의 부분 그래프 G’이 다음의 두 조건을 만족할 때, G’을 G의 spanning tree라고 한다.

(1) V’ = V

(2) G’은 수형도

결국 spanning tree란 그래프 G의 모든 꼭짓점을 가지는 Tree(수형도)라고 볼 수 있을 것이다.

이러한 spanning tree를 찾기 위해서 그래프에서 변을 제거하여도 남은 그래프가 여전히 연결그래프인 변 중 가장 큰 값을 갖는 변을 제거하는 것이 이산수학에서의 그리디 알고리즘이다.

즉 cost가 큰 값부터 제거하는 것이다.

Kruskal 알고리즘

그리디 알고리즘이 가장 큰 것을 선택하는 것이라면 krustal 알고리즘은 이와 반대로 가장 작은 것부터 선택하는 것이라고 할 수 있다.

그래프에서 가장 작은 값을 변을 선택하고 만약 같은 값을 가진 변이 있으면 임의로 한 변을 제거하는 형식을 통해서 spanning tree를 구하는 것이다. 이 때, 선택한 변이 회로를 구성하지 않아야 한다.

참고