언제나 처음처럼

[문제 링크]

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

학생은 a이상 b이하인 책을 받을 수 있고, 줄 수 있는 책은 1번부터 N번까지 N개 존재한다.

두 학생이 있을 때 서로 a가 같다면 b가 더 큰 학생이 받을 수 있는 책의 범위가 더 넓기 때문에 b가 작은 학생순으로 낮은 번호의 책을 나눠주는 것이 항상 최적해를 보장한다는 것을 알 수 있다.

이를 구현하기 위해 b를 기준으로 오름차순 정렬하고, b의 값이 같을 경우 a가 더 작은 학생이 앞에 가도록 정렬하였다. 그리고 한 학생이 여러권의 책을 받을 수 없기 때문에 check 배열을 통해 책을 받았는지 여부를 확인하였다.

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

bool check[1000];

int Greedy(vector<pair<int, int>>& student, int N, int M)
{
	sort(student.begin(), student.end());

	int here = 0, cnt = 0;
	
	for (int book = 1; book <= N; book++)
	{
		for (int here = 0; here < M; here++)
		{
			if (student[here].second <= book && student[here].first >= book && !check[here])
			{
				cnt++;
				check[here] = true;
				break;
			}
		}
	}

	return cnt;
}

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

	while (test_case--)
	{
		memset(check, 0, sizeof(check));

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

		cout << Greedy(data, N, M) << endl;
		
		data.clear();
	}

	return 0;
}

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

[문제 링크]

그리디 알고리즘과 DFS가 섞인 문제였다.

파이프를 연결할 수 있는 경우는 오른쪽 대각선 위, 오른쪽 옆, 오른쪽 대각선 아래 세가지가 있고, 파이프가 서로 겹치거나 엇갈리면 안되기 때문에 대각선 위 -> 옆 -> 아래 순으로 탐색 하는 것이 항상 최적해를 보장한다.

성공적으로 파이프를 연결했다면 1을 반환하고, 파이프가 연결되었기 때문에 다른 경우는 고려할 필요 없이 탐색을 종료한다.

한번 방문했던 좌표는 그전에 이미 시도해본 좌표이기 때문에 고려해줄 필요가 없다. 따라서 2차원 visit 배열을 선언하여 방문여부를 체크했다.

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

string board[10000];
bool visit[10000][500];
int dy[3] = { -1, 0, 1 };

int Greedy(int startY, int startX, int R, int C)
{
	if (startX == C - 1) return 1;

	int ret = 0;

	for (int i = 0; i < 3; i++)
	{
		int nextY = startY + dy[i];
		int nextX = startX + 1;

		if (nextY >= 0 && nextY < R && board[nextY][nextX] != 'x' && !visit[nextY][nextX])
		{
			visit[nextY][nextX] = true;
			ret = Greedy(nextY, nextX, R, C);
		}

		if (ret == 1)
			break;
	}

	return ret;
}

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

	int R, C;
	cin >> R >> C;

	for (int i = 0; i < R; i++)
		cin >> board[i];

	int cnt = 0;
	for (int i = 0; i < R; i++)
		cnt += Greedy(i, 0, R, C);

	cout << cnt << endl;

	return 0;
}

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

[문제 링크]

문제 풀이법을 떠올리기가 쉽지않았던 문제였다.

플로이드 와샬 알고리즘을 이용하는 문제였는데, 필자는 도시 A에서 도시 B로 이동하는데 걸리는 최소 시간을 비교함에 있어 도시 A에서 도시 C를 거쳐 도시 B로 가는 경우 뿐만 아니라 도시 A에서 도시 C를 거치고 도시 D를 거쳐 도시 B로 이동하는 시간이 더 짧을수도 있다고 생각하고 풀어서 정답을 출력할 수 없었다.

입력으로 주어지는 행렬이 각 도시에서 도시로 이동하는 최소 시간이기 때문에 도시 A에서 도시 B로 이동하는데 걸리는 최소 시간과 A와 B를 제외한 다른 도시를 경유해서 가는데 걸리는 최소 시간을 비교하여 걸리는 시간이 같을 경우 A->B로 연결되는 도로는 사용할 필요가 없으므로 제거하고, 다른 도시를 경유해서 가는데 걸리는 최소 시간이 더 짧을 경우 입력으로 받은 행렬이 잘못 주어진 것이므로 옳은 결과를 얻는 것이 불가능하다.

모든 도시를 경유해서 갔지만 위 두가지 경우에 해당하지 않는다면 다른 길이 존재하지 않는 것이므로 A->B로 연결되는 도로를 사용해야 한다.

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

int city[20][20];
bool check[20][20];

int Greedy(int N)
{
	memset(check, 1, sizeof(check));

	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
			for (int k = 0; k < N; k++)
			{
				if (i == j || i == k || j == k)
					continue;

				if (city[i][j] == city[i][k] + city[k][j])
				{
					check[i][j] = false;
					check[j][i] = false;
				}
				else if (city[i][j] > city[i][k] + city[k][j])
					return -1;
			}

	return 0;
}

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

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

	int sum = Greedy(N);

	if (sum == -1)
	{
		cout << "-1" << endl;
		return 0;
	}
	else
	{
		for (int i = 0; i < N; i++)
			for (int j = i+1; j < N; j++)
				if (check[i][j])
					sum += city[i][j];

		cout << sum << endl;
		return 0;
	}
}

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

[문제 링크]

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

입력받는 보석의 무게와 가격은 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