언제나 처음처럼

[문제 링크]

간단한 다이나믹 프로그래밍 문제였다.

입력받은 물품 목록 배열에서, 현재 보고있는 물품의 무게가 준서가 버틸 수 있는 무게보다 무겁지 않을 경우 해당 물품을 가방에 담았을 때 나올 수 있는 최대 가치값과 담지 않았을 때 나올 수 있는 최대 가치값을 비교하여 더 큰 가치값을 선택하도록 구현하면 된다.

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

maxValue = max(dp(here+1, weight + itemWeight) + itemValue , dp(here+1, weight))

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

int N, K, V, W;
int memo[101][100001];

//first : W, second : V
vector<pair<int, int>> item;

int dp(int here, int weight) {
	// 기저사례 : N개의 물건을 모두 탐색했다면 재귀를 종료한다.
	if (here == N) return 0;

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

	if (weight + item[here].first <= K)
		return ret = max(dp(here + 1, weight + item[here].first) + item[here].second, dp(here + 1, weight));
	else
		return ret = dp(here + 1, weight);
}

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

	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> W >> V;
		item.push_back({ W,V });
	}

	cout << dp(0, 0) << endl;
}

[문제 링크]

 먼저 입력으로 주어지는 건설 순서대로 그래프를 만든다. 필자는 역순으로 탐색할 계획이었기 때문에 X, Y 를 입력받았으면 Y정점에서 X정점으로 가는 간선을 연결하였다.

 그래프를 연결했으면 승리를 위한 건물을 시작정점으로 하는 깊이 우선 탐색을 수행하는데, 현재 정점의 건물까지 짓는데 걸리는 시간은 (현재 정점에서 건물을 짓는 시간 + 현재 정점에서 갈 수 있는 정점의 건물을 짓는데 걸리는 시간들 중 가장 큰 값) 이므로 이를 그대로 구현해주면 된다.

 추가로 이미 계산한 정점을 다시 호출하는 경우가 많으면 시간복잡도가 커지게 되므로 동적 계획법의 메모이제이션 기법을 통해 한번 계산한 정점의 최소 시간을 저장하여 중복되는 연산을 최소화해야 한다.

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

int N, K;
vector<int> adj[1001];
vector<int> weight(1001);
int memo[1001];

int dfs(int start) {
	int& ret = memo[start];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 0; i < adj[start].size(); i++) {
		int next = adj[start][i];
		ret = max(ret, dfs(next));
	}
	ret += weight[start];

	return ret;
}

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

	while (tc--) {
		memset(memo, -1, sizeof(memo));

		for (int i = 0; i < 1001; i++)
			adj[i].clear();

		cin >> N >> K;

		for (int i = 1; i <= N; i++)
			cin >> weight[i];

		for (int i = 0; i < K; i++) {
			int a, b;
			cin >> a >> b;
			adj[b].push_back(a);
		}

		int W;
		cin >> W;
		
		cout << dfs(W) << endl;
	}

	return 0;
}

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

[문제 링크]

알고리즘 문제해결전략의 비트마스크 부분을 공부하면서 풀게된 첫 문제였다.

주어지는 입력의 범위가 20 미만으로 작기 때문에 최대 32비트 길이의 2진수를 표현할 수 있는 int형 정수의 비트연산을 통해 효율적으로 정답을 구할 수 있다.

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

const int INF = 987654321;
int N, K, M, L;
int preceding[12], classes[10];
int memo[10][1 << 12];

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

int BitCount(int taken)
{
	int cnt = 0;

	for (int i = 0; i < N; i++)
		if (taken & (1 << i))
			cnt++;

	return cnt;
}

int Topdown(int semester, int taken)
{
	if (BitCount(taken) >= K) return 0;
	if (semester >= M) return INF;

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

	ret = INF;

	int canTake = (classes[semester] & ~taken);

	for (int i = 0; i < N; i++)
		if ((canTake & (1 << i)) && (preceding[i] & taken) != preceding[i])
			canTake &= ~(1 << i);

	for (int take = canTake; take > 0; take = ((take - 1) & canTake))
	{
		if(BitCount(take) > L) continue;
		
		ret = min(ret, 1 + Topdown(semester + 1, taken | take));	
	}

	ret = min(ret, Topdown(semester+1, taken));

	return ret;
}

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

	while (test_case--)
	{
		memset(preceding, 0, sizeof(preceding));
		memset(classes, 0, sizeof(classes));
		memset(memo, 0, sizeof(memo));

		cin >> N >> K >> M >> L;

		
		for (int i = 0; i < N; i++)
		{
			int R;
			cin >> R;
			
			for (int j = 0; j < R; j++)
			{
				int num;
				cin >> num;
				preceding[i] |= (1 << num);
			}
		}

		for (int i = 0; i < M; i++)
		{
			int C;
			cin >> C;

			for (int j = 0; j < C; j++)
			{
				int num;
				cin >> num;
				
				classes[i] |= (1 << num);
			}
		}

		int result = Topdown(0, 0);

		if (result == INF)
			cout << "IMPOSSIBLE" << endl;
		else
			cout << result << endl;
	}

	return 0;
}

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

[문제 링크]

변형된 LIS 문제였다. 겉으로 보기엔 LIS 문제가 아닌듯 보이지만 가장 길게 오름차순으로 서있는 아이들을 제외한 나머지 아이들을 옮겨주면 최소한의 이동으로 줄을 세울 수 있기 때문에 결과적으로 입력받은 배열의 LIS를 구한 뒤 전체 아이들 수에서 LIS를 뺀 값이 곧 정답이 된다.

#include <iostream>
using namespace std;

int N, arr[201], memo[201];

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

int LIS(int start)
{
	if (start == N) return 1;

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

	ret = 1;

	for (int i = start + 1; i <= N; i++)
	{
		if (start == 0)
			ret = max(ret, LIS(i));
		else if (arr[start] < arr[i])
			ret = max(ret, LIS(i) + 1);
	}

	return ret;
}

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

	cout << N - LIS(0) << endl;

	return 0;
}

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

[문제 링크]

파보나치 수열 유형의 간단한 dp 문제였다. 문제에 제시된 조건대로 함수를 구현하면 된다.

#include <iostream>
using namespace std;

long long memo[67];

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

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

	return ret = Topdown(n - 1) + Topdown(n - 2) + Topdown(n - 3) + Topdown(n - 4);
}

long long Bottomup(int n)
{
	memo[0] = memo[1] = 1;
	memo[2] = 2, memo[3] = 4;

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

	return memo[n];
}

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

		cout << Topdown(n) << endl;

		cout << Bottomup(n) << endl;
	}

	return 0;
}

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

[문제 링크]

O로 표시된 칸이 없을 경우 (첫번째 칸 -> N*M번째 칸 으로 가는 경우의 수) 를 구해주면 되고,

O로 표시된 칸이 있을 경우 (첫번째 칸 -> O로 표시된 칸으로 가는 경우의 수) * (O로 표시된 칸 -> N*M번째 칸으로 가는 경우의 수) 를 구해주면 된다.

#include <iostream>
using namespace std;

int N, M, K, memo[15*15][15*15];

int Topdown(int start, int end)
{
	if (start >= end) return start == end ? 1 : 0;

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

	if(start%M != 0)
		ret += Topdown(start + 1, end);

	ret += Topdown(start + M, end);

	return ret;
}

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

	if (K == 0)
		cout << Topdown(1, N*M) << endl;
	else
		cout << Topdown(1, K) * Topdown(K, N*M) << endl;

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

현재 계산하려는 위치와, 누적한 값에 따른 올바른 등식의 개수를 2차원 dp배열에 저장하여 중복을 최소화하였다.

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

int N, arr[101];
long long memo[101][21];

long long Topdown(int here, int sum)
{
	if (sum < 0 || sum > 20) return 0;
	if (here == N) return sum == arr[N] ? 1 : 0;

	long long& ret = memo[here][sum];
	if (ret != -1) return ret;

	ret = 0;

	ret += Topdown(here + 1, sum + arr[here]);
	ret += Topdown(here + 1, sum - arr[here]);

	return ret;
}

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

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

	cout << Topdown(2, arr[1]) << endl;

	return 0;
}

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

[문제 링크]

먼저 N x M 행렬과 M x K 행렬을 곱하면 N x K 행렬이 만들어진다는 것을 알고있어야 한다.

행렬 A, B, C, D가 있을 때 만들 수 있는 곱셈 순서는 다음과 같다.

(A) * (BCD),

(AB) * (CD),

(ABC) * (D)

2개로 묶인 행렬은 바로 곱해주면 되지만 3개 이상으로 묶인 행렬은 그 최솟값을 구하기 위해 다시 곱셈 순서를 나눠줘야 한다.

예를 들어 (A) * (BCD) 에서 (BCD)를 (B) * (CD) 와 (BC) * (D) 두가지로 나눌 수 있다.

위 과정을 재귀적으로 반복하는 함수를 구현하면 원하는 결과를 얻을 수 있다.

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

const int INF = 987654321;
int proc[501][2], memo[501][501];

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

int Topdown(int start, int end)
{
	if (start == end) return 0;
	if (start + 1 == end) return proc[start][0] * proc[start][1] * proc[end][1];

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

	ret = INF;

	for (int i = start; i < end; i++)
		ret = min(ret, Topdown(start, i) + Topdown(i + 1, end) + proc[start][0] * proc[i + 1][0] * proc[end][1]);

	return ret;
}

int Bottomup(int start, int end)
{
	for(int i = 1; i <= end; i++)
		for (int j = i - 1; j > 0; j--)
		{
			memo[j][i] = INF;

			for(int k=j; k<i; k++)
				memo[j][i] = min(memo[j][i], memo[j][k] + memo[k + 1][i] + proc[j][0] * proc[k + 1][0] * proc[i][1]);
		}

	return memo[start][end];
}

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

	cout << Topdown(1, N) << endl;

	cout << Bottomup(1, N) << endl;

	return 0;
}

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