언제나 처음처럼

[문제 링크]

알고스팟의 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

[문제 링크]

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