언제나 처음처럼

[문제 링크]

필자는 입력받은 식을 역순으로 탐색해서 풀었다.

숫자를 만나면 수를 누적하고 자릿수를 올려주다가, '+'를 만나면 자릿수를 다시 1의 자리로 바꿔준다.

그렇게 계속 누적하다가 '-'를 만나면 결과값에다 누적한 수를 빼고 0으로 초기화한다. 그리고 자릿수를 1의 자리로 바꿔준다.

문제에서 식의 처음과 끝은 반드시 숫자라고 명시했으므로 처음 나오는 수는 반드시 양수일 것이기 때문에 결과값에 처음 나온 수를 더한 값을 출력하면 원하는 결과를 얻을 수 있다.

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

int Greedy(string& exp)
{
	int len = exp.length();
	int ret = 0, sum = 0, digit = 1;
	for (int i = len-1; i >=0; i--)
	{
		if (exp[i] == '+')
			digit = 1;
		else if (exp[i] == '-')
		{
			ret -= sum;
			digit = 1;
			sum = 0;
		}
		else
		{
			sum += (exp[i]-'0') * digit;
			digit *= 10;
		}
	}

	return ret + sum;
}

int main(void)
{
	string exp;
	cin >> exp;

	cout << Greedy(exp) << endl;

	return 0;
}

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

[문제 링크]

30의 배수가 되기 위한 조건에는 2가지가 있다.

첫째, 반드시 0이 한개 이상 존재해야한다.

둘째, 각 자리수를 모두 더한 값이 3의 배수여야 한다.

위 조건을 검사하여 30의 배수가 가능한지 체크한 다음 불가능할 경우 -1 출력, 가능할 경우 N을 내림차순 정렬하여 그대로 출력해주면 원하는 결과를 얻을 수 있다.

처음엔 퀵정렬을 이용하여 정렬하였는데 정답은 받았지만 N의 최댓값이 100,000이기 때문에 효율성이 떨어졌다.

정렬할 숫자의 범위가 0~9로 제한되어 있다는 점을 이용하여 계수정렬로 정렬해 효율성을 높였다.

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

void Quick_sort(string& 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] - '0' >= data[pivot] - '0')
			i++;
		while (j > start && data[j] - '0' <= data[pivot] - '0')
			j--;

		if (i > j)
		{
			char temp = data[pivot];
			data[pivot] = data[j];
			data[j] = temp;
		}
		else
		{
			char temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	
	Quick_sort(data, start, j - 1);
	Quick_sort(data, j + 1, end);

	return;
}

void Counting_sort(string& data)
{
	int arr[10] = { 0 };

	int len = data.length();
	for (int i = 0; i < len; i++)
		arr[data[i] - '0']++;

	int here = 0;
	for (int i = 9; i >= 0; i--)
		while (arr[i]--)
			data[here++] = i + '0';
}

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

	int sum = 0, len = N.size();
	bool zeroCheck = false;
	for (int i = 0; i < len; i++)
	{
		if (N[i] == '0') zeroCheck = true;
		sum += N[i] - '0';
	}

	if (!zeroCheck || sum % 3 != 0)
		cout << -1 << endl;
	else
	{
		//Quick_sort(N, 0, len - 1);
		Counting_sort(N);
		cout << N << endl;
	}

	return 0;
}

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

[문제 링크]

k개의 로프를 이용하여 중량이 w인 물체를 들어올릴 때  각각의 로프에는 w/k만큼의 중량이 걸린다고 한다.

k개의 로프를 이용하는 경우 들어올릴 수 있는 물체의 최대 중량은 (들 수 있는 무게가 가장 낮은 로프 * k)로 나타낼 수 있다. 

따라서, 여러개를 묶었을 때 들 수 있는 최대 중량은 들 수 있는 무게가 가장 낮은 로프에 의해 결정되기 때문에 들 수 있는 무게가 큰 로프 순으로 묶어서 중량을 계산해야 항상 최적해를 얻을 수 있다.

#include <iostream>
using namespace std;

int lope[100000];

int max(int a, int b) { return a > b ? a : b; }

void Quick_sort(int start, int end)
{
	if (start >= end) return;

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

	while (i <= j)
	{
		while (i <= end && lope[i] >= lope[pivot])
			i++;
		while (j > start && lope[j] <= lope[pivot])
			j--;

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

	Quick_sort(start, j - 1);
	Quick_sort(j + 1, end);
}

int Greedy(int N)
{
	Quick_sort(0, N - 1); // 내림차순 정렬

	int ret = 0;
	for (int i = 0; i < N; i++)
		ret = max(ret, lope[i] * (i + 1));

	return ret;
}

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

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

	cout << Greedy(N) << endl;

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/124 동전 0 문제와 같은 유형의 문제였다.

엔화가 1, 5, 10, 50, 100, 500 단위인 것을 보면 배수로 이루어져 있다는 것을 알 수 있다.

따라서 가장 큰 금액인 500엔부터 비교하도록 구현하면 된다.

#include <iostream>
using namespace std;

int money[6] = { 500, 100, 50, 10, 5, 1 };

int Greedy(int change)
{
	int cnt = 0;

	for (int i = 0; i < 6; i++)
		if (change >= money[i])
		{
			cnt += change / money[i];
			change %= money[i];
		}

	return cnt;
}

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

	cout << Greedy(1000 - price) << endl;
}

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

[문제 링크]

알고리즘 문제 해결 전략에서도 풀어봤던 유형의 그리디 알고리즘 문제였지만 새로운 것을 알게된 문제였다.

회의가 빨리 끝나는 순으로 회의를 진행하면 항상 최적해를 얻을 수 있기 때문에 회의가 끝나는 시간을 기준으로 오름차순 정렬하여 회의를 진행하면 쉽게 정답을 얻을 수 있다.

필자는 STL algorithm 해더파일에 정의된 sort함수를 쓰지 않고 직접 퀵정렬을 구현해서 써봤는데 시간초과가 발생하였다.

문제에서 N이 최대 100,000이고 퀵정렬 최악의 시간복잡도가 O(N^2) 인 것을 고려하면 시간 초과가 뜨는 것이 이해는 갔지만 STL의 sort함수도 퀵정렬을 기반으로 동작한다고 알고 있었기 때문에 의구심이 들었다.

찾아본 결과 STL의 sort함수는 최악의 시간복잡도가 O(N^2)인 것을 보완한 특별한 정렬법을 사용한다고 한다.

https://www.acmicpc.net/board/view/16770

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

pair<int, int> schedule[100000];

int Greedy(int N)
{
	sort(schedule, schedule + N);

	int start = 0, ret = 0;

	for (int i = 0; i < N; i++)
	{
		if (start <= schedule[i].second)
		{
			ret++;
			start = schedule[i].first;
		}
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> schedule[i].second >> schedule[i].first;

	cout << Greedy(N) << endl;

	return 0;
}

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

[문제 링크]

이 문제같은 경우 메모이제이션을 활용한 동적계획법으로도 정답을 얻을 수 있을 것이다.

하지만 K의 최댓값이 100,000,000이고 동전의 가치가 1원부터 시작하기 때문에 최악의 경우 시간초과가 걸릴 것이 분명하다.

문제의 핵심은 입력으로 주어지는 조건에 있다.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

보다시피 Ai는 Ai-1의 배수이기 때문에 조합에 따라 K원을 만들지 못하거나, 만들 수 있는 경우로 나뉘지 않는다.

따라서, 가장 큰 가치의 동전부터 시작하여 동전의 가치가 K원보다 큰지 작은지 비교한 다음 작을 경우 K원을 동전의 가치로 나눈 몫을 동전 갯수에 누적시키고, 나머지를 가지고 다시 비교하는 것을 반복하면 최종적으로 K가 0이 되었을 때 누적된 동전 갯수가 곧 최소 갯수가 된다.

#include <iostream>
using namespace std;

int coin[10];

int Greedy(int N, int K, int cnt) // 재귀
{
	if (K == 0) return cnt;

	for (int i = N - 1; i >= 0; i--)
		if (K <= coin[i])
			return Greedy(N, K % coin[i], cnt + (K / coin[i]));
}

int Greedy2(int N, int K) // 비재귀
{
	int cnt = 0;

	for (int i = N - 1; i >= 0; i--)
	{
		if (K == 0) return cnt;

		if (K <= coin[i])
		{
			cnt += K / coin[i];
			K %= coin[i];
		}
	}

	return cnt;
}

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

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

	cout << Greedy(N, K, 0) << endl;

	cout << Greedy2(N, K) << endl;

	return 0;
}

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

[문제 링크]

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

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

#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