언제나 처음처럼

[문제 링크]

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

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

만약 (누적한 무게 + 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

[문제 링크]

이 문제를 풀면서 LIS를 O(N^2)이 아닌 O(NlogN) 시간에 푸는 방법에 대해서 배우게 되었다.

핵심은 lower_bound를 사용하여 logN 시간에 LIS배열을 완성한다는 것이다.

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

int port[40000];

int Greedy(int n)
{
	int LIS[40000], size = 1;
	LIS[0] = port[0];
	for (int i = 1; i < n; i++)
	{
		if (LIS[size-1] < port[i])
		{
			LIS[size] = port[i];
			size++;
		}
		else
		{
			int idx = lower_bound(LIS, LIS + size, port[i]) - LIS;
			LIS[idx] = port[i];
		}
	}

	return size;
}

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

	for (int i = 0; i < n; i++)
		cin >> port[i];

	cout << Greedy(n) << endl;

	return 0;
}

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

[문제 링크]

(1,1)부터 (N,M)까지 차례대로 탐색하면서 A행렬과 B행렬의 값이 일치하지 않는 위치를 발견하면 행렬을 변환하는 연산을 수행한다.

행렬 변환을 수행할 때마다 횟수를 카운팅하면서 (N,M)까지 탐색을 완료했을 때, A행렬과 B행렬이 일치하지 않는다면 불가능이므로 -1을 출력하고 일치한다면 카운팅한 횟수를 출력하면 정답을 받을 수 있다.

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

int Greedy(bool check[][50], int N, int M)
{
	int cnt = 0;
	for(int i=0; i<N-2; i++)
		for (int j = 0; j < M-2; j++)
			if (!check[i][j])
			{
				for (int k = 0; k < 3; k++)
					for (int l = 0; l < 3; l++)
						check[i + k][j + l] = !check[i + k][j + l];
				cnt++;
			}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (!check[i][j])
				return -1;

	return cnt;
}

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

	bool check[50][50];
	string A[50], B[50];

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

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

	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++)
		{
			if (A[i][j] == B[i][j])
				check[i][j] = true;
			else
				check[i][j] = false;
		}

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

	return 0;
}

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

[문제 링크]

탐욕법과 DFS를 사용하여 풀 수 있었다.

부등호를 만족하는 최댓값을 구하기 위해서는 가장 큰 숫자(9)부터 가장 작은 숫자(0) 순으로 조건을 만족하는 숫자를 선택해나가야 한다.

부등호를 만족하는 최솟값을 구하기 위해서는 최댓값과 반대로 가장 작은 숫자(0)부터 가장 큰 숫자(9) 순으로 조건을 만족하는 숫자를 선택해 나가면 된다.

최적의 숫자를 선택한 뒤 재귀호출한 결과가 등식을 만족했다면 다른 숫자들은 진행할 필요가 없기 때문에 결과를 반환하도록 구현하였다.

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

char arr[10];
bool check[10];

string Greedy(int here, int last, int k, bool ver)
{
	if (here == k) return "";

	string result;

	if (ver)
	{
		for (int i = 9; i >= 0; i--)
		{
			if (result.length() == k - here) 
				return result;

			if (here == -1)
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '>' && last > i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '<' && last < i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
		}
	}
	
	else
	{
		for (int i = 0; i <= 9; i++)
		{
			if (result.length() == k - here) 
				return result;

			if (here == -1)
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '>' && last > i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '<' && last < i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
		}
	}
    
	return result;
}

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

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

	cout << Greedy(-1, 0, k, 1) << endl;
	cout << Greedy(-1, 0, k, 0) << endl;

	return 0;
}

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

[문제 링크]

이 문제를 풀기 위해 필요한 정보는 패키지로 샀을 때 가장 저렴한 브랜드와, 낱개로 샀을 때 가장 저렴한 브랜드이다. 패키지 가격과 낱개 가격이 가장 저렴한 브랜드를 제외한 다른 브랜드는 고려하지 않아도 된다.

입력 받으면서 가장 저렴한 가격을 갱신하는 방법이 더 효율적이지만 필자는 배열에 저장한 다음 정렬하였다.

#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 p[], int s[], int N, int M)
{
	Quick_sort(p, 0, M - 1);
	Quick_sort(s, 0, M - 1);

	int sum = 0;
	while (N > 0)
	{
		if (N < 6)
		{
			if (p[0] < s[0] * N)
			{
				sum += p[0];
				N -= 6;
			}
			else
			{
				sum += s[0] * N;
				N = 0;
			}
		}
		else
		{
			int pack = N / 6;
			if (p[0] * pack < s[0] * (pack * 6))
			{
				sum += p[0] * pack;
				N -= pack * 6;
			}
			else
			{
				sum += s[0] * (pack * 6);
				N -= pack * 6;
			}
		}
	}

	return sum;
}

int main(void)
{
	int single[50], package[50];

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++)
		cin >> package[i] >> single[i];

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

	return 0;
}

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

[문제 링크]

반복문 횟수를 줄여야 하는데 자꾸 해메서 풀이까지 오래걸린 문제였다.

먼저 서류심사 성적을 기준으로 오름차순 정렬을 한 뒤, 서류심사 성적이 더 좋은 지원자들의 면접시험 성적과 서류심사 성적이 안좋은 지원자들의 면접시험 성적을 비교하여 서류심사 성적이 안좋은 지원자의 면접시험 성적이 더 높다면 그 지원자를 뽑는 식으로 구현하였다.

이번에도 퀵소트를 직접 구현해보았는데 시간초과가 발생하였다. 

입력받는 성적에서 중복되는 성적이 없고, 범위가 1~N 인 점을 이용하여 최악의 시간복잡도가 O(N)인 정렬 방법을 만들어서 구현하였다.

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

/* 시간 초과 발생 ///
void Quick_sort(vector<pair<int, int>>::iterator start, vector<pair<int, int>>::iterator end)
{
	if (start >= end) return;

	vector<pair<int, int>>::iterator pivot = start;
	vector<pair<int, int>>::iterator i = start + 1;
	vector<pair<int, int>>::iterator j = end - 1;

	while (i <= j)
	{
		while (i < end &&  (*i).first <= (*pivot).first)
			i++;
		while (j > start && (*j).first >= (*pivot).first)
			j--;

		if (i > j)
		{
			pair<int, int> temp = *pivot;
			*pivot = *j;
			*j = temp;
		}
		else
		{
			pair<int, int> temp = *i;
			*i = *j;
			*j = temp;
		}
	}

	Quick_sort(start, j);
	Quick_sort(j + 1, end);
}
*/

void DH_sort(vector<pair<int, int>>& data, int start, int end)
{
	int i = start;
	int j = end;

	while (i < j)
	{
		while (1)
		{
			if (data[i].first == i + 1)
			{
				i++;
				break;
			}
			else
			{
				pair<int, int> temp = data[data[i].first-1];
				data[data[i].first - 1] = data[i];
				data[i] = temp;
			}
		}
	}
}

int Greedy(vector<pair<int, int>>& emp, int N)
{
	//Quick_sort(emp.begin(), emp.end()); // 시간초과

	DH_sort(emp, 0, N);

	int ret = 1;
	int index = emp[0].second;
	for (int i = 1; i < N; i++)
		if (index > emp[i].second)
		{
			ret++;
			index = emp[i].second;
		}

	return ret;
}

int main(void)
{
	vector<pair<int, int>> emp;

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

		for (int i = 0; i < N; i++)
		{
			int a, b;
			cin >> a >> b;
			emp.push_back(make_pair(a, b));
		}

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

	return 0;
}

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