1. 그리디 개요

주어진 제약 조건을 만족하는 최적인 해를 구하는 문제에 주로 적용하는 알고리즘 설계 방법

• 최적화 문제 : 제약조건을 만족하며 목적함수의 값을 최대 혹은 최소로하는 해를 구하는 문제
• 주어진 문제의 해는 일력의 선택으로 나타낼 수 있고, 각 단계에서 xi를 결정한다
• 전체적인 입장에서 보지 않고, 현재 상태에서 최선의 판단을 내려 local optimum을 해로 한다

기본적인 알고리즘

// Solution(S) : 특정 후보들의 집합 S가 해인지 결정하는 함수
// Feasible(S) : 특정 후보들의 집합 S가 해가 될 가능성이 있는지 결정하는 함수
// Select(C) : 남은 후보 집합 C에서 현 상태에서 최선의 후보를 선택하는 함수

function Greedy(C) 
    S = ∅ 
    while (C != ∅ and !Solution(S)) 
        x = Select(C)
        C = C - {x}
        if (feasible(S ∪ {x}))
            S = S ∪ {x}
    
    if (Solution(S))
        return S
    else
        return ∅

2. 거스름돈 교환 문제

문제 : 여러 단위의 동전들이 주어져 있다. 거스름돈을 가장 적은 수의 동전으로 교환해주는 방법을 설명하라

1. 목적함수 : 사용 동전 개수
2. 후보 집합 C : {1원, 10원, ..., 500원}
3. Solution(S) : 선택한 동전들의 합이 거스름돈과 같은 경우 true
4. Feasible(S) : 선택한 후보들의 합이 거스름 돈을 넘지 않을 경우 true
5. Select(C) : 후보들 중 가장 단위가 큰 동전 선택

• 거스름돈 문제의 경우 일반적인 화폐 시스템에서 동전 단위 사용시 그리디로 최적해 계산이 보장된다

3. 평균적인 대기 시간을 최소로 하는 작업 스케쥴링

문제 : n개의 작업들이 있고, 각 작업 i를 처리하는데 걸리는 시간이 p(i)이다. 작업 가능한 사람이 한명일때, 작업들의 평균적인 대기시간을 최소로 하는 작업들의 처리 순서를 정하라

• 평균 대기 시간 = 전체 대기 시간 / 작업 개수
• 작업 i의 대기 시간 = 이전 처리한 모든 작업의 대기 시간의 합

작업을 번호 순서대로 처리하면 총 대기 시간의 합은 0 + 3 + (3+4) + (3+4+1) + ... + (3+4+1+8+2) = 52이다.
하지만, 처리시간이 짧은 순서대로 처리하면 합은 0 + 1 + (1+2) + (1+2+3) + ... + (1+2+3+4+6) = 36이다.

4. Activity Selection 문제

문제 : 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 각 회의 i의 시작시간 si와 끝나는 시간 fi가 주어져 있다. 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

• 회의가 종료와 동시에 다음 회의가 시작할 수 있으므로, fi에 맞춰 회의를 정렬한다. 끝나는 시간이 빠른 회의부터 선택해 최적해를 구한다

// S : {(s[i], f[i]) | 1 <= i <= n}
Algorithm GreedySchedule(S, n)
    solution = {1}
    last = 1
    for i=2 to n
        if (s[i] >= f[last])
            solution = solution ∪ {i}
            last = i
            
    return solution

5. Knapsack 문제

문제 : 용량이 M인 배낭이 있다. 이 배낭에 넣고자하는 물건이 n개 있다. 물건 i의 무게는 w[i]이고 이것을 배낭에 넣을 경후 p[i]의 이익을 얻는다. 배낭에 넣는 물건들의 총 무게의 합이 M을 넘지 않으면서 얻는 이익이 최대가 되도록 하라. 각 물건은 넣지 않을 수도, 일부만 넣을 수도, 전부 넣을 수도 있다.

이익의 합 : Σp[i]x[i]
무게의 합 : Σw[i]x[i]
후보 해 : x = {x[i] | 0 <= x[i] <= 1}

// p와 w는 무게 당 이득으로 내림차순 정렬
Algorithm GreedyKnapsack(p, w, M, n)
    x = [0] * n
    weight_left = M
    for i=1 to n
        if (w[i] <= weight_left)
            x[i] = 1
            weight_left -= w[i]
        else
            x[i] = weight_left/w[i]
    return x            

• x[i]를 0 또는 1로 제한할 경우, 그리디는 최적해를 보장하지 못하고 NP-Complete 문제가 된다.