[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

반응형

 

그리디 알고리즘 (Greedy Algorithm)

눈앞의 이익만 좇는 선택을 반복하는 알고리즘이다. 그리디 알고리즘은 당장의 경우에는 최적의 경우일지라도, 결과는 대부분 최적이 아니다. 그렇지만 드물게 최적의 답을 보장해주는 경우가 있다. 

해가 만들어 질 때 까지 가장 좋아 보이는 선택을 하는 것을 반복한다.

 

그리디 알고리즘은 이미 앞에서 사용되었다. 바로, 최소 신장 트리를 구할 때 사용한 프림 알고리즘과 크루스칼 알고리즘이다. 또한, 프림 알고리즘과 크루스칼 알고리즘은 최적해가 보장되는 예들 중 하나이기도 하다.

 

그러나 이 둘이 특별한 경우이고 대부분의 경우에는 최적의 해를 보장하지 못한다. 아래와 같은 예시를 보자.

 

---

 

1. 이진 트리의 그리디 탐색

 

이진 트리에서 리프 노드를 만날 때 까지 방문한 노드의 값들을 더한 값이 최대인 값을 찾는 알고리즘을 생각해보자. 그리디 알고리즘으로 이를 찾게 된다면 어떤 경우에는 해가 맞을 수 있겠지만, 대부분의 경우에는 해가 맞지 않음을 알 수 있다. 아래 그림은 한 이진 트리를 예시로 그리디를 통해 답을 찾는 것을 표현했다.

 

척 봐도 그리디를 통해서 해를 구할 수 없음을 알 수 있다.

 

실제 답은 아래와 같이 모든 노드를 뒤져가면서 발견해야한다.

 

 

 

// 이진 트리는 자료구조 때 만든 연결리스트로 구현한 이진 트리임.
// 그리디를 적용한 탐색. 대부분의 경우 원하는 해가 아님!
int Greedy_Sum(Node* root) {
    Node* n = root;
    int sum = 0;
    
    while (n != NULL) {
        sum += n->data;
        
        // 그 순간에 더 큰 자식노드로 감.
        if (n->left.data > n->right.data) { 
            n = n->left;
        }
        else {
            n = n->right;
        }
    }
    
    return sum;
}

 

---

 

 

2. 보따리 문제

 

부피가 M인 보따리와 이 보따리에 넣으려 하는 n개의 물건이 있다. 물건 i의 부피를 \(w_i\)라고 하고, 이것을 보따리에 넣는다면 \(P_i\)의 가치를 가진다고 한다. 전체의 부피가 M을 넘지 않도록 하면서 가치가 최대가 되도록 물건을 넣어야한다.

 

그리디 알고리즘을 이용한다면, 가장 부피가 큰 물건 순서로 보따리에 넣을 것이다. 그러나 이는 최적해를 보장하지 못한다. 또한 이 문제는 NP-난해에 속하는 난제이기도 하다.

 

---

 

3. 동전 바꾸기

 

돈을 동전으로 바꿀 때 동전의 수를 최대한 줄이는 상황이다. 일반적인 경우에서는 그리디를 통해 최적의 답을 구할 수 있다. 하지만, 동전의 액면가가 바뀌게 된다면 그리디를 통해 최적해를 보장할 수 없다.

 

1300원은 500원 2개, 100원 3개로 총 5개가 된다. 그리디를 통해서 얻어낸 값이다. 실제로 최적의 해와 같다.

그런데, 동전에 400원이 추가가 된다면? 그리디의 경우에는 500원 2개 100원 3개의 경우가 나온다. 하지만, 실제로는 500원 1개 400원 2개로 총 3개의 동전이 생기게 되어 그리디가 최적의 해가 아니게 된다.

 

---

 

물론, 그리디를 통해 최적의 해가 보장되는 경우도 있다. 앞에서 언급한 프림 알고리즘과 크루스칼 알고리즘이 있다. 이 외에도 다익스트라 알고리즘도 그리디 알고리즘의 한 예이다.

 

[알고리즘] 최소 신장 트리(Minimum Spanning Tree)

[알고리즘] 최소 신장 트리(Minimum Spanning Tree)

 

[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90