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

1. 그리디 알고리즘

매 순간마다 눈 앞에 보이는 최선의 상황을 선택하며 최종 답으로 도달하는 방법이다.

시간 복잡도 : 상황에 따라 다양하지만, 보통 O(N), O(NlogN)

😈 gif script)

지나가는 전체 노드의 합이 최대가 되도록 하고 싶은 경우라고 가정 했을 때, 아래 gif에서는 눈 앞의 큰 노드 값만을 선택하며 최종적으로 9에 다다른다.

→ 결론적으로는 오답이다. 마지막 노드가 99가 되는 경로로 가야 전체 노드의 합이 최대가 되는 경우이기 때문이다.

요는, 그리디 알고리즘을 이용하는 것은 문제에 따라 더 빠르거나 느릴 수 있기에(혹은 답 자체가 틀릴 수도 있다.) 시행 전에 분석이 필요하다는 것이다.

👿 조건 및 수행 과정

1. 각 단계에서의 최선의 선택이 이후의 선택들에 영향을 미치지 않는 경우에 사용할 수 있다.

ex ) 1260원을 거스름돈(동전)으로 줘야되는 경우
→ 1) 500원 2개를 사용하고, 2) 260원이 남았을 때, 500원을 2개 선택했던 것은 260원에서 최적의 해를 결정하는데 영향을 미치지 않는다. 따라서 큰 값의 동전부터 처리하는 것은 그리디 알고리즘이 적용된 것으로 볼 수 있다.

2. 문제의 최적해가 부분 문제의 최적해로 구성되는 경우에 그리디 알고리즘을 사용할 수 있다.

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지를 검사한다.

ex) 백준 11047번

큰 동전부터 조사하고, 동시에 알맞은 연산을 통해 최소 동전 개수를 구할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int N, K, cnt=0;
    cin >> N >> K;
    
    vector<int> coin(N);
    
    for (int i = 0; i < N; i++) {
        cin >> coin[i];
    }
    
    for (int i = N-1; i >=0; i--) {
    
    // 전체 값보다 작은 동전 중, 가장 큰 동전이 보이는 경우
        if (K >= coin[i]) {
            cnt += K / coin[i];
            
    // 다음 사이클을 돌 때 나머지 값을 사용하기 위해서
            K %= coin[i];
        }
    }
    cout << cnt;

}

---

현재 상태에서 최선의 경우를 선택하여 해결할 수 있다. 간단한 문제의 경우, 문제를 직관적으로만 생각해도 코드가 자연스럽게 그리디 알고리즘으로 이어질 수 있겠지만 복잡해지면, 조건과 수행 과정을 꼼꼼하게 따져볼 필요가 있을 것이다.