그리디 알고리즘

• 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다

• 그리디 알고리즘의 문제 해결 절차

  • 1. 선택 절차
       거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
  • 2. 적절성 검사
       1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다.
       초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
  • 3. 해답 검사
       선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
       액수가 부족하면 1번 과정부터 다시 반복한다.

#11047

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

int main()
{
	int N, K;
	int A[10] = { 0 };
	int count = 0;
	cin >> N >> K;

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

	for (int i = N-1; i >= 0; i--)
	{
		while (K - A[i] >= 0) //A[i]의 동전이 (가방에) 들어간다면
		{
			count++;
			K = K - A[i];
		}
	}

	cout << count;
	return 0;
}

#1931

//원래 vector를 (시작시간, 종료시간)으로 받고 종료시간으로 sorting시키려고 myComp 함수를 만들었는데 오류가 나서 (종료시간, 시작시간)으로 바꿔서 받았다.
-> myComp 함수에서 a.second == b.second 일 때를 고려 안해줘서 오류가 난 것! 수정완료

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

////vector의 second 변수로 오름차순 정렬 하기 위함
bool myComp(const pair<int, int> &a, const pair<int, int> &b)
{
	if (a.second == b.second)
		return a.first < b.first;
	else
		return a.second < b.second;
}

int main()
{
	int N, temp1, temp2;
	int endTime = 0;
	int count = 0;
	vector<pair<int, int>> vec;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> temp1 >> temp2;
		vec.push_back(make_pair(temp2, temp1));
	}

	sort(vec.begin(), vec.end());

	for (int i = 0; i < N; i++)
	{
		if (vec[i].second >= endTime) //다음 회의의 시작하는 시간이 끝나는 시간보다 뒤라면
		{
			endTime = vec[i].first; //endTime을 다음 회의의 끝나는 시간으로 저장
			count++; //실행하는 회의의 개수 +1
		}
	}

	cout << count;
	return 0;
}

#11399

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

int main()
{
	int N, sum = 0;
	int p[1000] = { 0 };

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> p[i];
	}
	
	sort(p, p + N); //시간을 오름차순으로 정렬

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			sum += p[j];
		}
	}

	cout << sum;

	return 0;
}

#1541

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

int main()
{
	//stoi 사용
	// - 가 나오면 뒤의 수들은 - 처리 해준다
	string str;
	string num;
	int result = 0;
	bool b_minus = false;
	cin >> str;

	for (int i = 0; i <= str.size(); i++)
	{
		if (str[i] == '-' || str[i] == '+' || i == str.size())
		{
			if (b_minus)
			{
				result -= stoi(num);
				num = ""; //string 초기화
			}
			else
			{
				result += stoi(num);
				num = ""; //string 초기화
			}
		}
		else
		{
			num += str[i];
		}

		if (str[i] == '-')
			b_minus = true;
	}

	cout << result;
	return 0;
}

#13305

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

int arr[100000] = { 0 }; //도로의 길이
int cost[100000] = { 0 }; //리터당 가격

int main()
{
	int N;
	long long sum = 0;
	long long thisCost = 0;
	cin >> N;

	for (int i = 1; i <= N-1; i++)
	{
		//도로의 길이 입력받기
		cin >> arr[i];
	}

	for (int i = 0; i < N; i++)
	{
		//리터당 가격 입력받기
		cin >> cost[i];
	}

	thisCost = cost[0];
	sum = thisCost * arr[1]; //1번도시에서 2번도시로 이동

	for (int i = 1; i < N; i++)
	{
		//만약 앞의 도시에서 기름 가격이 뒤의 도시보다 싸다면
		if (thisCost < cost[i])
		{
			sum += thisCost * arr[i + 1];
		}
		else
		{
			//더 비싸다면
			thisCost = cost[i];
			sum += thisCost * arr[i + 1];
		}
	}

	cout << sum;

	return 0;
}