언제나 처음처럼

[문제 링크]

간단한 dp문제였다.

이동할수 있는 방향이 (y+1, x), (y, x+1), (y+1, x+1) 세가지 존재하기 때문에 (N, M)까지 이동할 때 얻을 수 있는 사탕 개수의 최댓값은 (N, M) 이전에 위치할 수 있는 좌표들 중 최댓값을 선택하도록 구현하면 원하는 결과를 얻을 수 있다.

추가) 좌표에 존재하는 사탕개수가 0 이상이기 때문에 대각선으로 이동하는 것보다 왼쪽 또는 아래로 이동하는 것이 항상 이득이다. 따라서 대각선으로 이동하는 (y+1, x+1) 의 경우는 고려하지 않아도 된다.

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

int arr[1001][1001], memo[1001][1001];

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

int Topdown(int y, int x)
{
	if (y == 0 || x == 0)
		return 0;

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

	return ret = max(Topdown(y - 1, x), max(Topdown(y, x - 1), Topdown(y - 1, x - 1))) + arr[y][x];
}

int Bottomup(int N, int M)
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			memo[i][j] = max(memo[i - 1][j], max(memo[i][j - 1], memo[i - 1][j - 1])) + arr[i][j];

	return memo[N][M];
}

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

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> arr[i][j];

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N, M) << endl;
	
	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N, M) << endl;

	return 0;
}

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

[문제 링크]

필자는 1행 1열에서 1행 M열까지 숫자를 입력받는다고 했을 때, 1행 i열에 1열부터 i열까지의 합을 메모이제이션하였다.

미리 배열의 합을 계산한 이유는 1행 i열부터 1행 j열까지 배열의 합을 memo[1][j] - memo[1][i-1] 식으로 간단히 구할 수 있기 때문이다.

위 식을 이용하여 각 행마다 배열의 합을 구하고 결과값에 누적시켜주면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

int memo[301][301];

int Solution(int i, int j, int x, int y)
{
	int ret = 0;
	for (int col = i; col <= x; col++)
		ret += memo[col][y] - memo[col][j-1];

	return ret;
}

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

	for (int i = 1; i <= N; i++)
	{
		int num, sum = 0;
		for (int j = 1; j <= M; j++)
		{
			cin >> num;
			sum += num;
			memo[i][j] = sum;
		}
	}

	int K;
	cin >> K;
	while (K--)
	{
		int i, j, x, y;
		cin >> i >> j >> x >> y;
		cout << Solution(i, j, x, y) << endl;
	}

	return 0;
}

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

[문제 링크]

문자열 A, B의 시작 지점에 따라 LCS는 각각 다르기 때문에 2차원 dp배열을 선언하였다.

문자열 A, B 모두 첫번째 원소에서 시작할 때 가지는 최대 길이는 A의 첫번째 문자와 같은 문자가 B에 존재하는 경우

A의 첫번째 문자를 LCS에 포함시킨 다음 A의 두번째 원소, B에서 A의 첫번째 문자와 일치하는 원소의 다음 위치에서 시작할 때 가지는 최대 길이 vs  첫번째 원소를 LCS에 포함시키지 않고 A의 두번째  원소, B의 첫번째 원소에서 시작할 때 가지는 최대 길이 중 더 큰 값이 정답이 된다.

만약 A의 첫번째 문자와 같은 문자가 B에 존재하지 않을 경우 LCS에 포함시킬 수 없기 때문에 최대 길이는 A의 두번째 원소, B의 첫번째 원소를 시작으로 할 때 최대 길이가 정답이 된다.

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

int memo[1000][1000];
string strA, strB;

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

int Topdown(int startA, int startB)
{
	if (startA == strA.length() || startB == strB.length())
		return 0;

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

	ret = 0;

	for (int i = startB; i < strB.length(); i++)
		if (strA[startA] == strB[i])
			return ret = max(Topdown(startA+1, startB), Topdown(startA+1, i + 1) + 1);

	return ret = Topdown(startA+1, startB);
}

int main(void)
{
	memset(memo, -1, sizeof(memo));

	cin >> strA >> strB;

	cout << Topdown(0,0) << endl;

	return 0;
}

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

[문제 링크]

변형된 LIS문제였다.

필자는 길이가 i인 수열에서 i번째 원소를 반드시 포함할 때 갖는 최대값을 memo[i]에 저장하였다.

수열의 길이 N을 입력받았다면 1~N까지 위 작업을 진행한 다음 memo[1]~memo[N]에서 가장 큰 값을 찾아주면 원하는 정답을 얻을 수 있다.

#include <iostream>
using namespace std;

int arr[1001], memo[1001];

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

int Topdown(int N)
{
	if (N == 0) return arr[N];

	int& ret = memo[N];
	if (ret != 0) return ret;
	
	ret = arr[N];

	for (int i = 0; i < N; i++)
		if (arr[i] < arr[N])
			ret = max(ret, Topdown(i) + arr[N]);
	
	return ret;
}

int Bottomup(int N)
{
	int ret = 0;

	for (int i = 0; i < N; i++)
	{
		memo[i] = arr[i];
		for (int j = 0; j < i; j++)
			if (arr[i] > arr[j])
				memo[i] = max(memo[i], memo[j] + arr[i]);
		
		ret = max(ret, memo[i]);
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	
	//top-down
	int res = 0;
	for(int i=0; i<N; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

	//bottom-up
	cout << Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

자연수 N을 제곱수의 합으로 나타낼 때 최소항의 개수를 찾는 방법은 min(1 + [N - (제곱한 값이 N보다 작거나 같은 수들의 제곱수)]의 항의 개수) 이다.

예를 들어 N = 10 일 때 최소 항의 개수는 dp[10] = min( 1 + dp[10-1], 1 + dp[10-4], 1 + dp[10-9] ) 로 나타낼 수 있다.

따라서 점화식은 다음과 같다.

for(i = 1; i<=N; i++)

if(i*i <= N) dp[N] = min(dp[N], 1 + dp[N-i*i])

#include <iostream>
using namespace std;

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

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

int Topdown(int N)
{
	if (N == 0) return 0;

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

	ret = INF;

	for (int i = 1; i <= N; i++)
	{
		if (i*i > N) break;
		ret = min(ret, 1 + Topdown(N - i * i));
	}

	return ret;
}

int Bottomup(int N)
{
	memo[0] = 0;
	memo[1] = 1;

	for (int i = 2; i <= N; i++)
	{
		memo[i] = INF;
		for (int j = 1; j <= N; j++)
		{
			if (j*j > i) break;
			memo[i] = min(memo[i], 1 + memo[i - j * j]);
		}
	}

	return memo[N];
}
int main(void)
{
	int N;
	cin >> N;

	cout << "top-down: " << Topdown(N) << endl;
	cout << "bottom-up: " << Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

top-down 방식으로 풀어보려다 너무 많은 시간을 허비한 문제였다.

동전의 순서만 다른 경우를 가려내기 위해선 2차원 dp 배열을 선언해야 하는데 dp[101][10001] 으로 선언하게 되면 메모리가 4mb를 넘게되어 메모리 초과가 발생하게 된다.

bottom-up 방식으로 풀었더니 코드도 훨씬 간결하고 쉽게 풀렸다. 

틀에 박힌 사고를 개선해야 한다는 것을 다시한번 느끼게 된 문제였다.

#include <iostream>
using namespace std;

int n, k, pay[101], memo[10001];

int Bottomup(int k)
{
	memo[0] = 1;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			if(j - pay[i] >= 0)
				memo[j] += memo[j - pay[i]];

	return memo[k];
}

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

	for (int i = 1; i <= n; i++)
		cin >> pay[i];

	cout << Bottomup(k) << endl;

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

시작 숫자와 자릿수를 상태값으로 가져야하기 때문에 2차원 dp 배열이 필요하다.

문제 조건을 보면 0부터 시작할 수 있고, 인접한 수가 같아도 오름차순으로 인정해준다고 되어있기 때문에 이를 유의하여 점화식을 세워주면 된다.

top-down 방식의 경우 시작 숫자가 i 일 때 그 뒤에 나올 수 있는 숫자는 i보다 같거나 큰 숫자이다. 따라서 시작 숫자를 i로 하고 자릿수-1을 매개변수로 넘겨주어 재귀호출하는 방법으로 풀 수 있다. 첫번째 자리에 올 수 있는 숫자는 0~9이므로 이를 다 더해주면 된다. 기저사례로 자릿수가 0일 때 끝에 도달했으므로 1을 반환한다.

bottom-up 방식의 경우 자리수가 1이고 시작 숫자가 0~9 일 때 가질 수 있는 경우의 수를 미리 저장한 다음, 임의의 수 i부터 시작하고 자리수가 N인 경우의 수는 시작 숫자가 i~9이고 자리수가 N-1인 경우의 수의 합인 것을 이용하여 값을 갱신해가면 간단하게 원하는 결과를 얻을 수 있다. 

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

int memo[10][1001];

int Topdown(int start, int N)
{
	if (N == 0) return 1;

	int& ret = memo[start][N];
	if (ret != 0) return ret;

	for (int i = start; i < 10; i++)
		ret += Topdown(i, N - 1) % 10007;

	return ret % 10007;
}

int Bottomup(int N)
{
	memset(memo, 0, sizeof(memo));

	for (int i = 0; i < 10; i++)
		memo[i][1] = 10 - i;

	for (int i = 2; i <= N; i++)
		for (int j = 0; j < 10; j++)
			for (int k = j; k < 10; k++)
				memo[j][i] += (memo[k][i - 1] % 10007);

	return memo[0][N] % 10007;
}

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

	// top-down
	cout << "top-down: " << Topdown(0,N) << endl;

	// bottom-up
	cout << "bottom-up: " << Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

이 문제는 점화식을 세우는 과정에서 자꾸 뇌정지가 와서 오래 걸린 문제였다.

top-down 방식의 경우 사이트가 서쪽에 N개 동쪽에 M개 있을 때 다리를 짓는 경우의 수는 서쪽의 N번째 사이트와 동쪽의 M번째 ~ N번째 사이트가 연결되는 경우의 수들의 합이다.

기저사례로 서쪽 사이트가 1개일 때, 동쪽 사이트 개수를 반환하고, 서쪽 사이트와 동쪽 사이트 개수가 같다면 1을 반환하였다.

bottom-up 방식의 경우 서쪽에 N개 동쪽에 M개 있을 때 다리를 짓는 경우의 수 = 서쪽의 N번째 사이트가 동쪽의 M번째 사이트와 연결되는 경우의 수 + 동쪽의 M-1번째 사이트와 연결되는 경우의 수이며, 이를 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

int memo[31][31];

//* W = 서쪽, E = 동쪽 *//
int Topdown(int W, int E)
{
	if (W == 1) return E;
	if (W == E) return 1;

	int& ret = memo[W][E];
	if (ret != 0) return ret;

	for (int i = 1; i <= E; i++)
		ret += Topdown(W - 1, E - i);

	return ret;
}

int Bottomup(int W, int E)
{
	for (int i = 1; i <= E; i++)
		memo[1][i] = i;

	for(int i=2; i<=W; i++)
		for (int j = i; j <= E; j++)
			memo[i][j] = memo[i-1][j-1] + memo[i][j-1];

	return memo[W][E];
}

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

		// top-down
		cout << "top-down: " << Topdown(N, M) << endl;
		// bottom-up
		cout << "bottom-up: "<< Bottomup(N, M) << endl;
	}
	return 0;
}

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