[ 탐욕법 ] 그리디 알고리즘의 사용 조건 및 정당성 증명, 예시 문제 풀이

🔎 그리디 알고리즘(탐욕법)이란?

 

전체 문제를 여러 조각으로 분할하고, 각 단계별 최적해를 결합해 최종 최적 해를 만들어가는 알고리즘인데,

쪼갠 작은 단계마다 욕심쟁이처럼, 미래는 보지 않고 그저 눈 앞에 보이는 가장 좋은 방법만을 늘 선택합니다.

 

단순히, 현재 내릴 수 있는 최선의 선택에만 집중하는 알고리즘입니다.

 

 

 

 

 

---

 

 

 

 

 

 

📖 그리디 알고리즘 문제 출제 경향

 

단순히 각 단계에서 가장 최적의 값을 고르는 그리디 알고리즘이 늘 최적해를 구해내진 못합니다.

근사한 해만을 구할 수 있는 경우가 대부분입니다.

 

그리디 알고리즘은 계산 속도가 빠르기에,

시간 및 공간적 제약으로 최적해를 구하지 못해서 최적해 대신 근사해를 구해야 할 때 사용됩니다. 

 

그러나, 이 경우는 주로 코딩테스트에서 출제되진 않고, 

" 탐욕법을 사용해도 늘 최적해가 구해지는 문제 " 가 출제됩니다.

 

 

 

 

 

---

 

 

 

 

 

📚 탐욕법 사용의 정당성 증명

 

 

그래서 탐욕법을 사용해도 항상 최적해가 구해지는 문제인지 아닌지, 정당성을 증명해야 하는데

 

1. 탐욕 선택 속성
: 쪼갠 문제들이 서로 영향을 주지 않고, 전체 정답이 안전하게 보장되는 경우

2. 최적 부분 구조

: 쪼갠 문제의 해답들이 모여, 전체의 정답을 구성하는 경우

 

 

위의 두 가지 조건을 만족하면, 그리디 알고리즘을 적용해서 최적해를 구할 수 있습니다.

그리디 알고리즘 사용 조건

 

 

---

 

 

 

최적해 계산을 위한 탐욕법 적용의 두 가지 조건을 예시를 들어 좀 더  자세하게 보겠습니다.

1. 탐욕 선택 속성 ( Greedy Choice Property ) 

: 탐욕법으로 구한 부분 문제의 최적 해가 다음 문제에 영향주지 않고,

안전하게 전체 문제의 최종 최적해를 보장함

 

탐욕적으로 당장 최적의 값을 선택한다 해도, 안전하게 문제의 최적해가 보장될 때 !

욕심쟁이처럼 좋은 것을 선택해도, 전체 결과에 손해가 없으며, 다음 부분 문제에 영향을 주지 않는 경우 탐욕 선택 속성 조건을 만족하는 것입니다.

 

2. 최적 부분 구조 ( Optimal Substructure )

: 전체 문제의 해가 부분 문제들의 최적해로 구성됨

 

 탐욕법은 큰 문제를 여러 개로 작게 분할한다고 했었습니다. 이렇게 쪼갠 부분 문제의 최적해가 전체 문제의 최적해로 확장되는 경우를 말합니다.

 전체 문제를 작게 쪼개, 각 문제들의 그리디한 최적해를 모아 결합해서 전체 문제의 최적해를 알 수 있다면 이 최적 부분 구조 조건을 만족하는 것입니다.

그리디 알고리즘 사용 조건 상세

 

 

 

 

 

 

 

---

 

 

 

 

 

📝 예시 문제

 

위에서 본 정당성 증명 과정을 통해,

그리디 알고리즘을 적용해도 최적해가 나오는지를 증명하고 풀어야한다.

 

 

백준 11047번 동전 0 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

문제 개요

 

 

그리디 알고리즘의 사용 조건 2가지를 만족하는 지 확인해보자. 

 

1. 탐욕 선택 속성 (Greedy Choice Property)

- 부분 문제의 최적해가 다음 문제에 영향을 주지 않고, 안전하게 최적해를 보장한다 !

탐욕적인 방법으로 전체 동전 수를 줄이기 위해, 단순히 가장 큰 값의 동전을 사용한다해도, 다음 단계에 영향을 주지 않는다 !

최종적으로 구해지는 해 (최소 동전 개수) 에도 손해를 끼치지 않는다.

 

예를 들어, 10원, 50원짜리 동전으로 100원을 표현해야한다.

그렇다면, 50원짜리 2개가 10원짜리 10개보다 적은 수의 동전을 사용한다.

가능한 큰 동전을 써서 최종 동전 사용 개수를 줄이려는 단순하고 탐욕스러운 방식이 손해 없이 최종 정답을 보장한다 !

 

2. 최적 부분 구조 ( Optimal Substructure )

- 부분 문제의 최적해가 전체 문제의 최적해로 확장된다 !

탐욕적으로 각 단계에서 가능한 제일 큰 값의 동전을 사용하는 것이, 문제가 요구하는 최소 개수의 동전을 사용하는 것이다. 즉, 각 단계마다의 그리디한 최적해가 전체문제의 최적의 해로 확장된다.

 

예를 들어, 800원을 500원, 100원, 50원짜리 동전으로 나타내려한다.

800  = 100*8 = 500*1 + 100*3

이런 식으로, 100원짜리 8개 대신, 500원 1개 쓰고, 100원을 3개 쓰면 동전 개수가 줄어든다.

즉, 가능한 가장 큰 금액의 동전을 그때그때 쓰는 것이, 최종적으로 동전 개수를 줄이는 문제의 정답으로 확장된다 !

 

 

따라서 이 문제에 그리디 알고리즘을 적용해,

매 순간마다 가능한 가장 큰 동전을 사용하며 점차 남은 돈을 줄여나가면,

최소의 동전 개수를 구할 수 있다 :)

 

 

(정답 코드)

#include <iostream>
#include <vector>

using namespace std;


// 그리디 알고리즘 활용 : 늘 가능한 가장 큰 동전 사용하기 !

int cntCoins(vector<int>& coins, int k) {
    int cnt = 0;
    
   for(int i=coins.size()-1 ; i>=0; i--) { // 오름차순으로 정렬된 동전들. 금액 큰 순서부터 반복문 !
       if(coins[i]<=k) { // 현재 남은 금액(k)보다 작은 동전들 중 가장 큰 동전 coins[i] 
           k-=coins[i]; // 남은 금액에서 현재 사용한 동전만큼 빼기
           cnt ++ ; // 사용한 동전 개수 +1
           i++; // 현재 동전부터 다음 반복 다시 시작하려고 !
       }
   }
    return cnt;
}

int main()
{
    // 속도 향상 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // 선언
    int n, k, temp;
    vector <int> coins; // n개 종류의 동전들 담을 벡터
    
    // 입력
    cin >> n >> k;
    while(n--) {
        cin >> temp;
        coins.push_back(temp);
    }
    
    // 연산 및 출력
    cout << cntCoins(coins, k);
    
    return 0;
}