언제나 처음처럼

[문제 링크]

지난번에 완전탐색으로 한번 풀었던 문제였는데 이번에 동적 계획법을 사용하여 다시 풀게되었다.

아래에서 위로 탐색하는 알고리즘은 금방 생각해냈지만, 위에서 아래로 탐색하여 정답을 얻어내는 알고리즘을 생각하다가 이틀이나 날려먹었다.....

일단은 아래에서 위로 재귀호출을 통해 탐색하는 방식으로 문제를 해결하였다.

이 문제의 핵심은 해당 일에 상담을 했을 때 얻는 최대이익과 상담을 하지 않았을 때 얻는 최대이익 중 더 큰 값을 선택한다는 것에 있다.

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

dp(N) = max(dp(N+1), dp(N+T[N]) + P[N]);

위 점화식을 알고리즘으로 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

const int INF = 987654321;
int N, T[16], P[16], memo[16];
inline int max(int a, int b) { return a > b ? a : b; }

int brute(int start, int pay)
{
	int ret = pay;
	for (int i = start; i < N; i++)
	{
		int next = i + T[i];
		if (next > N) continue;
		ret = max(ret, brute(next, pay + P[i]));
	}
	return ret;
}

int Topdown(int start)
{
	if (start >= N) return start == N ? 0 : -INF;

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

	return ret = max(Topdown(start + 1), Topdown(start + T[start]) + P[start]);
}

int main(void)
{
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> T[i] >> P[i];

	// brute-force
	cout << brute(0, 0) << endl;

	// top-down
	cout << Topdown(0) << endl;

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

파도반 수열에는 일정한 규칙이 있는데, 이를 점화식으로 표현하면 다음과 같다.

padovan(N) = padovan(N-2) + padovan(N-3)

위 점화식을 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

long long memo[101];

long long Topdown(int N)
{
	if (N == 1) return 1;
	if (N == 2) return 1;
	if (N == 3) return 1;

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

	return ret = Topdown(N - 2) + Topdown(N - 3);
}

long long Bottomup(int N)
{
	memo[1] = memo[2] = memo[3] = 1;

	for (int i = 4; i <= N; i++)
		memo[i] = memo[i - 2] + memo[i - 3];
	
	return memo[N];
}

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

		// Top-down
		cout << "Top-down: " << Topdown(N) << endl;

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

	return 0;
}

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

[문제 링크]

1x2, 2x1 타일을 사용해서 2 x n 직사각형을 채우는 문제의 업그레이드 버젼이다.

먼저, 1x2, 2x1 타일을 사용하는 타일링 문제의 점화식이 dp(n) = dp(n-1) + dp(n-2) 라는 것을 기억하자.

위 점화식에서 dp(n-1)은 2x(n-1) 타일을 채우는 방법의 수 * 2x1 타일을 채우는 방법의 수를 나타내는데,

2 x 1 타일을 채우는 방법이 한가지밖에 존재하지 않기 때문에 *1 이 생략된 것이다.

dp(n-2) 도 마찬가지로 2x(n-2) 타일을 채우는 방법의 수 * 2x2 타일을 채우는 방법의 수를 나타내는데,

2x2 타일을 채우는 방법은 1x2 타일 2개로 채우는 방법과 2x1 타일 2개로 채우는 방법이 존재하지만

2x1 타일 2개로 채우는 방법은 dp(n-1)과 중복되므로 제외시킨다.

따라서 2x2 타일을 채우는 방법도 한가지 밖에 존재하지 않기 때문에 *1이 생략된 것이다.

이 문제는 1x2, 2x1 타일과 추가로 2x2 타일을 사용할 수 있다고 한다.

2x2 타일이 추가되었기 때문에 2x1 타일을 채우는 방법의 수는 변함이 없다.

하지만 2x2 타일을 채우는 방법은 1x2 타일 2개로 채우는 방법에 추가로 2x2 타일 1개로 채우는 방법이 생기게 되므로 총 두가지 방법이 존재하게 되어 * 2를 해주어야 한다.

따라서 이 문제의 점화식은 다음과 같다.

dp(n) = dp(n-1) + (dp(n-2) * 2)

위 점화식을 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

const int MOD = 10007;
int memo[1001];

int Topdown(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 3;

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

	return ret = (Topdown(n - 1) + (Topdown(n - 2) * 2)) % MOD;
}

int Bottomup(int n)
{
	memo[1] = 1;
	memo[2] = 3;

	for (int i = 3; i <= n; i++)
		memo[i] = (memo[i - 1] + (memo[i - 2] * 2)) % MOD;

	return memo[n];
}

int main(void)
{
	int n;
	cin >> n;
	
	// Top-down
	cout << "Top-down: " << Topdown(n) << endl;
	
	// Bottom-up
	cout << "Bottom-up: "<< Bottomup(n) << endl;

	return 0;
}

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

[문제 링크]

알고스팟의 LIS 문제와 같은 문제였다. 

Top-down 방식의 알고리즘은 1~N번째에서 시작하여 아래 방향으로 1번째까지 탐색하면서 가장 긴 LIS를 찾아주도록 구현하였고, 기저사례로 현재 위치가 1번째일 경우 LIS는 반드시 1이므로 1을 반환하도록 하였다.

Bottom-up 방식의 알고리즘은 1번째에서 시작하여 윗 방향으로 1~N번째까지 탐색하면서 가장 긴 LIS를 찾아주도록 구현하였다. 1번째까지만 탐색하는 경우와 LIS가 최소일 때 길이는 무조건 1이므로 dp배열을 1로 초기화 해주었다.

#include <iostream>
using namespace std;

int arr[1001], memo[1001];

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

int TopDown(int here)
{
	if (here == 1) return 1;

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

	ret = 1;

	for (int i = here-1; i > 0; i--)
		if (arr[i] < arr[here])
			ret = max(ret, TopDown(i) + 1);

	return ret;
}

int BottomUp(int N)
{	
	for (int i = 0; i < 1001; i++)
		memo[i] = 1;

	int ret = 1;
	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j <= i; j++)
			if (arr[i] > arr[j] && memo[i] < memo[j] + 1)
				memo[i] = memo[j] + 1;

		ret = max(ret, memo[i]);
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	
	// Top-down
	int res = 0;
	for (int i = 1; i <= N; i++)
		res = max(res, TopDown(i));
	cout << "Top-down: " << res << endl;

	// Bottom-up
	cout << "Bottom-up: " << BottomUp(N) << endl;

	return 0;
}

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

[문제 링크]

5개월 전에 책 없이 공부할 때 결국 못풀고 포기한 문제였다. 그 당시엔 정말 어렵게 느껴졌던 문제였는데 동적계획법을 제대로 이해하고 보니 풀이법을 금방 생각해낼 수 있었다.

 0~9 사이의 숫자 number로 시작하는 길이가 N인 계단수는 number-1로 시작하는 길이가 N-1인 계단수 + number+1로 시작하는 길이가 N-1인 계단수와 같다. 그리고 number가 0일 때 number-1인 -1과 9일 때 number+1인 10은 0~9 사이의 숫자가 아니므로 계산에서 제외시켜야 한다.

따라서 이 문제의 점화식을 다음과 같이 표현할 수 있다.

if (number == 0)  dp(N, number) = dp(N-1, number+1)

else if (number == 9)  dp(N, number) = dp(N-1, number-1)

else  dp(N, number) = dp(N-1, number-1) + dp(N-1, number+1)

위 점화식을 알고리즘으로 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

const int MOD = 1000000000;
int memo[101][10];

int TopDown(int n, int here)
{
	if (n == 1) return 1;

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

	if (here == 0)
		return ret = TopDown(n - 1, here + 1) % MOD;
	else if (here == 9)
		return ret = TopDown(n - 1, here - 1) % MOD;
	else
		return ret = (TopDown(n - 1, here - 1) + TopDown(n - 1, here + 1)) % MOD;
}

int BottomUp(int n)
{
	for (int i = 0; i <= 9; i++)
		memo[1][i] = 1;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			if (j == 0)
				memo[i][j] = memo[i - 1][j + 1] % MOD;
			else if (j == 9)
				memo[i][j] = memo[i - 1][j - 1] % MOD;
			else
				memo[i][j] = (memo[i - 1][j - 1] + memo[i - 1][j + 1]) % MOD;
		}
	}
	int res = 0;
	for (int i = 1; i <= 9; i++)
	{
		res += memo[n][i];
		res %= MOD;	// memo[n][i]가 3,000,000,00 정도의 값이라고 생각했을 때
        			// 1~9까지 반복하여 더하다보면 10억을 넘어갈 수 있기 때문에 %=MOD 해줌
	}

	return res;
}
int main(void)
{
	int n;
	cin >> n;
	
	// Top-Down
	int res = 0;
	for (int i = 1; i <= 9; i++)
	{
		res += TopDown(n, i);
		res %= MOD; // 위와 동일
	}
	cout << res << endl;

	// Bottom-Up
	cout << BottomUp(n) << endl;

	return 0;
}

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

[문제 링크]

이 문제는 dp 함수를 수행하면서 만들어지는 연속합 중 최대값을 저장해줘야 한다.

TopDown 알고리즘은 다음과 같다.

시작 위치가 n일 때 최대 연속합은 시작 위치가 n-1일 때 최대 연속합에 n번째가 가지는 정수를 더한 값과 n번째가 가지는 정수 중 더 큰 값이 최대 연속합이 된다. 따라서 점화식은 다음과 같이 표현할 수 있다. 

TopDown(n) = max(TopDown(n-1) + arr[n], arr[n])

위 점화식을 이용하여 첫번째부터 마지막까지를 시작 위치로 했을 때 나오는 최대 연속합을 구하면서 그중 최대값을 저장하고 출력하도록 구현하면 된다.

BottomUp 알고리즘도 탐색 순서만 다를뿐 TopDown 알고리즘과 동일하다.

#include <iostream>
using namespace std;

const int MINF = -987654321;

int arr[100001], memo[100001];

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

int TopDown(int here)
{
	if (here == 0) return arr[here];

	int& ret = memo[here];
	if (ret != MINF) return ret;

	ret = max(TopDown(here-1) + arr[here], arr[here]);

	return ret;
}

int BottomUp(int n)
{
	int ret;
	ret = memo[0] = arr[0];

	for (int i = 1; i < n; i++)
	{
		memo[i] = max(memo[i - 1] + arr[i], arr[i]);
		ret = max(ret, memo[i]);
	}

	return ret;
}

int main(void)
{
	for (int i = 0; i < 100001; i++)
		memo[i] = MINF;
	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	//Top-Down
	int res = MINF;
	for (int i = 0; i < n; i++)
		res = max(res, TopDown(i));
	cout << "TopDown: " << res << endl;
	
	//Bottom-Up
	cout << "BottomUp: " << BottomUp(n) << endl;

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/74 

계단 오르기와 유사한 형태의 문제였다.

차이점은 계단 오르기 문제는 마지막 계단을 반드시 밟아야 한다는 조건이 있었지만,

이 문제는 마지막 포도주를 반드시 마셔야 한다는 조건이 없다는 것이다.

따라서 마지막 포도주를 반드시 마시는 경우와 마시지 않는 경우의 최대값을 추가로 비교해줘야 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

int wine[10001], memo[10001][2];

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

int TopDown(int here, int check)
{
	// check == 0 : 뒤에 포도주 마셨을 때
	// check == 1 : 뒤에 포도주 안 마셨을 때

	if (here < 0) return 0;

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

	if (check)
		ret = TopDown(here - 1, 0) + wine[here];

	return ret = max(ret, max(TopDown(here - 1, 1), TopDown(here - 2, 1) + wine[here]));
}

int BottomUp(int n)
{
	// memo[i][0] : 앞에 포도주 마셨을 때
	// memo[i][1] : 앞에 포도주 안 마셨을 때

	memo[0][0] = memo[0][1] = wine[0];
	memo[1][0] = wine[0] + wine[1];
	memo[1][1] = wine[1];

	for (int i = 2; i < n; i++)
	{
		memo[i][0] = max(memo[i - 1][1] + wine[i], memo[i - 1][0]);
		memo[i][1] = max(memo[i - 2][0] + wine[i], memo[i - 2][1] + wine[i]);
	}

	return max(memo[n - 1][0], memo[n - 1][1]);
}

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

	for (int i = 0; i < n; i++)
		cin >> wine[i];

	//Top-Down
	cout << "TopDown: " << TopDown(n-1,1) << endl;
    
	//Bottom-Up
	cout << "BottomUp: "<< BottomUp(n) << endl;

	return 0;
}

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

[문제 링크]

간단한 DP문제였다. 이친수의 규칙을 살펴보면 N이 1씩 증가할때 이친수 갯수의 수열은 피보나치 수열을 이룬다.

따라서, 점화식은 DP(N) = DP(N-1) + DP(N-2) 이며 이를 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

long long memo[91];

long long TopDown(int N)
{
	if (N == 1 || N == 2) return 1;

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

	return ret = TopDown(N - 1) + TopDown(N - 2);
}

long long BottomUp(int N)
{
	memo[1] = memo[2] = 1;

	for (int i = 3; i <= N; i++)
		memo[i] = memo[i - 1] + memo[i - 2];
	
	return memo[N];
}

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

	// Top-Down
	cout << "TopDown: " << TopDown(N) << endl;
    
	// Bottom-Up
	cout << "BottomUp: "<< BottomUp(N) << endl;

	return 0;
}

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