Greedy(그리디) 알고리즘

Subin·2024년 10월 9일

Algorithm

목록 보기

44/69

Greedy = 탐욕적인
-> 눈 앞의 가장 큰 이익을 추구하는 기법

탐욕 알고리즘은, 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최정적인 해답에 도달한다.

Greedy 알고리즘은 탐욕적인 선택 전략을 사용하는 문제 해결 기법이다. 즉, 문제를 해결하는 과정에서 현재 상태에서 가장 최적이라고 판단되는 선택을 반복해서 수행함으로써 전체 문제를 해결하려는 방식이다. Greedy 알고리즘은 일반적으로 매번 선택할 때 그 순간에 가장 좋은 방법을 고르고, 그러한 선택들이 쌓여 문제를 해결하는 방식이다.

Greedy 알고리즘의 작동 방식

현재 상황에서 가장 최적의 선택을 한다.
한 번 선택한 것은 다시 되돌릴 수 없다(비가역적).
각 단계에서 최적의 선택을 반복하여, 전체적으로도 최적의 해를 구하려고 한다.

이 알고리즘은 문제를 단계별로 나누고 각 단계에서의 최적 선택이 결국 전체 문제 해결에 도움이 된다고 가정한다. 그러나 항상 전역 최적해를 보장하는 것은 아니기 때문에, 특정 문제에서는 Greedy 알고리즘이 잘 작동하고, 다른 문제에서는 그렇지 않을 수 있다.

Greedy 알고리즘의 기본 특성

탐욕적 선택 속성 (Greedy Choice Property)
- 각 단계에서의 선택이 전체 최적 해에 영향을 미치지 않는 경우.
- 즉, 각 단계에서 지역 최적해(local optimum)를 고르면서, 그 선택이 나중에 전역 최적해(global optimum)를 형성한다.
최적 부분 구조 (Optimal Substructure)
- 문제의 부분 문제들이 각각 최적해를 가지고, 이들을 결합해서 전체 문제의 최적해를 구할 수 있는 경우.
- 쉽게 말해, 부분 문제들의 최적해가 전체 문제의 최적해로 이어져야 한다는 조건이다.

Greedy 알고리즘의 장점

속도가 빠름: 매 순간 최적의 해를 선택하므로, 여러 가지 경우를 모두 탐색할 필요 없이 빠르게 답을 구할 수 있다. (일반적으로 시간 복잡도는 (O(n)) 또는 (O(n log n)))
구현이 단순: 알고리즘이 직관적이고 복잡하지 않으며, 다른 복잡한 알고리즘에 비해 구현이 쉽다.

Greedy 알고리즘의 단점

전역 최적해를 보장하지 않음: 모든 문제에 적용 가능한 것은 아니다. Greedy 알고리즘으로 얻은 해답이 항상 전역 최적해와 일치하지 않을 수 있다. 문제에 따라 Greedy 알고리즘이 제공하는 해답은 최적해가 아닐 가능성이 크다.

Greedy 알고리즘이 잘 적용되는 문제 유형

최소 신장 트리 (Minimum Spanning Tree, MST)
- 크루스칼 알고리즘 (Kruskal's Algorithm), 프림 알고리즘 (Prim's Algorithm)에서 사용.
- 간선 가중치의 합이 최소가 되는 신장 트리를 만드는 문제.
최단 경로 문제 (Shortest Path Problem)
- 다익스트라 알고리즘 (Dijkstra's Algorithm)은 Greedy 알고리즘을 기반으로 합니다.
- 시작점에서 다른 모든 정점으로 가는 최단 경로를 구하는 문제.
활동 선택 문제 (Activity Selection Problem)
- 여러 활동 중에서 서로 겹치지 않도록 최대한 많은 활동을 선택하는 문제.
동전 거스름돈 문제
- 주어진 동전으로 최소한의 개수로 거스름돈을 주는 문제. 단, 동전의 액면가가 특정 조건을 만족해야 한다.

Greedy 알고리즘의 예시

1. 동전 거스름돈 문제 (Coin Change Problem)

문제: 100원의 거스름돈을 주기 위해 1원, 5원, 10원, 50원 동전이 있다고 가정하고, 최소한의 동전 개수로 거스름돈을 주는 방법을 구하시오.

Greedy 알고리즘의 선택 전략:

현재 남은 거스름돈 중에서 가장 큰 동전 단위를 선택하여 최대한 거스름돈을 줄이는 방식.

#include <iostream>
#include <vector>

using namespace std;

int coinChange(vector<int>& coins, int amount) {
    int count = 0;
    
    for (int i = coins.size() - 1; i >= 0; i--) {
        if (amount >= coins[i]) {
            count += amount / coins[i];  // 현재 동전으로 몇 개를 쓸 수 있는지 계산
            amount %= coins[i];  // 남은 거스름돈
        }
    }
    
    return count;
}

int main() {
    vector<int> coins = {1, 5, 10, 50}; // 동전 종류
    int amount = 100;  // 거스름돈
    
    int result = coinChange(coins, amount);
    cout << "최소 동전 개수: " << result << endl;
    return 0;
}

2. 활동 선택 문제 (Activity Selection Problem)

문제: 주어진 활동들의 시작 시간과 종료 시간이 주어졌을 때, 서로 겹치지 않게 최대한 많은 활동을 선택하는 방법을 구하시오.

Greedy 알고리즘 선택 전략:

종료 시간이 가장 빠른 활동을 먼저 선택하는 방식.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int activitySelection(vector<pair<int, int>>& activities) {
    sort(activities.begin(), activities.end(), [](pair<int, int>& a, pair<int, int>& b) {
        return a.second < b.second;  // 종료 시간을 기준으로 정렬
    });
    
    int count = 1;
    int lastEnd = activities[0].second;  // 첫 번째 활동의 종료 시간
    
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].first >= lastEnd) {  // 다음 활동이 이전 활동과 겹치지 않으면
            count++;
            lastEnd = activities[i].second;  // 종료 시간 갱신
        }
    }
    
    return count;
}

int main() {
    vector<pair<int, int>> activities = {{1, 3}, {2, 5}, {3, 9}, {6, 8}, {5, 7}};
    
    int result = activitySelection(activities);
    cout << "선택한 활동 개수: " << result << endl;
    return 0;
}

Greedy 알고리즘 적용 가능성 판단

Greedy 알고리즘이 잘 동작하려면, 문제 자체가 Greedy 알고리즘으로 해결 가능해야 한다. 즉, 각 단계에서 탐욕적인 선택이 최종적으로 전체 최적해로 이어져야 한다. 이를 확인하는 방법은 탐욕적 선택 속성과 최적 부분 구조가 성립하는지 확인하는 것이다.

함께 보면 좋을 블로그
https://sectumsempra.tistory.com/88