[C++] 그리디(Greedy)

그리디(Greedy)

각 단계에서 최선의 선택을 하는 알고리즘으로 탐욕적 기법이라고도 부른다.

• Greedy Choice Property (탐욕 선택 속성)
  • 국소 최적 선택이 전체 최적 해로 이어진다.
  • 현재 단계에서 가장 좋아 보이는 선택이 이후에도 전체적으로 최적인 결과로 이어진다는 속성이다.
• Optimal Substructure (최적 부분 구조)
  • 문제를 더 작은 문제로 나눌 수 있고, 그 작은 문제의 최적해들을 조합해서 전체 최적해를 만들 수 있어야 한다.
• Exchange Argument (교환 논법)
  • 임의의 최적해를 그리디 해와 다르게 만들 수 있다면, 이를 점진적으로 바꿔서 그리디 해처럼 만들 수 있고 성능이 떨어지지 않는다.

 

문제

 

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

1931번: 회의실배정

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

int main()
{
	int n;
	cin >> n;

	vector<pair<int, int>> v(n); // 끝나는 시간, 시작 시간
	for (int i = 0; i < n; i++)
		cin >> v[i].second >> v[i].first;
	sort(v.begin(), v.end());

	int ans = 1, next = v[0].first;
	for (int i = 1; i < n; i++)
		if (next <= v[i].second) {
			next = v[i].first;
			ans++;
		}
	cout << ans;
}

 

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

2457번: 공주님의 정원

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

struct Flower
{
	int startDay;
	int endDay;
};

// 정렬 편의를 위해 월일을 일(365)로 변경
int MonthEndDay[12]{ 31,28,31,30,31,30,31,31,30,31,30,31 };
int ChangeMonthToDay(int month, int day)
{
	int totalday = 0;
	for (int i = 0; i < month - 1; ++i)
		totalday += MonthEndDay[i];
	return totalday + day;
}

int main()
{
	int N;
	cin >> N;

	vector<Flower> v(N);
	for (int i = 0; i < N; ++i) {
		int month, day;
		cin >> month >> day;
		v[i].startDay = ChangeMonthToDay(month, day);
		cin >> month >> day;
		v[i].endDay = ChangeMonthToDay(month, day);
	}

	sort(v.begin(), v.end(), [](Flower a, Flower b) { return a.startDay < b.startDay; });

	int ans = 0;
	int day31 = ChangeMonthToDay(3, 1), day1130 = ChangeMonthToDay(11, 30);
	for (int i = -1, startDay = day31, endDay = 0; i < N && startDay <= day1130;) {
		bool flag = false;
		i++;

		for (int j = i; j < N; j++) {
			if (startDay < v[j].startDay)
				break;

			if (endDay < v[j].endDay) {
				flag = true;
				i = j;
				endDay = v[j].endDay;
			}
		}

		if (flag) {
			ans++;
			startDay = endDay;
		}
		else {
			cout << 0;
			return 0;
		}
	}
	cout << ans;
}

 

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

2217번: 로프

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

int main()
{
	int n;
	cin >> n;

	vector<int> v(n);
	for (int i = 0; i < n; ++i)
		cin >> v[i];
	sort(v.rbegin(), v.rend());

	int ans = 0;
	for (int i = 1; i <= n; ++i)
		ans = max(ans, v[i - 1] * i);
	cout << ans;
}

 

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

1422번: 숫자의 신

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

int main(void)
{
	int K, N;
	cin >> K >> N;

	int len = 0;
	vector<string> v(K);
	for (int i = 0; i < K; ++i) {
		cin >> v[i];
		len = max(len, (int)v[i].length());
	}

	sort(v.begin(), v.end(), [](const string& a, const string& b) {
		return a + b > b + a;
		});

	for (int i = 0, j = N - K; i < K; ++i) {
		while (len == (int)v[i].length() && j-- > 0)
			cout << v[i];
		cout << v[i];
	}
}

 

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

13305번: 주유소

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

int main()
{
	int N;
	cin >> N;

	vector<int> a(N - 1), b(N);
	for (int i = 0; i < N - 1; ++i)
		cin >> a[i];
	for (int i = 0; i < N; ++i)
		cin >> b[i];

	long long ans = 0;
	for (int i = 0, tmp = b[0]; i < N - 1; ++i) {
		ans += (long long)tmp * a[i];
		tmp = min(tmp, b[i + 1]);
	}
	cout << ans;
}

 

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

1202번: 보석 도둑

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

int main()
{
	int N, K;
	cin >> N >> K;

	vector<pair<int, int>> gem(N);
	for (int i = 0; i < N; ++i)
		cin >> gem[i].first >> gem[i].second;
	sort(gem.begin(), gem.end());

	vector<int> bag(K);
	for (int i = 0; i < K; ++i)
		cin >> bag[i];
	sort(bag.begin(), bag.end());

	long long ans = 0;
	priority_queue<int> pq;
	for (int i = 0, j = 0; i < K; ++i) {
		while (j < N && gem[j].first <= bag[i]) {
			pq.push(gem[j++].second);
		}

		if (!pq.empty()) {
			ans += pq.top();
			pq.pop();
		}
	}
	cout << ans;
}

 

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

1826번: 연료 채우기

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

int main(void)
{
	int n;
	cin >> n;

	vector<pair<int, int>> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end());

	int home, remain;
	cin >> home >> remain;

	int ans = 0, index = 0;
	priority_queue<int> pq;
	while (remain < home) {
		while (index < n && v[index].first <= remain)
			pq.push(v[index++].second);

		if (pq.empty())
			break;

		ans++;
		remain += pq.top();
		pq.pop();
	}

	if (remain < home)
		cout << -1;
	else
		cout << ans;
}

 

https://leetcode.com/problems/gas-station/description/

LeetCode - The World's Leading Online Programming Learning Platform

#include <vector>
using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        long sum = 0;
        for (int i = 0; i < gas.size(); ++i)
            sum += gas[i] - cost[i];
        if (sum < 0)
            return -1;

        int index = 0;
        sum = 0;
        for (int i = 0; i < gas.size(); ++i) {
            sum += gas[i] - cost[i];
            if (sum < 0) {
                sum = 0;
                index = i + 1;
            }
        }
        return index;
    }
};