언제나 처음처럼

[문제 링크]

간단한 문제였다. 모든 정점을 시작점으로 bfs나 dfs를 수행하여 그중 최댓값을 찾으면 정답을 받을 수 있다.

하지만 이 문제를 더 빠르게 풀 수 있는 방법이 존재한다고 한다. 

뿌리노드인 1번 노드에서 가장 멀리 떨어진 정점을 찾고, 그 정점을 시작점으로 하여 가장 멀리 떨어진 정점까지의 거리가 곧 트리의 지름이 된다. 따라서 탐색을 2번 수행하므로 O(n) 시간에 문제를 해결할 수 있다.

자세한 증명은 구사과님의 블로그에 설명되어 있다.

https://koosaga.com/14

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

int N;
vector<vector<pair<int, int>>> adj(10001);
bool visited[10001];

pair<int, int> bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = true;

	pair<int, int> ret = { 0,0 };
	while (!q.empty()) {
		int here = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (ret.second < cost)
			ret = { here, cost };

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = cost + adj[here][i].second;

			if (!visited[there]) {
				visited[there] = true;
				q.push({ there, nextCost });
			}
		}
	}

	return ret;
}


int main(void) {
	cin >> N;
	
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	// find maximum node
	int maxNode = bfs(1).first;

	memset(visited, false, sizeof(visited));

	// get diameter
	int diameter = bfs(maxNode).second;

	cout << diameter << endl;

	return 0;
}

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

[문제 링크]

그리디 알고리즘과 DFS가 섞인 문제였다.

파이프를 연결할 수 있는 경우는 오른쪽 대각선 위, 오른쪽 옆, 오른쪽 대각선 아래 세가지가 있고, 파이프가 서로 겹치거나 엇갈리면 안되기 때문에 대각선 위 -> 옆 -> 아래 순으로 탐색 하는 것이 항상 최적해를 보장한다.

성공적으로 파이프를 연결했다면 1을 반환하고, 파이프가 연결되었기 때문에 다른 경우는 고려할 필요 없이 탐색을 종료한다.

한번 방문했던 좌표는 그전에 이미 시도해본 좌표이기 때문에 고려해줄 필요가 없다. 따라서 2차원 visit 배열을 선언하여 방문여부를 체크했다.

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

string board[10000];
bool visit[10000][500];
int dy[3] = { -1, 0, 1 };

int Greedy(int startY, int startX, int R, int C)
{
	if (startX == C - 1) return 1;

	int ret = 0;

	for (int i = 0; i < 3; i++)
	{
		int nextY = startY + dy[i];
		int nextX = startX + 1;

		if (nextY >= 0 && nextY < R && board[nextY][nextX] != 'x' && !visit[nextY][nextX])
		{
			visit[nextY][nextX] = true;
			ret = Greedy(nextY, nextX, R, C);
		}

		if (ret == 1)
			break;
	}

	return ret;
}

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

	int R, C;
	cin >> R >> C;

	for (int i = 0; i < R; i++)
		cin >> board[i];

	int cnt = 0;
	for (int i = 0; i < R; i++)
		cnt += Greedy(i, 0, R, C);

	cout << cnt << endl;

	return 0;
}

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

[문제 링크]

입력의 크기가 크지 않음에도 불구하고 동적계획법으로 접근했다가 풀이까지 오래걸린 문제였다.

경우의 수는 두가지로 나뉜다.

1. 현재 숫자와 다음 숫자 사이를 괄호로 묶었을 때 최댓값

2. 다음 숫자와 그 다음 숫자 사이를 괄호로 묶었을 때 최댓값

ex) 1 + 2 * 3 -> (1 + 2) * 3 || 1 + (2 * 3)

위 경우의 수를 모두 고려하여 최댓값을 찾아주면 원하는 결과를 얻을 수 있다.

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

const int INF = 987654321;
string str;
int N, result = -INF;

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

int Calc(int first, int second, char oper)
{
	switch (oper)
	{
	case '+':
		return first + second;

	case '-':
		return first - second;

	case '*':
		return first * second;
	}
}

void Solution(int here, int sum)
{
	if (here > N - 1)
	{
		result = max(result, sum);
		return;
	}
	
	int firNum = sum;
	int secNum = str[here + 1] - '0';
	
	Solution(here + 2, Calc(firNum, secNum, str[here]));

	if (here + 2 < N)
	{
		int thirdNum = str[here + 3] - '0';
		Solution(here + 4, Calc(firNum, Calc(secNum, thirdNum, str[here + 2]), str[here]));
	}
}

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

	Solution(1, str[0]-'0');

	cout << result << endl;

	return 0;
}

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

[문제 링크]

탐욕법과 DFS를 사용하여 풀 수 있었다.

부등호를 만족하는 최댓값을 구하기 위해서는 가장 큰 숫자(9)부터 가장 작은 숫자(0) 순으로 조건을 만족하는 숫자를 선택해나가야 한다.

부등호를 만족하는 최솟값을 구하기 위해서는 최댓값과 반대로 가장 작은 숫자(0)부터 가장 큰 숫자(9) 순으로 조건을 만족하는 숫자를 선택해 나가면 된다.

최적의 숫자를 선택한 뒤 재귀호출한 결과가 등식을 만족했다면 다른 숫자들은 진행할 필요가 없기 때문에 결과를 반환하도록 구현하였다.

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

char arr[10];
bool check[10];

string Greedy(int here, int last, int k, bool ver)
{
	if (here == k) return "";

	string result;

	if (ver)
	{
		for (int i = 9; i >= 0; i--)
		{
			if (result.length() == k - here) 
				return result;

			if (here == -1)
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '>' && last > i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '<' && last < i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
		}
	}
	
	else
	{
		for (int i = 0; i <= 9; i++)
		{
			if (result.length() == k - here) 
				return result;

			if (here == -1)
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '>' && last > i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
			else if (arr[here] == '<' && last < i && !check[i])
			{
				check[i] = true;
				result = (char)(i + '0') + Greedy(here + 1, i, k, ver);
				check[i] = false;
			}
		}
	}
    
	return result;
}

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

	for (int i = 0; i < k; i++)
		cin >> arr[i];

	cout << Greedy(-1, 0, k, 1) << endl;
	cout << Greedy(-1, 0, k, 0) << endl;

	return 0;
}

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