언제나 처음처럼

[문제 링크]

이 문제는 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

[문제 링크]

https://onlytrying.tistory.com/61

알고스팟의 삼각형 위 최대경로 문제와 유사한 문제였다.

TopDown으로 푸는 경우 현재 위치(Y, X)에서 다음 위치로 가는 경우가 (Y-1, X-1)과 (Y-1, X)만 존재하기 때문에 (Y-1, X-1) 이 가질 수 있는 최대값과 (Y-1, X) 이 가질 수 있는 최대값을 비교하여 더 큰 경우를 선택하면 된다.

함수를 재귀 호출하는 방법으로 이를 구현할 수 있으며, 기저사례로 X가 범위에 속하지 않을 경우 0을 반환하고, Y가 0일 때 즉, 삼각형의 꼭대기에 도달했을 때 그 위치의 정수값을 반환하도록 하였다.

BottomUp으로 푸는 경우 현재 위치(Y, X)가 가질 수 있는 최대값은 (Y-1, X-1)의 최대값과 (Y-1, X)의 최대값 중 더 큰 값에 현재 위치(Y, X)의 정수값을 더해줌으로써 구할 수 있다. 

TopDown과 마찬가지로 X가 범위에 속하지 않는 경우 최대값이 존재할 수 없기 때문에 계산하지 않도록 구현하였다.

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

int n, tri[501][501], memo[501][501];

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

int TopDown(int hereY, int hereX)
{
	if (hereX < 0 || hereX > hereY) return 0;
	if (hereY == 0) return tri[hereY][hereX];

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

	ret = 0;

	int val = tri[hereY][hereX];
	return ret = max(TopDown(hereY - 1, hereX - 1), TopDown(hereY - 1, hereX)) + val;
}

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

	for(int i = 1; i<n; i++)
		for (int j = 0; j < i + 1; j++)
		{
			int val = tri[i][j];
			if (j == 0)
				memo[i][j] = memo[i - 1][j] + val;
			else
				memo[i][j] = max(memo[i - 1][j - 1], memo[i - 1][j]) + val;
		}

	int res = -1;
	for (int i = 0; i < n; i++)
		res = max(res, memo[n - 1][i]);

	return res;
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < i + 1; j++)
			cin >> tri[i][j];

	// Top-Down
	int res = -1;
	for (int i = 0; i < n; i++)
		res = max(res, TopDown(n - 1, i));
	cout << "TopDown: " << res << endl;
	
	// Bottom-Up
	cout << "BottomUp: " << BottomUp(n) << endl;

	return 0;
}

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

[문제 링크]

TopDown 으로 푸는 경우 위에 계단을 밟았는지 안밟았는지 여부에 따라 다른 점화식으로 동작하도록 하였고, 위에 계단을 밟은 경우와 안밟은 경우의 최댓값을 다르게 저장하기 위해 2차원 배열로 메모이제이션 하였다.

기저사례로 현재 위치가 계단 범위를 벗어날 경우 값이 없으므로 0을 반환해주었다.

BottomUp 으로 푸는 경우 마찬가지로 아래 계단을 밟았을 경우와 안밟았을 경우의 값이 다르기 때문에 2차원 배열로 메모이제이션 하였다. 첫번째 계단과 두번째 계단을 미리 계산하여 결과값을 메모이제이션한 다음, 미리 계산한 값을 이용하여 세번째 계단부터 N번째 계단까지 계산하는 형태로 구현하였다.

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

int N, stairs[301], memoTop[301][2], memoBot[301][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; // 기저사례: 계단을 벗어났을 경우 0 반환

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

	if (check)
		ret = max(TopDown(here - 1, 0) + stairs[here], TopDown(here - 2, 1) + stairs[here]);
	else
		ret = TopDown(here - 2, 1) + stairs[here];

	return ret;
}

int BottomUp(int N)
{
	// memoBot[i][0] : 아래 계단 밟은 경우
	// memoBot[i][1] : 밟지 않은 경우
	memoBot[0][0] = memoBot[0][1] = stairs[0];
	memoBot[1][1] = stairs[1];
	memoBot[1][0] = stairs[0] + stairs[1];
    
	for (int i = 2; i < N; i++)
	{
		memoBot[i][1] = max(memoBot[i - 2][0], memoBot[i - 2][1]) + stairs[i];
		memoBot[i][0] = memoBot[i - 1][1] + stairs[i];
	}
    
	return max(memoBot[N - 1][0], memoBot[N - 1][1]);
}

int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> stairs[i];

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

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/61

알고스팟의 삼각형 위 최대경로 문제와 유사한 문제라고 생각한다.

N번째 집이 어떤 색으로 칠해진다면 N+1번째 집은 N번째 집이 칠해진 색깔을 제외한 색깔로 칠해져야 한다는 사실과 

N+1번째 집이 칠해진 색깔에 따라 N+2번째 집이 칠해지는 색깔도 정해진다는 사실을 생각한다면 어렵지 않게 풀이법을 떠올릴 수 있을 것이다.

동적계획법 문제는 Top-Down과 Bottom-Up으로 알고리즘을 구현할 수 있는데, 각각의 방식마다 장점과 단점이 존재한다.

필자는 두 가지 방식을 연습하기 위하여 Top-Down과 Bottom-Up 각각 구현하였다.

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

const int INF = 987654321;
int house[1001][3], memo[1001][3];

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

int TopDown(int here, int color)
{
	if (here == 0) return house[here][color];

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

	ret = INF;

	for (int i = 0; i < 3; i++)
	{
		if (i == color) continue;
		ret = min(ret, TopDown(here - 1, i) + house[here][color]);
	}

	return ret;
}

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

	for (int i = 1; i < N; i++)
		for (int j = 0; j < 3; j++)
		{
			int cost = house[i][j];
			if (j == 0) 
				memo[i][j] = min(cost + memo[i - 1][1], cost + memo[i - 1][2]);
			else if (j == 1) 
				memo[i][j] = min(cost + memo[i - 1][0], cost + memo[i - 1][2]);
			else 
				memo[i][j] = min(cost + memo[i - 1][0], cost + memo[i - 1][1]);
		}

	return min(memo[N - 1][0], min(memo[N - 1][1], memo[N - 1][2]));
}
int main(void)
{
	memset(memo, -1, sizeof(memo));

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			cin >> house[i][j];

	// Top-Down
	int res = INF;
	for (int i = 0; i < 3; i++)
		res = min(res, TopDown(N - 1, i));		
	cout << res << endl;
	
	// Bottom-Up
	cout << BottomUp(N) << endl;

	return 0;
}

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

[문제 링크]

간단한 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