언제나 처음처럼

[문제 링크]

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

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

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

[문제 링크]

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

숫자를 만나면 수를 누적하고 자릿수를 올려주다가, '+'를 만나면 자릿수를 다시 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