언제나 처음처럼

[문제 링크]

알고리즘 문제해결전략의 비트마스크 부분을 공부하면서 풀게된 첫 문제였다.

주어지는 입력의 범위가 20 미만으로 작기 때문에 최대 32비트 길이의 2진수를 표현할 수 있는 int형 정수의 비트연산을 통해 효율적으로 정답을 구할 수 있다.

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

const int INF = 987654321;
int N, K, M, L;
int preceding[12], classes[10];
int memo[10][1 << 12];

int min(int a, int b) { return a < b ? a : b; }

int BitCount(int taken)
{
	int cnt = 0;

	for (int i = 0; i < N; i++)
		if (taken & (1 << i))
			cnt++;

	return cnt;
}

int Topdown(int semester, int taken)
{
	if (BitCount(taken) >= K) return 0;
	if (semester >= M) return INF;

	int& ret = memo[semester][taken];
	if (ret != 0) return ret;

	ret = INF;

	int canTake = (classes[semester] & ~taken);

	for (int i = 0; i < N; i++)
		if ((canTake & (1 << i)) && (preceding[i] & taken) != preceding[i])
			canTake &= ~(1 << i);

	for (int take = canTake; take > 0; take = ((take - 1) & canTake))
	{
		if(BitCount(take) > L) continue;
		
		ret = min(ret, 1 + Topdown(semester + 1, taken | take));	
	}

	ret = min(ret, Topdown(semester+1, taken));

	return ret;
}

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

	while (test_case--)
	{
		memset(preceding, 0, sizeof(preceding));
		memset(classes, 0, sizeof(classes));
		memset(memo, 0, sizeof(memo));

		cin >> N >> K >> M >> L;

		
		for (int i = 0; i < N; i++)
		{
			int R;
			cin >> R;
			
			for (int j = 0; j < R; j++)
			{
				int num;
				cin >> num;
				preceding[i] |= (1 << num);
			}
		}

		for (int i = 0; i < M; i++)
		{
			int C;
			cin >> C;

			for (int j = 0; j < C; j++)
			{
				int num;
				cin >> num;
				
				classes[i] |= (1 << num);
			}
		}

		int result = Topdown(0, 0);

		if (result == INF)
			cout << "IMPOSSIBLE" << endl;
		else
			cout << result << endl;
	}

	return 0;
}

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

[문제 링크]

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

항상 길이가 가장 짧은 두 문자열을 합치는 것이 최적해를 보장하기 때문에, 오름차순 정렬을 통해 길이가 가장 짧은 두 문자열을 합치도록 구현하였다.

삽입, 삭제 연산이 빈번할 때 유리한 list 컨테이너를 사용하였다. 두 문자열을 합칠 때마다 새로운 원소가 추가되기 때문에 오름차순 정렬을 수행해줬다.

또한 원소를 삽입할 때 자동으로 정렬되어 삽입되는 set 컨테이너를 사용해서 구현해보았는데, 원소 검색에 효율적인 set 컨테이너는 삽입 삭제 연산에 시간이 오래 걸린다는 단점이 있어 시간초과가 날수도 있겠다 생각했지만 통과되었다.

// 추가: 알고리즘 문제해결 전략에서는 priority_queue 를 사용하여 구현하였다. 우선순위큐는 원소를 자동으로 정렬해줄뿐더러 새 원소를 추가하는 작업을 log시간에 할 수 있기 때문에 가장 효율적이다.

<list 사용>

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

list<int> str;

int Greedy(int n)
{
	if (n == 1)
		return str.front();

	int result = 0;
	while (--n)
	{
		str.sort();

		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += str.front();
			str.pop_front();
		}
		result += join;
		str.push_back(join);
	}

	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.push_back(len);
		}

		cout << Greedy(n) << endl;
		str.clear();
	}

	return 0;
}

<multiset 사용>

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

multiset<int> str;

int Greedy(int n)
{
	if (n == 1)
		return *str.begin();

	int result = 0;
	while (--n)
	{
		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += *str.begin();
			str.erase(str.begin());
		}
		result += join;
		str.insert(join);
	}

	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.insert(len);
		}

		cout << Greedy(n) << endl;
		str.clear();
	}

	return 0;
}

<priority_queue 사용>

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


priority_queue<int, vector<int>, greater<int>> str;

int Greedy(int n)
{
	int result = 0;

	if (n == 1)
	{
		result = str.top();
		str.pop();
		return result;
	}

	while (--n)
	{
		int join = 0;
		for (int i = 0; i < 2; i++)
		{
			join += str.top();
			str.pop();
		}
		result += join;
		str.push(join);
	}

	str.pop();
	return result;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int len;
			cin >> len;
			str.push(len);
		}

		cout << Greedy(n) << endl;
	}

	return 0;
}

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

[문제 링크]

먹는데 가장 오래걸리는 도시락을 먼저 데우고 먹기 시작해야 가장 빨리 점심시간을 마칠 수 있다.

따라서, 먹는데 걸리는 시간을 기준으로 내림차순 정렬한 다음 오래 걸리는 도시락 순으로 데우도록 구현하였다.

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

vector<pair<int, int>> lunchBox;

int Greedy(int N)
{
	// 먹는데 오래걸리는 순으로 정렬
	sort(lunchBox.begin(), lunchBox.end(), greater<pair<int, int>>());

	int longest = 0, time = 0;

	for (int i = 0; i < N; i++)
	{
		if (longest < lunchBox[i].first + lunchBox[i].second)
		{
			longest = lunchBox[i].first;
			time += lunchBox[i].second;
		}
		else
		{
			longest -= lunchBox[i].second;
			time += lunchBox[i].second;
		}
	}

	return time + longest;
}

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

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

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

		for (int i = 0; i < N; i++)
			lunchBox.push_back(make_pair(eat[i], heat[i]));

		cout << Greedy(N) << endl;

		lunchBox.clear();
	}

	return 0;
}

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

[문제 링크]

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

러시아팀의 한 선수를 이길 수 있는 한국팀의 선수가 여러명 있을 때 가장 레이팅이 낮은 선수를 매칭시켜야만 최대의 승점을 얻을 수 있기 때문에 이를 그대로 구현하였다.

먼저 러시아팀, 한국팀의 선수들을 레이팅에 따라 오름차순으로 정렬한다.

러시아팀에서 레이팅이 가장 낮은 선수를 시작으로 한국팀에서 레이팅이 가장 낮은 선수부터 비교한다.

한국팀 선수가 러시아팀 선수보다 레이팅이 같거나 클경우 두 선수를 매치 시키고 러시아팀의 다음 선수를 비교한다.

한국팀에서 가장 레이팅이 높은 선수까지 탐색했다면 더이상 비교할 필요가 없기 때문에 누적한 승점을 반환한다.

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

vector<int> rusia, korea;

int Greedy(int N)
{
	// 오름차순 정렬
	sort(rusia.begin(), rusia.end());
	sort(korea.begin(), korea.end());

	int lowest = 0, win = 0;

	for (int i = 0; i < N; i++)
		if (rusia[lowest] <= korea[i])
		{
			lowest++;
			win++;
		}

	return win;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int N;
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			int rate;
			cin >> rate;
			rusia.push_back(rate);
		}

		for (int i = 0; i < N; i++)
		{
			int rate;
			cin >> rate;
			korea.push_back(rate);
		}

		cout << Greedy(N) << endl;

		rusia.clear();
		korea.clear();
	}

	return 0;
}

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

[문제 링크]

교도소가 있는 마을(P)에서 지난 일수(D)동안 도달할 확률을 계산할 마을(Q)에 도달할 수 있는 경로의 수가 여러 개일 때 확률을 구하기 위해서는 각 경로의 확률을 더해줘야한다는 사실을 몰라서 어려웠던 문제였다.

이 사실을 책에서 참고한 것을 제외하면 전체적인 알고리즘을 책을 보지 않고 구현했다는 생각에 뿌듯함과 보람을 느꼈다.

필자는 도달할 확률을 계산할 마을(Q)를 시작으로 하여 역순으로 탐색하였다.

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

int N, D, P, Q;
double memo[101][51];
bool map[51][51];
int dist[51];

double Solution(int day, int here)
{
	if (here == P && day == 0) return 1;
	if (day == 0) return 0;

	double& ret = memo[day][here];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 0; i < N; i++)
	{
		int path = map[here][i] * dist[i];
		double temp = 0;
		if (path != 0)
			temp = Solution(day - 1, i) / path;

		ret += temp;
	}
	return ret;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(dist, 0, sizeof(dist));

		for (int i = 0; i < 101; i++)
			for (int j = 0; j < 51; j++)
				memo[i][j] = -1;

		cin >> N >> D >> P;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
			{
				cin >> map[i][j];
				if (map[i][j]) dist[i]++;
			}

		int T;
		cin >> T;
		while (T--)
		{
			cin >> Q;
			printf("%.8f ", Solution(D, Q));
		}
		printf("\n");
	}

	return 0;
}

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

[문제 링크]

최상단에 블록을 몇개 놓느냐에 따라 그 아래 블록에 놓을 수 있는 경우의 수가 정해진다.

n개의 블록으로 폴리오미노를 만든다고 했을 때, 최상단에 블록 2개를 놓는다면 그 아래 블록은 n-2개의 블록으로 폴리오미노를 만드는 경우와 같다.

또한 최상단 블록과 그 아래 블록을 한칸씩 엇갈리게(?) 놓는 경우도 있으므로 이 경우만큼 곱해주어야 한다.

최상단 블록을 first, 그 아래 블록을 second라고 했을 때, 엇갈리게 놓는 경우의 수는 (first + second - 1) 이다.

따라서 이 문제는 큰 문제를 작은 문제로 쪼갤 수 있기 때문에 재귀호출로 구현할 수 있으며

블록의 개수를 n, 최상단에 놓는 블록의 개수를 first 로 하여 2차원 배열에 메모라이징을 적용할 수 있다.

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

const int MOD = 10000000;
int memo[101][101];		

int Solution(int n, int first)
{
	if (n == first) return 1;

	int& ret = memo[n][first];
	if (ret != -1) return ret;

	ret = 0;
	for (int second = 1; second <= n - first; second++)
	{
		int add = first + second - 1;
		add *= Solution(n - first, second);
		add %= MOD;
		ret += add;
		ret %= MOD;
	}
	return ret;
}
int main(void)
{
	memset(memo, -1, sizeof(memo));
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		int ret = 0;
		for (int i = 1; i <= n; i++)
		{
			ret += Solution(n, i);
			ret %= MOD;
		}
		cout << ret << endl;
	}

	return 0;
}

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

[문제 링크]

(비대칭 타일수 = 전체 타일수 - 대칭 타일수) 라는 것을 알 수 있다.

n이 홀수라면 가운데 타일이 놓이는 경우가 1개 밖에 없지만, 짝수라면 가운데 타일이 놓이는 경우가 2개 존재한다.

따라서 n에 대한 전체 타일수를 구한 다음,

n이 홀수라면 전체 타일수에 (n / 2)에 대한 전체 타일수를 빼주고,

n이 짝수라면 전체 타일수에 (n / 2)에 대한 전체 타일수와 (n / 2 -1)에 대한 전체 타일수를 빼준다.

위 과정을 통해 결과적으로 양쪽 타일이 대칭인 경우를 제거할 수 있다.

 1,000,000,007 을 나눠주기 전에 먼저 한번 더해줘야 한다는 것을 생각하지 못하여 책을 보고 이해하게 되었다.

(만약 1,000,000,008과 1,000,000,006이 있을 때 전자는 나머지 결과 1이라는 값을 가지고, 후자는 1,000,000,006 값을 가지게 되는데 전자와 후자의 차는 2가 정상이지만, 나머지 연산을 거치면서 -1,000,000,005 값을 가지게 되어 오류가 출력될 수 있기 때문. -1,000,000,005에 1,000,000,007을 더해주게 되면 값이 2로 바뀜)

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

const int MOD = 1000000007;
int memo[101];

int tilingCount(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;

	int& ret = memo[n];
	if (ret != -1) return ret;
	return ret = (tilingCount(n - 1) + tilingCount(n - 2)) % MOD;
}
int Solution(int n)
{
	if (n % 2 == 1) return (tilingCount(n) - tilingCount(n / 2) + MOD) % MOD;

	int ret = tilingCount(n);
	ret = (ret - tilingCount(n / 2) + MOD) % MOD;
	ret = (ret - tilingCount(n / 2 - 1) + MOD) % MOD;
	return ret;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		int n;
		cin >> n;
		if (n == 2) 
			cout << "0" << endl;
		else
			cout << Solution(n)<< endl;
	}
	return 0;
}

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

[문제 링크]

알고리즘 문제해결전략 책에 나와있는 알고리즘과 동일하게 구현하였다.

제대로 구현한 것이 분명한데 자꾸 쌩뚱맞은 결과가 출력되어서 골머리를 앓았다.

double형 2차원 배열을 memset()함수를 통해 -1로 초기화했다는 것이 오답의 원인이었다.

이중 for문으로 memo[1001][2001] 배열을 -1로 초기화하여 문제를 해결하였다.

#include <cstdio>
using namespace std;

double memo[1001][2001];
int n, m;

double Solution(int days, int clime)
{
	if (days == m) return clime >= n ? 1 : 0;

	double& ret = memo[days][clime];
	if (ret != -1) return ret;

	return ret = (0.25 * Solution(days + 1, clime + 1)) + (0.75 * Solution(days + 1, clime + 2));
}
int main(void)
{
	int tc;
	scanf("%d", &tc);

	while (tc--)
	{
		for (int i = 0; i < 1001; i++)
			for (int j = 0; j < 2001; j++)
				memo[i][j] = -1;

		scanf("%d %d", &n, &m);
		printf("%.10f\n", Solution(0, 0));
	}

	return 0;
}

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