[코딩테스트][C++]이론6. 그리디 알고리즘

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지를 선택하는 것이 전체의 선택지에서 최선의 선택지를 선택하는 것이라고 가정하는 알고리즘이다. 

수행과정

1. 최선의 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.

2. 적절성 검사 : 현재 선택한 해가 전체 문제에서 적절한지 검사

3. 해 검사 : 현재 상태에서 최선의 선택지가 전체 문제에서의 최선인지 검사

 

예시 문제1.

동전개수의 최솟값 구하기

 

문제에서 그리디하게 접근해보자면 가장 가격이 큰 동전부터 사용하면 동전개수를 최소로 사용할 수 있다. 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;
	vector<int> a(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int cnt = 0;
	for (int i = n - 1; i >= 0; i--) {
		cnt += k / a[i];
		k %= a[i];
	}

	cout << cnt << "\n";
}

 

문제 예시2

최솟값을 만드는 괄호배치 찾기 

최솟값을 만들려면 가능한 큰 수를 빼야하는데 이렇게 하려면 더할걸 모두 다 더하고 빼기를 할 수 있도록 괄호를 구성해줘야한다. 

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

vector<string> split(string input, char del);
int mySum(string a);
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int answer = 0;
	string ex;
	cin >> ex;
	vector<string> s = split(ex, '-');

	for (int i = 0; i < s.size(); i++) {
		int tmp = mySum(s[i]);
		if (i == 0) {				//젤 앞에꺼면 더하고
			answer += tmp;
		}
		else {					//아니면 빼주기 
			answer -= tmp;
		}
	}

	cout << answer << "\n";
}

vector<string> split(string input, char del) {
	vector<string> result;
	stringstream mystream(input);
	string splitdata;

	while (getline(mystream, splitdata, del)) {		//split
		result.push_back(splitdata);
	}
	return result;
}

int mySum(string a) {			//-하기 전 더하기
	int sum = 0;
	vector<string> tmp = split(a, '+');

	for (int i = 0; i < tmp.size(); i++) {
		sum += stoi(tmp[i]);
	}
	return sum;
}