[알고리즘] C++로 이해하는 그리디

참고 : https://www.geeksforgeeks.org/greedy-algorithms/

---

☑️ C++로 이해하는 그리디

📌 이론과 알고리즘은 다르다.

그리디, 부르트포스, 위상정렬 등 다양한 알고리즘 이론들이 존재한다. 이 방법들은 '제안된 이론'을 의미한다. 이론을 어떤 방식으로 구현하냐에 따라서 알고리즘이 갈린다. 예를 들어 '정렬'은 어떠한 기준대로 배치를 바꾸는 것을 의미한다. 정렬이란 이론을 실행하기 위해서 버블 정렬, 힙 정렬, 퀵 정렬 등 다양한 정렬 알고리즘들이 존재한다.

 

☑️ 그리디 알고리즘(Greedy)

프로그래밍 용어는 있는 단어에서 가져온 것들이 많다. 네트워크(Network)는 그물 'Net'와 'Work'의 합성어로 그물처럼 얽혀 연결되어 있는 것을 의미한다. 그리디 알고리즘의 그리디(Greedy)도 '탐욕스러운', '욕심 많은' 뜻을 가지고 있다. 이 단어들로 알고리즘의 성격을 표현할 수 있다.

 

그리디 알고리즘은 최적화 문제를 해결하는 방법 중 하나로, 매 선택 단계에서 현재 상황에서 최적의 선택을 한다. 그렇기 때문에 문제의 작은 조각들에서는 항상 최적해를 보장한다. 하지만 지역적으로 작은 최적해가 문제 전체의 최적해를 항상 보장하지 않는다.

 

1️⃣ 그리디 알고리즘은 문제의 최적해를 보장하는가?

그렇지 않다. 그리디 알고리즘은 현재 상황에서 가장 좋은 선택을 한다. 지역적(선택)으로 최적의 해를 도출하지만, 전체적인 최적해를 보장하지 않는다. 특정 조건에서만 보장할 뿐이다. 항상 문제의 최적해를 찾기 위해서는 DP를 사용하는게 좋다.

 

2️⃣ 그리디가 문제의 최적해를 보장하는 조건

아래의 조건이 보장되어야 한다.

• 탐욕 선택 속성 (Greedy Choice Property)
  • 각 단계에서 지역적인 최적의 선택이 전역의 최적해로 이어져야 한다.
  • 현재 선택이 이후의 선택에 영향을 줄 수 있지만, 이전 선택에는 영향을 주면 안된다.
• 최적 부분 구조 (Optimal Substructure)
  • 최적해가 부분 문제의 최적해들로 구성되어야 한다.
  • 전체 문제를 작은 부분 문제들로 나눌 수 있고 각 부분 문제의 최적해를 조합하여 전체 문제의 최적해를 나눌 수 있어야 한다.
• 선택의 독립 (Independence of Choices)
  • 이전에 한 선택이 이후 선택에 부정적인 영향을 미치지 않아야 한다.

 

3️⃣ 최적해를 보장하지 못하는 예시

📌 0-1 배낭 문제(0-1 Knapsack Problem)

각각 무게와 가치가 다른 여러 물건들이 있다. 배낭은 최대 용량이 정해져 있는데, 배낭에 담을 수 있는 최대 가치를 찾자. 각 물건은 통째로 넣거나(1), 넣지 않거나(0)만 가능하다.

 

배낭 용량 : 50kg

물건 이름	무게	가치	단위 무게
1	10	60	6
2	20	100	5
3	30	120	4

 

📌 그리디 접근 방법

1. 단위 무게당 가치가 높은 물건부터 진행한다. (단위 무게 : 가치/무게)
2. 1번 물건을 가방에 넣는다. ( 남은 가방 용량 : 40 )
3. 2번 물건을 가방에 넣는다. ( 남은 가방 용량 : 20 )
4. 3번 물건은 가방에 넣을 수 없다.

결과적으로 1번 물건과 2번 물건을 넣어서 가방의 가치는 160이 됐다. 실제 문제 최적해는 2번 물건과 3번 물건을 선택하는 것으로 가방의 가치를 220으로 만들 수 있다.

 

4️⃣ 그리디 알고리즘을 사용하는 이유

그리디 알고리즘은 모든 문제의 최적해를 보장하지 않지만, 그리디 알고리즘은 아래의 이유로 사용된다.

• 효율성과 속도
  • 매우 빠른 실행 시간을 가지고 있다.
    • 대부분 O(log n) 또는 그 이하의 시간을 가진다.
  • 입력 크기가 큰 문제에서도 효율적으로 동작한다.
• 구현의 단순성
  • 복잡한 상태 추적이나 재귀 호출이 필요 없는 경우가 많다.
• 특정 문제에서의 최적해 보장
  • 최적 부분 구조와 탐욕 선택 속성을 만족하는 문제에서는 최적해를 보장한다.

 

☑️ 그리디를 사용해서 풀 수 있는 문제

1️⃣ 거스름 돈

링크 : https://www.acmicpc.net/problem/5585

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    vector<int> coins = { 500, 100, 50, 10, 5, 1 };
    
    int i = 0;
    n = 1000 - n;
    while (n > 0)
    {
        if (n- coins[i] < 0)
            i++;
        else
        {
            n -= coins[i];
            ans++;
        }
    }

    cout << ans;

    return 0;
}

 

2️⃣ 설탕 배달

링크 : https://www.acmicpc.net/problem/2839

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main() {
	int n, ans = 0;
	vector<int> k = { 5, 3 };
	cin >> n;

	int i = 0;
	while (n > 0)
	{
		if (n % 5 == 0)
		{
			ans += (n / 5);
			break;
		}
		else
		{
			n -= 3;

			if (n < 0)
				ans = -1;
			else
				ans++;
		}
	}
	
	cout << ans << endl;

	return 0;
}

 

☑️ 관련 게시글

1️⃣ 최소 신장 트리

[알고리즘] C++로 이해하는 MST