언제나 처음처럼

[문제 링크]

간단한 그리디 알고리즘 문제였다.

인출하는데 걸리는 시간이 짧은 사람부터 먼저 인출하는 것이 항상 최적해를 보장하기 때문에, 입력받은 배열을 오름차순 정렬한 후 인출 시간이 짧은 사람부터 차례대로 계산해주면 원하는 결과를 얻을 수 있다.

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

void QuickSort(vector<int>& data, int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;

	while (i <= j)
	{
		while (i <= end && data[i] <= data[pivot])
			i++;

		while (j > start && data[j] >= data[pivot])
			j--;

		if (i > j)
		{
			int temp = data[pivot];
			data[pivot] = data[j];
			data[j] = temp;
		}

		else
		{
			int temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}

	QuickSort(data, start, j - 1);
	QuickSort(data, j + 1, end);
}

int Greedy(vector<int>& wait, int N)
{
	QuickSort(wait, 0, N-1);

	int time = 0, res = 0;

	for (int i = 0; i < N; i++)
	{
		time = (time + wait[i]);
		res += time;
	}

	return res;
}

int main(void)
{
	int N;
	cin >> N;
	
	vector<int> wait;
	for (int i = 0; i < N; i++)
	{
		int P;
		cin >> P;
		wait.push_back(P);
	}

	cout << Greedy(wait, N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day

[문제 링크]

간단한 그리디 알고리즘 문제였다.

항상 길이가 가장 짧은 두 문자열을 합치는 것이 최적해를 보장하기 때문에, 오름차순 정렬을 통해 길이가 가장 짧은 두 문자열을 합치도록 구현하였다.

삽입, 삭제 연산이 빈번할 때 유리한 list 컨테이너를 사용하였다. 두 문자열을 합칠 때마다 새로운 원소가 추가되기 때문에 오름차순 정렬을 수행해줬다.

또한 원소를 삽입할 때 자동으로 정렬되어 삽입되는 set 컨테이너를 사용해서 구현해보았는데, 원소 검색에 효율적인 set 컨테이너는 삽입 삭제 연산에 시간이 오래 걸린다는 단점이 있어 시간초과가 날수도 있겠다 생각했지만 통과되었다.

// 추가: 알고리즘 문제해결 전략에서는 priority_queue 를 사용하여 구현하였다. 우선순위큐는 원소를 자동으로 정렬해줄뿐더러 새 원소를 추가하는 작업을 log시간에 할 수 있기 때문에 가장 효율적이다.

<list 사용>

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

list<int> str;

int Greedy(int n)
{
	if (n == 1)
		return str.front();

	int result = 0;
	while (--n)
	{
		str.sort();

		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += str.front();
			str.pop_front();
		}
		result += join;
		str.push_back(join);
	}

	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.push_back(len);
		}

		cout << Greedy(n) << endl;
		str.clear();
	}

	return 0;
}

<multiset 사용>

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

multiset<int> str;

int Greedy(int n)
{
	if (n == 1)
		return *str.begin();

	int result = 0;
	while (--n)
	{
		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += *str.begin();
			str.erase(str.begin());
		}
		result += join;
		str.insert(join);
	}

	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.insert(len);
		}

		cout << Greedy(n) << endl;
		str.clear();
	}

	return 0;
}

<priority_queue 사용>

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


priority_queue<int, vector<int>, greater<int>> str;

int Greedy(int n)
{
	int result = 0;

	if (n == 1)
	{
		result = str.top();
		str.pop();
		return result;
	}

	while (--n)
	{
		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += str.top();
			str.pop();
		}
		result += join;
		str.push(join);
	}

	str.pop();
	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.push(len);
		}

		cout << Greedy(n) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 109 day

[문제 링크]

먹는데 가장 오래걸리는 도시락을 먼저 데우고 먹기 시작해야 가장 빨리 점심시간을 마칠 수 있다.

따라서, 먹는데 걸리는 시간을 기준으로 내림차순 정렬한 다음 오래 걸리는 도시락 순으로 데우도록 구현하였다.

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

vector<pair<int, int>> lunchBox;

int Greedy(int N)
{
	// 먹는데 오래걸리는 순으로 정렬
	sort(lunchBox.begin(), lunchBox.end(), greater<pair<int, int>>());

	int longest = 0, time = 0;

	for (int i = 0; i < N; i++)
	{
		if (longest < lunchBox[i].first + lunchBox[i].second)
		{
			longest = lunchBox[i].first;
			time += lunchBox[i].second;
		}
		else
		{
			longest -= lunchBox[i].second;
			time += lunchBox[i].second;
		}
	}

	return time + longest;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int N;
		cin >> N;

		int heat[10000];
		for (int i = 0; i < N; i++)
			cin >> heat[i];

		int eat[10000];
		for (int i = 0; i < N; i++)
			cin >> eat[i];

		for (int i = 0; i < N; i++)
			lunchBox.push_back(make_pair(eat[i], heat[i]));

		cout << Greedy(N) << endl;

		lunchBox.clear();
	}

	return 0;
}

알고리즘 200일 프로젝트 - 108 day

[문제 링크]

간단한 그리디 알고리즘 문제였다.

러시아팀의 한 선수를 이길 수 있는 한국팀의 선수가 여러명 있을 때 가장 레이팅이 낮은 선수를 매칭시켜야만 최대의 승점을 얻을 수 있기 때문에 이를 그대로 구현하였다.

먼저 러시아팀, 한국팀의 선수들을 레이팅에 따라 오름차순으로 정렬한다.

러시아팀에서 레이팅이 가장 낮은 선수를 시작으로 한국팀에서 레이팅이 가장 낮은 선수부터 비교한다.

한국팀 선수가 러시아팀 선수보다 레이팅이 같거나 클경우 두 선수를 매치 시키고 러시아팀의 다음 선수를 비교한다.

한국팀에서 가장 레이팅이 높은 선수까지 탐색했다면 더이상 비교할 필요가 없기 때문에 누적한 승점을 반환한다.

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

vector<int> rusia, korea;

int Greedy(int N)
{
	// 오름차순 정렬
	sort(rusia.begin(), rusia.end());
	sort(korea.begin(), korea.end());

	int lowest = 0, win = 0;

	for (int i = 0; i < N; i++)
		if (rusia[lowest] <= korea[i])
		{
			lowest++;
			win++;
		}

	return win;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int N;
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			int rate;
			cin >> rate;
			rusia.push_back(rate);
		}

		for (int i = 0; i < N; i++)
		{
			int rate;
			cin >> rate;
			korea.push_back(rate);
		}

		cout << Greedy(N) << endl;

		rusia.clear();
		korea.clear();
	}

	return 0;
}

알고리즘 200일 프로젝트 - 107 day