언제나 처음처럼

[문제 링크]

간단한 DP 문제였다. 피보나치 수열과 비슷한(거의 같은) 점화식으로 풀 수 있다.

2 x n 타일을 채우는 경우의 수는 타일 가장 오른쪽을 세로블록 한개로 채우는 경우의 수와 가로블록 두개로 채우는 경우의 수의 합과 같기 때문이다.

따라서 점화식은 dp(n) = dp(n-1) + dp(n-2) 이며,

기저사례로 n == 1일 때 1을 반환, n == 2일 때 2를 반환하여 횟수를 카운팅 해주면 쉽게 원하는 결과를 얻을 수 있다.

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

int memo[1001];

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

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

	return ret = (Solution(n - 1) + Solution(n - 2)) % 10007;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));
	int n;
	cin >> n;
	cout << Solution(n) << endl;

	return 0;
}

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

[문제 링크]

간단한 DP 문제였다. 0과 1이 호출되는 횟수를 카운팅하기 위해 pair 컨테이너를 사용하였고,

pair 컨테이너의 first 에는 0이 호출되는 횟수, second 에는 1이 호출되는 횟수를 저장하는 형태로 구현하였다.

끝으로 피보나치 함수의 점화식이 Sol(n) = Sol(n-1) + Sol(n+1) 인 것을 활용하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

pair<int, int> memo[41];

pair<int, int> Solution(int n)
{
	if (n == 0 || n == 1) return memo[n];

	pair<int, int>& ret = memo[n];
	if (ret.first != -1 && ret.second != -1) return ret;

	pair<int, int> a, b;
	a = Solution(n - 1);
	b = Solution(n - 2);

	return ret = make_pair(a.first + b.first, a.second + b.second);
}

int main(void)
{
	for (int i = 2; i < 41; i++)
		memo[i] = make_pair(-1, -1);

	memo[0] = make_pair(1, 0);
	memo[1] = make_pair(0, 1);

	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		pair<int, int> res = Solution(n);
		cout << res.first << ' ' << res.second << endl;
	}
	
	return 0;
}

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

[문제 링크]

간단한 DP 문제였다.

n을 1, 2, 3의 합으로 나타내는 방법의 수를 계산하는 함수를 Sol(int n) 이라고 할 때,

n이 10일 때 나올 수 있는 방법의 수 Sol(10)은  Sol(9) + Sol(8) + Sol(7) 과 같다.

따라서 기저사례로 n == 0 또는 n == 1 일 때 1을 반환하도록 하여 방법의 수를 카운팅하고

(n == 0일 때 1을 반환하는 이유는 n이 2 또는 3일 경우 숫자의 합이 아닌 2, 3 그 자체로도 표현할 수 있기 때문) 

중복호출 되는 n을 메모이제이션하여 알고리즘을 구현하면 원하는 결과를 얻을 수 있다.

다른 방법으로는 n이 1, 2, 3 일 때 방법의 수를 사전에 메모라이징 해두고 기저사례를 조금 수정하면 동일한 결과를 얻을 수 있다.

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

int memo[11];

int Solution(int n)
{
	if (n == 0 || n == 1) return 1;

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

	ret = 0;

	for (int i = 1; i <= 3; i++)
		if (n - i >= 0) ret += Solution(n - i);
	
	return ret;
}

/*
int Solution2(int n)
{
	memo[1] = 1, memo[2] = 2, memo[3] = 4;

	if (n == 1 || n == 2 || n == 3) return memo[n];

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

	ret = 0;

	for (int i = 1; i <= 3; i++)
		ret += Solution(n - i);

	return ret;
}
*/
int main(void)
{
	memset(memo, -1, sizeof(memo));
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		cout << Solution(n) << endl;
	}
	
	return 0;
}

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

[문제 링크]

알고리즘 문제해결전략에서 배운 방식으로 메모이제이션하여 Top-down 방식으로 풀었는데 무난하게 정답처리를 받을 수 있었다.

하지만 필자가 사용하는 컴파일러인 Visual Studio 2017 환경에서 돌렸을 때 N이 8000정도만 넘어가도 스택 오버플로가 발생하였다.

원인은 N이 커지면 커질수록 재귀호출 횟수가 급격하게 증가하는데, 이때 프로그램이 컴파일러의 호출 스택에서 이용가능한 공간 이상을 사용하려다 충돌이 일어나게 되는 것이었다.

따라서 스택 오버플로 문제를 해결하기 위해 재귀호출이 아닌 for문으로 알고리즘을 구현하였고, 재귀호출 없이 Top-down 방식을 구현하는 것은 불가능하다 판단하여 Bottom-up 방식으로 문제를 해결하였다.

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

const int INF = 987654321;
int memo[1000001];

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

int TopDown(int N)
{
	if (N == 1) return 0;

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

	ret = 0;

	int A = INF, B = INF, C = INF;
	if (N % 3 == 0) A = 1 + TopDown(N / 3);
	if (N % 2 == 0) B = 1 + TopDown(N / 2);
	C = 1 + TopDown(N - 1);

	return ret = min(A, min(B, C));
}

int BottomUp(int N)
{
	memo[1] = 0;
	for (int i = 2; i <= N; i++)
	{
		memo[i] = memo[i - 1] + 1;
		if (i % 3 == 0) memo[i] = min(memo[i], memo[i / 3] + 1);
		if (i % 2 == 0) memo[i] = min(memo[i], memo[i / 2] + 1);
	}

	return memo[N];
}
int main(void)
{
	int N;
	cin >> N;
	
	memset(memo, -1, sizeof(memo));
	
	cout << BottomUp(N) << endl;
	
	return 0;
}

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