TIL day 73

1. 코딩테스트

---

최근에 계속 프로그래머스 문제를 풀다 백준으로 넘어왔습니다.

백준 class 4문제를 풀고있습니다.

 

오늘은 boj 2096 내려가기 문제를 풀었습니다.

https://www.acmicpc.net/problem/2096

 

처음에 이 문제를 보고 BFS를 떠올렸습니다.  (아니면 DP)

아마도 답은 맞지 않을까 싶은데, 메모리 초과가 발생해서 다른 방법을 찾게 되었습니다. (문제의 제한 4mb)

• 배열의 크기를 계산해보면, 100,002 * 3 * 4byte = 1,200,024 byte
• mb로 환산하면 1024로 두번 나누면 대략 1.14mb 정도 크기가 나온다.
• 질문 게시판을 보다보니 단순히 배열의 사이즈 뿐만 아니라 다른 사용량(cin, cout 버퍼 등)도 있기 때문에, 넉넉하게 생각해서 메모리를 잡아야 한다고 한다.

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

int n;
int board[100'002][3];
int vis[100'002][3];
int dx[3] = { 1,1,1 };
int dy[3] = { 0,1,-1 };
int maxAns = INT_MIN;
int minAns = INT_MAX;

void bfs(pair<int,int> st)
{
	for (int i = 0; i < n; ++i)
		fill(vis[i], vis[i] + 3, -1);

	queue<pair<int, int>>q;
	q.push({ st.first, st.second });
	vis[st.first][st.second] = board[st.first][st.second];

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		for (int dir = 0; dir < 3; ++dir)
		{
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];

			if (abs(cur.second - ny) >= 2)
				continue;
			if (nx < 0 || nx >= n || ny < 0 || ny >= 3)
				continue;
			if (vis[nx][ny] != -1)
				continue;
			q.push({ nx,ny });
			vis[nx][ny] = vis[cur.first][cur.second] + board[nx][ny];
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> board[i][0] >> board[i][1] >> board[i][2];
	}

	bfs({ 0, 0 });

	maxAns = max(maxAns, *max_element(vis[n - 1], vis[n - 1] + 3));
	minAns = min(minAns, *min_element(vis[n - 1], vis[n - 1] + 3));

	bfs({ 0, 1 });

	maxAns = max(maxAns, *max_element(vis[n - 1], vis[n - 1] + 3));
	minAns = min(minAns, *min_element(vis[n - 1], vis[n - 1] + 3));

	bfs({ 0, 2 });

	maxAns = max(maxAns, *max_element(vis[n - 1], vis[n - 1] + 3));
	minAns = min(minAns, *min_element(vis[n - 1], vis[n - 1] + 3));

	cout << maxAns << " " << minAns;
}

그래서 다음으로 들었던 생각인 DP로 전환해서 최대한 배열의 크기를 아껴서 아래와 같이 구성하여 해결하였습니다.

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int board[100'002][3];

int dp_max[3];
int dp_min[3];
int max_temp[3];
int min_temp[3];

int n;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> board[i][0] >> board[i][1] >> board[i][2];
	}

	dp_max[0] = board[0][0];
	dp_max[1] = board[0][1];
	dp_max[2] = board[0][2];

	dp_min[0] = board[0][0];
	dp_min[1] = board[0][1];
	dp_min[2] = board[0][2];

	for (int i = 1; i < n; ++i)
	{
		//하나 전 기록
		for (int j = 0; j < 3; ++j)
			max_temp[j] = dp_max[j];

		for (int j = 0; j < 3; ++j)
			min_temp[j] = dp_min[j];

		dp_max[0] = max(max_temp[0], max_temp[1]) + board[i][0];
		dp_max[1] = max(max(max_temp[0], max_temp[1]),max_temp[2]) + board[i][1];
		dp_max[2] = max(max_temp[2], max_temp[1]) + board[i][2];

		dp_min[0] = min(min_temp[0], min_temp[1]) + board[i][0];
		dp_min[1] = min(min(min_temp[0], min_temp[1]), min_temp[2]) + board[i][1];
		dp_min[2] = min(min_temp[2], min_temp[1]) + board[i][2];
	}

	cout << *max_element(dp_max, dp_max + 3) << " " << *min_element(dp_min, dp_min + 3);
}

 

 

2. 언리얼

---

추가적으로 데디케이티드 서버 관련 공부를 하고

https://gbleem.tistory.com/148

Unreal Engine - 데디케이티드 서버 2

 

팀 프로젝트를 진행하였습니다.

• 해금 시스템과 시스템을 연동
• 각 캐릭터 선택시 해당 캐릭터로 플레이 가능
• 맵 선택시 해당 맵에 맞는 캐릭터 스폰