언제나 처음처럼

[문제 링크]

이 문제를 풀면서 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

[문제 링크]

입력의 크기가 크지 않음에도 불구하고 동적계획법으로 접근했다가 풀이까지 오래걸린 문제였다.

경우의 수는 두가지로 나뉜다.

1. 현재 숫자와 다음 숫자 사이를 괄호로 묶었을 때 최댓값

2. 다음 숫자와 그 다음 숫자 사이를 괄호로 묶었을 때 최댓값

ex) 1 + 2 * 3 -> (1 + 2) * 3 || 1 + (2 * 3)

위 경우의 수를 모두 고려하여 최댓값을 찾아주면 원하는 결과를 얻을 수 있다.

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

const int INF = 987654321;
string str;
int N, result = -INF;

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

int Calc(int first, int second, char oper)
{
	switch (oper)
	{
	case '+':
		return first + second;

	case '-':
		return first - second;

	case '*':
		return first * second;
	}
}

void Solution(int here, int sum)
{
	if (here > N - 1)
	{
		result = max(result, sum);
		return;
	}
	
	int firNum = sum;
	int secNum = str[here + 1] - '0';
	
	Solution(here + 2, Calc(firNum, secNum, str[here]));

	if (here + 2 < N)
	{
		int thirdNum = str[here + 3] - '0';
		Solution(here + 4, Calc(firNum, Calc(secNum, thirdNum, str[here + 2]), str[here]));
	}
}

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

	Solution(1, str[0]-'0');

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 113 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

[문제 링크]

이 문제가 왜 그리디 알고리즘으로 분류되어있는지 아리송한 문제였다.

필자는 완전탐색으로 풀이했다고 생각한다.

A문자열이 B문자열보다 짧을 경우 문자열 앞뒤로 아무 알파벳을 추가할 수 있다는 것은 B문자열과 일치하는 문자들을 추가할 수 있다는 뜻이기 때문에 A, B 문자열의 길이 차이만큼 한 칸씩 밀어서 비교하여 그중 차이가 최소인 값을 찾으면 그 값이 정답이 된다.

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

const int INF = 987654321;
int min(int a, int b) { return a < b ? a : b; }

int Greedy(string& a, string& b)
{
	int aLen = a.length();
	int bLen = b.length();
	int diff = bLen - aLen;


	int ret = INF;

	for (int i = 0; i <= diff; i++)
	{
		int res = 0;
		for (int j = 0; j < aLen; j++)
			if (a[j] != b[i + j])
				res++;

		ret = min(ret, res);
	}

	return ret;
}

int main(void)
{
	string A, B;
	cin >> A >> B;

	cout << Greedy(A, B) << endl;

	return 0;
}

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

[문제 링크]

필자는 인턴을 보내는 기준을 다음과 같이 정했다.

여학생이 이룰 수 있는 팀 개수가 남학생이 이룰 수 있는 팀 개수보다 많거나 같다면 남학생이 이룰 수 있는 팀 개수가 최대이기 때문에 여학생을 인턴으로 보내도 최대 팀 개수를 유지할 수 있다.

반대로 여학생이 이룰 수 있는 팀 개수가 남학생이 이룰 수 있는 팀 개수보다 적다면 여학생이 이룰 수 있는 팀 개수가 최대이기 때문에 남학생을 인턴으로 보내도 최대 팀 개수를 유지할 수 있다.

위 기준을 통해 학생들을 인턴으로 보내고나서 남은 학생들로 이룰 수 있는 팀 개수를 구하면 그 값이 정답이 된다.

#include <iostream>
using namespace std;

int Greedy(int woman, int man, int intern)
{
	while (intern--)
	{
		if (woman / 2 >= man)
			woman--;
		else
			man--;
	}

	return woman / 2 >= man ? man : woman / 2;
}

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

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

	return 0;
}

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