언제나 처음처럼

[문제 링크]

재밌는 그리디 알고리즘 문제였다.

입력받는 보석의 무게와 가격은 pair 컨테이너에 담고 가격을 기준으로 내림차순 정렬을 해주었고,

가방에 담을 수 있는 무게는 로그시간에 검색을 할 수 있도록 연관 컨테이너인 multiset 컨테이너에 오름차순으로 담아주었다.

가장 비싼 보석부터 해당 보석의 무게를 담을 수 있는 가방 중에서 가장 작은 무게의 가방을 선택하고, 담을 수 잇는 가방이 없다면 넘어가는 방식으로 구현하였다.

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

long long Greedy(vector<pair<int, int>>& jew, multiset<int>& bag, int N, int K)
{
	sort(jew.begin(), jew.end(), greater<pair<int, int>>()); // 보석 가격을 기준으로 오름차순 정렬

	int here = 0;
	long long sum = 0;

	while (!bag.empty() && here < N)
	{
		multiset<int>::iterator lowIter = bag.lower_bound(jew[here].second);
		if (lowIter != bag.end()) // 선택한 무게의 보석을 넣을 수 있는 가방이 존재한다면
		{
			sum += jew[here].first;
			bag.erase(lowIter);
		}

		here++;
	}

	return sum;
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int N, K;
	cin >> N >> K;

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

	multiset<int> bag;
	for (int i = 0; i < K; i++)
	{
		int C;
		cin >> C;
		bag.insert(C);
	}

	cout << Greedy(jew, bag, N, K) << endl;

	return 0;
}

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

[문제 링크]

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

각 자리마다 가장 많이 등장하는 알파벳을 뽑아서 문자열을 만들어주면 Hamming Distance의 합을 가장 작게 만들 수 있다.

사전순으로 가장 앞서는 것을 출력해야 하기 때문에 뉴클레오티드 A, T, G, C 를 A, C, G, T 순으로 비교하였다.

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

const int INF = 987654321;
char nuc[4] = { 'A', 'C', 'G', 'T' };
string DNA[1000];

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

string Greedy(int N, int M)
{
	string s;

	for (int i = 0; i < M; i++)
	{
		char idxChar;
		int idxCnt = 0;

		for (int j = 0; j < 4; j++)
		{
			int cnt = 0;
			for (int k = 0; k < N; k++)
				if (nuc[j] == DNA[k][i])
					cnt++;

			if (idxCnt < cnt)
			{
				idxCnt = cnt;
				idxChar = nuc[j];
			}
		}

		s.push_back(idxChar);
	}

	return s;
}

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

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

	string res = Greedy(N, M);

	int hamming = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (res[j] != DNA[i][j])
				hamming++;

	cout << res << endl;
	cout << hamming << endl;

	return 0;
}

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

[문제 링크]

멀티탭에 빈 구멍이 없고, 꽂혀있는 전기용품 중에 이후에 사용하지 않는 전기용품이 존재하지 않을 경우, 이후에 쓰게 될 빈도수가 가장 적은 전기용품을 먼저 뽑는 방법이 최적해를 보장한다고 생각하고 풀었으나 잘못된 접근이여서 고생했던 문제였다.

빈도수가 가장 적은 전기용품을 뽑는 것이 아닌, 가장 나중에 사용하게 되는 전기용품을 뽑아야 항상 최적해를 보장한다.

따라서, 멀티탭에 빈 구멍이 있거나 이미 꽂혀있는 전기용품이라면 플러그를 뺄 필요 없이 넘어가고, 두가지 경우에 해당하지 않는다면 이후에 사용할 일이 없는 전기용품이 있는지 확인한 다음 있다면 그 전기용품을 뽑도록 하고, 없다면 가장 나중에 사용되는 전기용품을 찾아 그 전기용품을 뽑도록 구현하면 된다.

#include <iostream>
using namespace std;

int arrCnt[101], arr[101];
bool check[101];

int Greedy(int N, int K)
{
	int empty = N, cnt = 0;

	for (int i = 1; i <= K; i++)
	{
		if (!check[arr[i]])
		{
			if (empty == 0)
			{
				int pick;

				bool ck = true;
				for (int j = 1; j <= K; j++)
					if (check[j] && arrCnt[j] == 0)
					{
						ck = false;
						pick = j;
						break;
					}

				if (ck)
				{
					int idx[100], temp = 0;

					for (int j = i + 1; j <= K; j++)
					{
						if (check[arr[j]])
						{
							bool ck = true;
							for (int i = 0; i < temp; i++)
							{
								if (arr[j] == idx[i])
								{
									ck = false;
									break;
								}
							}

							if (ck)
							{
								idx[temp] = arr[j];
								temp++;
							}
						}

						if (temp == N)
						{
							pick = arr[j];
							break;
						}
					}
				}

				cnt++;
				check[arr[i]] = true;
				check[pick] = false;
			}
			else
			{
				check[arr[i]] = true;
				empty--;
			}
		}

		arrCnt[arr[i]]--;
	}

	return cnt;
}

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

	for (int i = 1; i <= K; i++)
	{
		cin >> arr[i];
		arrCnt[arr[i]]++;
	}

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

	return 0;
}

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

[문제 링크]

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

문서의 가장 앞에서부터 탐색하면 찾는 단어가 등장하는 최대 횟수를 알 수 있다.

따라서 입력받은 문서의 가장 앞에서부터 차례대로 탐색하면서 찾는 단어와 일치하면 찾은 단어의 길이만큼 건너뛰고, 일치하지 않다면 한칸 건너뛰는 식으로 구현하였다.

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

int Greedy(string& s, string& f)
{
	int sLen = s.length();
	int fLen = f.length();
	int cnt = 0;
	for (int i = 0; i <= sLen - fLen; i++)
	{
		if (s.substr(i, fLen) == f)
		{
			cnt++;
			i += fLen - 1;
		}
	}

	return cnt;
}

int main(void)
{
	string str, find;

	getline(cin, str);
	getline(cin, find);

	cout << Greedy(str, find) << endl;

	return 0;
}

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

[문제 링크]

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

물이 새는 곳의 위치를 내림차순 정렬한 다음, 물이 새는 곳의 거리가 테이프의 길이보다 짧은지 긴지 비교한다.

물이 새는 곳의 거리가 테이프의 길이보다 짧다면 다음 장소까지 매꿀 수 있는지 비교해보고,

길다면 테이프 하나로 매꿀 수 없으므로 사용한 테이프를 1 증가시키고 다음 장소와 비교한다.

#include <iostream>
using namespace std;

void Quick_sort(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;
		}
	}

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

int Greedy(int arr[], int N, int L)
{
	Quick_sort(arr, 0, N - 1);

	int cnt = 0, tape = L - 1;
	
	for (int i = 1; i < N; i++)
	{
		int dist = arr[i - 1] - arr[i];
		if (dist > tape)
		{
			tape = L - 1;
			cnt++;
		}
		else
			tape -= dist;
	}

	return cnt + 1;
}

int main(void)
{
	int N, L, arr[1000];
	cin >> N >> L;

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

	cout << Greedy(arr, N, L) << endl;

	return 0;
}

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

[문제 링크]

어찌보면 간단한 그리디 알고리즘 문제였지만, 솔루션을 생각하기가 쉽지 않은 문제였다.

입력받은 추의 무게를 오름차순 정렬한 뒤 가장 가벼운 추부터 무게를 누적한다.

만약 (누적한 무게 + 1) 보다 현재 추의 무게가 더 클 경우 (누적한 무게 + 1)이 측정할 수 없는 무게 중 최솟값이 된다.

#include <iostream>
using namespace std;

void Quick_sort(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;
		}
	}

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

int Greedy(int arr[], int N)
{
	Quick_sort(arr, 0, N - 1);

	if (arr[0] != 1) return 1;

	int sum = 1, ret;
	for (int i = 1; i < N; i++)
	{
		if (sum + 1 < arr[i])
			break;

		sum += arr[i];
	}

	return sum + 1;
}

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

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

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

	return 0;
}

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

[문제 링크]

병든 나이트는 위아래로 이동할 수 있지만 왼쪽으로는 이동할 수 없고 오른쪽으로 밖에 이동하지 못한다.

따라서 세로 길이 N의 크기가 얼마인지는 중요하지 않으며, 위아래로 1칸 또는 2칸 이동할 수 있기 때문에 N이 1일 경우 나이트는 어느방향으로든 움직일 수 없고, N이 2일 경우 위아래로 2칸씩 이동할 수 없다. N이 3 이상일 경우 1칸 또는 2칸 자유롭게 이동할 수 있다.

또한 오른쪽으로 밖에 이동하지 못하기 때문에 가로 길이 M에 따라 이동할 수 있는 최대 회수가 정해지게 된다.

방문할 수 있는 칸의 최대 개수를 구하기 위해서는 N이 3이상이라는 가정하에 위아래로 2칸, 오른쪽으로 1칸씩 이동하는 방법이 항상 최적해를 보장한다.

마지막으로 이동 횟수가 4회 이상일 경우 나이트의 이동 방법을 모두 한번씩 사용해야 한다는 조건을 고려하여 알고리즘을 구현하면 된다.

#include <iostream>
using namespace std;

int Greedy(int N, int M)
{
	int cnt = 1;

	if (N == 1)
		return cnt;

	else if (N == 2)
	{
		cnt += (M - 1) / 2;
		return cnt >= 5 ? 4 : cnt;
	}

	else
	{
		if (M >= 7)
			return cnt + 4 + M - 7;
		else
		{
			cnt += M - 1;
			return cnt >= 5 ? 4 : cnt;
		}
	}
}

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

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

	return 0;
}

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

[문제 링크]

키가 큰 사람이 앞에 몇명이 있는지에 따라 줄 서는 위치가 바뀌기 때문에 키가 가장 작은 사람부터 큰 사람 순으로 줄을 맞춰주면 된다.

#include <iostream>
using namespace std;

const int INF = 987654321;
int arr[10], res[10];

void Greedy(int N)
{
	for (int i = 0; i < N; i++)
		res[i] = INF;

	for (int i = 0; i < N; i++)
	{
		int index = 0, here = 0;
		while (index <= arr[i])
		{
			if (res[here] > i+1)
			{
				index++;
				here++;
			}
			else
				here++;
		}
		res[here-1] = i + 1;
	}
}

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	Greedy(N);

	for (int i = 0; i < N; i++)
		cout << res[i] << ' ';

	return 0;
}

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