Greedy Algorithm

Greedy Algorithm이란?

Greedy algorithm이란 이후의 상황을 고려하지 않고 각 단계에서 최선의 선택을 하는 알고리즘이다. 이는 dynamic programming이 너무 많은 일을 한다고 판단하는 것에서 시작한 알고리즘이다. 그러나 이는 local maxima, local minima 문제로 모든 경우에 적용될 수 있는 것은 아니다.

Greedy Algorithm vs Dynamic Programming

Greedy Algorithm
- 하나의 subproblem이 발생
- Subproblem이 해결되기 전에 선택 실시
- Fractional knapsack (분할 가능 배낭 문제)

Dynamic Programming
- 여러 subproblem이 발생
- Subproblem이 해결된 후 선택 실시
- 0/1 knapsack (분할 불가능 배낭 문제)

동전 문제

기본적인 greedy algorithm 문제로 동전문제가 있다.
(문제) 500원, 100원, 10원짜리 동전으로 710원을 만들때, 최소 동전의 개수는?
(해결) 가장 액수가 큰 동전부터 하나씩 늘려가면서 710원을 만들어보면 된다.

int coin(int n) {
    int result = 0;  
    result += (n / 500);
    n %= 500;
    result += (n / 100);
    n %= 100;
    result += (n / 10);
    return result;
}

위의 코드와 같이 해결하면 500원 1개, 100원 2개, 10원 1개로 총 4개의 동전으로 지불할 수 있다는 결과를 얻을 수 있다.

그러나 이는 local minima 문제로 항상 사용할 수 없다. 아래의 예시를 참고해보자.
(문제) 10원, 30원, 40원, 50원짜리 동전으로 70원을 만들때, 최소 동전의 개수는?
(해결)
greedy algorithm에 따른 결과:
- 50원 1개, 10원 2개 (총 3개의 동전이 필요함)

실제 최소 동전을 이용하는 결과:
- 30원 1개, 40원 1개 (총 2개의 동전이 필요함)

따라서 문제별로 greedy algorithm을 적용할 수 있는지 확인하는 것이 중요하다.

시간표 문제

한 회의실에서 여러 회의가 진행된다고 하자. 각 회의의 시작시간과 종료시간을 입력받아서 가장 많은 회의를 배정하는 알고리즘을 만드는 문제이다.

위와 같은 스케줄표가 주어질때, 결과를 구하는 문제이다. 결론적으로 [A1, A3, A6, A8]이나 [A1, A3, A7, A9]를 얻게 된다. 이는 직관적으로 각 시점에서 후보 중 가장 빨리 끝나는 회의를 고르는 방식으로 알고리즘을 짜면 된다.

Fracional knapsack (분할 가능 배낭문제)

각 아이템마다 무게와 가치가 주어질 때, 해당 아이템들을 분할해서 넣을 수 있으므로 무게 대비 가치가 높은 아이템을 먼저 넣어준다.

위의 문제에서 무게 제한이 50인 가방에 상품을 담는다고 가정하자.

dynamic programming으로 해당 문제를 해결하는 경우: 0-1 knapsack 이용
[2,3] : $220
[1,3] : $180
[1,2] : $160
위와 같은 결과를 얻으므로 [2,3]을 선택하는 것이 가장 최적이다.

greedy algorithm으로 해당 문제를 해결하는 경우: fractional knapsack 이용
[1,2,3] : $240
가치가 높은 순서대로 담는다. 이 경우 3번 상품은 나눠서 담게 된다.