[알고리즘] 탐욕(Greedy) 알고리즘 - 코딩밥상

탐욕(Greedy) 알고리즘이란?

 탐욕 알고리즘 또한 전에 봐왔던 알고리즘과 동일하게 최적화 문제의 답을 얻기 위해 사용됩니다. 즉 DP 또는 Greedy 알고리즘으로 풀 수 있는 문제들이 정해져 있다는 뜻입니다.

'탐욕'이라는 이름은 각 단계의 부분 문제를 풀 때 근시안적으로 최적해를 구한다고 해서 붙여졌습니다. 탐욕 알고리즘은 DP보다 효율적(대부분 연산 횟수가 DP보다 적음)이긴 하지만 DP처럼 반드시 최적해를 구해준다는 보장은 하지 못합니다. 최적해가 나오기를 기대할 수 밖에 없는것이죠.

 

 탐욕 알고리즘이 DP와 다른 점만 있는 것은 아닙니다. 탐욕 알고리즘으로 풀 수 있는 문제는 동적 계획법과 같이 대상 문제가 최적 부분 구조를 갖고 있어야 합니다.

탐욕(Greedy) 알고리즘은 다음과 같은 과정으로 동작합니다.

1. 해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 후 이를 부분해 집합(Solution Set)에 추가합니다.
2. 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한 것인지 확인합니다. 다시 말해, 문제의 제약 조건을 위반하지 않는지 검사합니다.
3. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지 확인합니다. 아직 전체 문제의 해가 완성되지 않았다면 처음부터 과정을 반복합니다.

위 과정을 통해 대표적인 그리디 문제인 '거스름돈 줄이기 문제'를 풀어보겠습니다.

예제) 거스름돈 줄이기 문제

 이 문제는 제목 그대로 거스름돈으로 주는 화폐의 양을 최소로 만드는 문제입니다. 예를들어 거스름돈으로 줘야 할 돈이 800원이라면, 100원짜리 8개 보다 500원짜리 1개와 100원짜리 3개로 돌려주는 것이 화폐의 양을 최소로 하는 것입니다.

1. 해 선택 : 현재 고를 수 있는 가장 큰 단위의 동전을 추가합니다.
2. 실행 가능성 검사 : 거스름돈이 목표 액수를 초과하는지 확인합니다. 초과한다면 마지막에 추가한 동전을 빼고 전 단계로 돌아가서 현재보다 한 단계 작은 단위의 동전을 추가합니다.
3. 해 검사 : 해를 구성하는 총액이 목표액과 일치해야합니다. 액수가 모자라면 처음 단계로 돌아가서 추가할 동전을 고릅니다.

이를 코드로 구현하면

int CountCoins(int Amount, int CoinUnit){
    int CoinCount = 0;
    int CurrentAmount = Amount;
    
    while(CurrentAmount >= CoinUnit){
        CoinCount++;
        CurrentAmount = CurrentAmount - CoinUnit;
    }
    
    return CoinCount;
}

void GetChange(int Price, int Pay, int CoinUnits[], int Change[], int Size){
    int ChangeAmount = Pay - Price;
    
    for(int i=0; i<Size; i++){
        Change[i] = CountCoins(ChangeAmount, CoinUnits[i]);
        ChangeAmount = ChangeAmount - (CoinUnits[i] * Change[i]);
    }
}

---

그리디(Greedy) 알고리즘을 활용한 최소 신장 트리 만들기

그래프 내 모든 정점을 최소 비용으로 연결하는 트리를 최소 신장 트리라고 배웠습니다. 여기서 가장 중요한 제약은 사이클이 형성되어서는 안된다는 점입니다. 이러한 최소 신장 트리를 만드는 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘 두 가지를 배웠었는데 그 중 크루스칼 알고리즘을 그리디(탐욕적인) 관점에서 다시 한번 살펴보겠습니다.

잠깐 크루스칼 알고리즘에 대해 복습하자면,

1. 그래프 내 모든 간선을 가중치의 오름차순으로 정렬하여 목록을 만듭니다.
2. 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가합니다. 단, 사이클이 형성되면 안됩니다.

이 과정에서 그리디 측면의 방법으로 처리되는 부분은 두 번째 단계입니다. 그리디 측면에서 '해 선택 - 실행 가능성 검사 - 해 검사'의 반복으로 최소 신장 트리가 완성되는 것입니다. 

 먼저 '1. 해 선택'은 가장 작은 가중치의 간선을 선택합니다. 정렬은 이미 끝났으므로 차례대로 선택하기만 하면 됩니다.

크루스칼 알고리즘에서 가장 중요한 것은 '2. 실행 가능성 검사'입니다. 선택한 간선이 신장 트리 내에 사이클을 형성한다면 이 간선을 버리고 다음 가중치의 간선을 골라야 합니다. 이는 분리 집합을 이용하는데, 간선을 추가 할 떄마다 간선 양 끝에 있는 정점들을 같은 집합에 추가했을 때 이 두 개의 정점이 이미 같은 집합에 소속되어 있다면 이 간선이 사이클을 형성한다고 판단합니다.

'3. 해 검사'는 모든 정점이 하나의 집합에 들어 있으면 해가 완성되었다고 판단할 수 있습니다.

---

그리디(Greedy) 알고리즘을 활용한 최단거리 구하기

여기까지 최소 신장 트리를 만드는 과정인 크루스칼 알고리즘을 그리디 측면에서 정리해 보았는데

이번엔 정점간의 이동의 최소 비용(최단 거리)을 구하는 데이크스트라 알고리즘을 그리디 측면에서 살펴보겠습니다.

데이크스트라 알고리즘을 복습해 정리해보면,

1. 각 정점에 경로의 길이를 저장하고 그 값을 무한대로 초기화합니다.
2. 시작 정점의 경로 길이를 0으로 초기화하고 최단 경로에 추가합니다.
3. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가합니다.(만약 이미 최단 경로에 있는 정점이라면 각 경로의 길이 값을 비교하여 더 적은 값을 저장합니다.)
4. 그래프 내의 모든 정점이 최단 경로에 소속될때까지 과정을 반복합니다.

이를 그리디 측면에서 보면 3번 단계가 그리디의 '해 선택'과 '실행 가능성 검사'를 맡고 4번 단계가 '해 검사'를 맡고 있습니다. 또한 이 최단 경로가 해 집합이고 각 정점이 부분 문제에 대한 해입니다.

이 과정을 천천히 실행해 보면 한 정점의 인접 정점들에 대한 정보만 이용하여 최단 경로를 구축해 나간다는 사실을 알 수 있습니다. 즉 지금 보는 데이크스트라 알고리즘도 근시안적인 접근법을 이용하여 문제를 해결하는 것입니다.