[알고리즘] 그리디 알고리즘

1. 전형적인 그리디 알고리즘의 구조

- 눈앞의 이익만 우선 추구하는 알고리즘을 총칭해서 그리디 알고리즘이라 함.

- 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우도 있음.

- 그리디 알고리즘은 최적화 문제를 대상으로 함.

- 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼음.

do {
    가장 좋아 보이는 선택을 함;
} until ( 해 구성 완료 )

- 그리디 알고리즘은 하나의 온전한 해가 만들어질 때까지 눈앞에 가장 좋아보이는 선택을 반복함.

- 간선이 하나도 없는 집합에서 시작해서 간선을 하나씩 더해가면서 n-1개의 간선이 될 때까지 집합을 키워나감.

- 각 단계에서 어떤 간선을 택할지 결정하는 로직이 있어야 함.

- 이 로직이 눈앞의 이익만 추구하면 그리디 알고리즘 계열에 속하게 됨.

- 간선을 하나 더할 때마다 해당 간선이 기존에 선택된 간선들과 사이클을 이루지는 않는지 확인해야 함.

 

Greedy(C) // 원소들의 총 집합
{
    S <- Ø;
    while (C ≠ Ø and S는 아직 온전한 해가 아님) {
        ①x <- C에서 원소 하나 선택;
           집합 C에서 x를 제거함;
        ②if (S에 x를 더해도 됨 ) then S <- S∪{x};
    }
    if ( S가 온전한 해 ) then return S;
        else return "해X";
}

- ①에서 원소를 선택하는 기준이 눈앞의 이익을 우선하면 그리디 알고리즘 계열.

 

2. 그리디 알고리즘으로 최적해가 보장되지 않는 예

 이진 트리의 최적합 경로 찾기

- 모든 노드를 보기 전에는 최적해를 보장할 수 없음.

- 그러므로 루트로부터 DFS와 같은 백트래킹 탐색을 할 수밖에 없고, 수행 시간의 상한은 트리의 총 노드 수에 비례하게 됨.

- DFS나 BFS와 같은 방식으로 모든 노드를 다 확인해보기 전에는 최적해를 보장할 수 없음.

 

보따리 문제

- 부피가  M인 보따리와 이 보따리에 넣으려 하는 n개의 물건이 있음.

- 물건 i의 부피는 W이고, 이것을 보따리에 넣을 경우 p의 가치가 있음.

- 물건들의 전체 부피 합이 M을 넘지 않도록 하면서 가치가 최대가 되도록 함.

- 보따리 문제에서 물건을 자를 수 있다면 이 같은 방식으로 최적해를 보장할 수 있음. ( 이 유형의 문제를 자를 수 있는 보따리 문제라 함 )

 

동전 바꾸기

- 최소한의 동전으로 금액을 맞추는 문제.

- 가지고 있는 동전 종류에서 큰 단위가 작은 단위의 배수 형태라면 그리디 알고리즘으로 문제가 해결됨.

- 하지만 배수가 아니라면 최적해가 보장되지 않음.

 

3. 그리디 알고리즘으로 최적해가 보장되는 예

 최소 신장 트리

- 최소 신장 트리를 위한 프림 알고리즘, 크루스칼 알고리즘은 그리디 알고리즘으로 최적해가 보장됨.

- 어떤 시점이든지 그 시전에서 가장 적은 값을 가지고 연결되는 정점을 택하게 됨.

 

회의실 배정 문제

- 종료 시간이 빠른 순서로 정렬 후 회의들을 포함시킬지 체크함.

- 회의 시간이 짧은 것을 우선적으로 고려하거나, 시작시간이 빠른 회의부터 고려한다면 최적해를  보장할 수 없음.

 

4. 매트로이드 : 그리디 알고리즘으로 최적해가 보장되는 공간 구조

 매트로이드

- 독립성이라는 성질을 만족하는 수학적 공간.

- 어떤 문제의 공간이 매트로이드를 이루면 그리디 알고리즘이 존재함.

 

어떤 유한 집합 S의 부분 집합들의 집합인 I (즉, I ⊆ 2^s)가 다음의 성질을 만족하면 매트로이드라 함.
① A ∈ I이고 B ⊆ A이면 B ∈ I임.
② A,B ∈ I 이고 |A| < |B| 이면, A ∪ {x} ∈ I인 x ∈ B-A가 존재함.

- ① 집합 A가 I에 속하면 A의 모든 부분 집합들 또한 I에 속함.

- ② 크기가 다른 두 집합 A, B(|A| < |B|)가 I에 속하면, B의 원소이면서 A의 원소가 아닌 것 중에 A에 더해서 I에 속하게 하는 원소가 존재함.

 

매트로이드의 확장과 포화

매트로이드 I ⊆ 2^s와 A∈I에서 A에 속하지 않는 어떤 원소 x ∈ S에 대하여 A ∪ {x} ∈ I이면 x가 A를 확장한다고 함. A가 더 이상 확장되지 않으면 A를 포화 집합이라 함.

 

매트로이드 구조이면 그리디 알고리즘으로 최적해 보장

- 매트로이드 I의 원집합 S의 원소들이 가중치를 가지면 이를 가중치 매트로이드라 함.

- 매트로이드에서 가중치 최적화 문제는 항상 최적해를 찾을 수 있음.

- 그리디 알고리즘으로 풀려는 문제가 매트로이드 구조를 가니면 최적해를 보장하게 됨.

 

Greedy(I,w[])
{
    A = Ø;
    S의 원소들을 w의 가중치 크기로 내림차순 정렬함;
    for each x ∈ S (가중치 내림차 순)
        if ( A ∪ {x} ∈ I ) then A <- A ∪ {x};
    return A;
}