언제나 처음처럼

[문제 링크]

현재 좌표에서 동서남북 방향을 깊이 우선 탐색 함으로써 한 단지에 속하는 좌표를 방문하고 집의 개수를 저장하였다.

그리고 한번 깊이 우선 탐색을 했는데 방문하지 않은 좌표가 존재한다면 또다른 단지가 존재하는 것이므로 그 좌표를 시작으로 다시 깊이 우선 탐색 하는 것을 반복하도록 구현하였다.

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

int N;
vector<string> board(25);
bool visited[25][25];

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

struct Pos 
{
	int y;
	int x;
};

int dfs(Pos here)
{
	int ret = 1;

	for (int i = 0; i < 4; i++)
	{
		int ny = here.y + dy[i];
		int nx = here.x + dx[i];

		if (ny >= 0 && ny < N && nx >= 0 && nx < N)
			if (!visited[ny][nx] && board[ny][nx] == '1')
			{
				visited[ny][nx] = true;
				ret += dfs({ ny, nx });
			}
	}

	return ret;
}

int main(void) 
{
	cin >> N;

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

	vector<int> result;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			if (!visited[i][j] && board[i][j] == '1')
			{
				visited[i][j] = true;
				Pos start = { i,j };
				result.push_back(dfs(start));
			}

	sort(result.begin(), result.end());

	cout << result.size() << endl;
	
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << endl;

	return 0;
}

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

[문제 링크]

(0, 0) 위치에서 시작하여 동 서 남 북 방향을 확인하면서 이동 가능한 방향에 아직 방문하지 않고 값이 '1'인 위치가 있다면 queue에 추가해주는 너비 우선 탐색으로 구현하였다.

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

int N, M;
vector<string> board(100);
bool discovered[100][100];

int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

struct Point
{
	int y;
	int x;

	Point(int _y = 0, int _x = 0) : y(_y), x(_x) { }

	bool operator== (const Point& rhs) {
		if (y == rhs.y && x == rhs.x) return true;
		return false;
	}
};

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

	Point target = { N - 1, M - 1 };

	while (!q.empty()) {
		Point here = q.front().first;
		int move = q.front().second;

		q.pop();

		if (target == here)
			return move;

		for (int i = 0; i < 4; i++)
		{
			int ny = here.y + dy[i];
			int nx = here.x + dx[i];

			if (ny < N && ny >= 0 && nx < M && nx >= 0)
				if (!discovered[ny][nx] && board[ny][nx] == '1') {
					discovered[ny][nx] = true;
					q.push({ { ny, nx }, move + 1 });
				}
		}
	}

	return -1;
}

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

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

	cout << bfs() << endl;

	return 0;
}

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

[문제 링크]

트라이 자료구조를 사용하여 문자열을 빠르게 검색하는 문제인데 여러가지 고려해줘야할 것이 많아서 어려웠던 문제였다.

먼저 trie 객체에 count 변수를 추가하고 words 문자열이 각 노드를 방문하는 횟수를 카운팅함으로써 해당 위치에서 '?' 를 만났을 경우 가능한 가지수를 탐색하지 않고 바로 반환받을 수 있도록 하였다.

"????o" 와 같이 '?'가 접두사로 등장하는 경우에는 queries를 역순으로 탐색 해줘야하기 때문에 words를 뒤집은 문자열을 가지고 새로운 trie를 한개 더 만들었다.

마지막으로 '?'까지 문자열은 일치하지만 길이가 다른 경우를 걸러주기 위해 trie 객체를 words와 queries의 최대 길이인 10000만큼의 크기를 가진 배열로 선언하여 길이에 따라 다른 트라이에 담아주었다.

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

const int ALPHABETS = 26;

int toNumber(char ch) 
{ 
	if (ch == '?') return ALPHABETS;
	
	return ch - 'a'; 
}

struct TrieNode
{
	TrieNode* children[ALPHABETS];
	int count;
	bool terminal;

	TrieNode() : terminal(false), count(1)
	{
		memset(children, 0, sizeof(children));
	}
	~TrieNode()
	{
		for (int i = 0; i < ALPHABETS; i++)
			if (children[i]) delete children[i];
	}

	void insert(string& key, int here)
	{
		if (here == key.size()) terminal = true;
		else
		{
			int next = toNumber(key[here]);

			//자식 노드가 없다면 생성
			if (children[next] == NULL)
				children[next] = new TrieNode();
			else
				children[next]->count++;

			children[next]->insert(key, here + 1);
		}
	}

	int find(string& key, int here)
	{
		if (here == key.size()) return this->terminal ? 1 : 0;

		int next = toNumber(key[here]);

		int cnt = 0;

		if (next == ALPHABETS)
		{
			for (int i = 0; i < ALPHABETS; i++)
				if (children[i] != NULL)
					cnt += children[i]->count;
		}
		else
		{
			if (children[next] == NULL) return 0;
			else
			{
				cnt = children[next]->find(key, here + 1);
			}
		}

		return cnt;
	}
};

vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;

	vector<TrieNode> word(10001);
	vector<TrieNode> reword(10001);

	for (int i = 0; i < words.size(); i++)
	{
		int len = words[i].size();

		word[len].insert(words[i], 0);

		reverse(words[i].begin(), words[i].end());
		
		reword[len].insert(words[i], 0);
	}

	for (int i = 0; i < queries.size(); i++)
	{
		int len = queries[i].size();

		if(queries[i][0] != '?')
			answer.push_back(word[len].find(queries[i], 0));
		else
		{
			reverse(queries[i].begin(), queries[i].end());
			answer.push_back(reword[len].find(queries[i], 0));
		}
	}
	return answer;
}

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

[문제 링크]

이 문제와 같이 많은 양의 문자열을 검색하는 요구하는 문제들은 트라이 자료구조를 활용하면 효율적으로 해결할 수 있다.

트라이 자료구조는 알고리즘 문제해결 전략에서 구현한 것과 똑같이 구현하였다.

사전에 포함된 단어들을 출현 빈도에 따라 내림차순으로 정렬하고 출현 빈도가 같을 경우 오름차순으로 정렬하기 위해 출현 빈도 freq에 -를 붙여서 배열에 담았다.

스페이스바를 누르는 횟수까지 포함시켜야 하므로 cnt를 M - 1 로 초기화 하였다.

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

const int ALPHABETS = 26;

int toNumber(char ch) 
{ 
	return ch - 'A'; 
}

struct TrieNode
{
	TrieNode* children[ALPHABETS];
	int first;
	int terminal;

	TrieNode() : terminal(-1), first(-1)
	{
		memset(children, 0, sizeof(children));
	}
	~TrieNode()
	{
		for (int i = 0; i < ALPHABETS; i++)
			if (children[i]) delete children[i];
	}

	void insert(string& key, int here, int id)
	{
		if (first == -1) 
			first = id;

		if (here == key.size())
			terminal = id;
		else
		{
			int next = toNumber(key[here]);

			//자식 노드가 없다면 생성
			if (children[next] == NULL)
				children[next] = new TrieNode();

			children[next]->insert(key, here + 1, id);
		}
	}

	int type(string& key, int here, int id)
	{
		if (here == key.size()) return 0;

		if (first == id) return 1;

		int next = toNumber(key[here]);

		return 1 + children[next]->type(key, here + 1, id);
	}

	TrieNode* find(string& key, int here)
	{
		if (here == key.size()) return this;
		
		int next = toNumber(key[here]);

		if (children[next] == NULL) return NULL;
		return children[next]->find(key, here + 1);
	}
};

int countKeys(TrieNode& trie, string word)
{
	TrieNode* node = trie.find(word, 0);

	if (node == NULL || node->terminal == -1)
		return word.size();

	return trie.type(word, 0, node->terminal);
}

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

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, M;
		cin >> N >> M;

		
		vector<pair<int, string>> input;

		for (int i = 0; i < N; i++)
		{
			string words;
			int freq;
			cin >> words >> freq;
			input.push_back({ -freq, words });
		}

		sort(input.begin(), input.end());

		TrieNode word;
		
		for(int i=0; i<input.size(); i++)
			word.insert(input[i].second, 0, i);
		
		word.first = -1;

		int cnt = M - 1;

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

			cnt += countKeys(word, words);
		}

		cout << cnt << endl;
	}

	return 0;
}

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

[문제 링크]

세그먼트 트리라고 불리는 구간 트리를 활용하면 쉽게 풀 수 있는 문제였다.

구간의 최솟값을 저장하는 구간 트리는 알고리즘 문제해결 전략에 나와있는대로 구현하였고 구간의 최댓값을 구하기 위해 배열에 -1을 곱한 뒤 구간 트리를 한개 더 만들었다.

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

const int INTMAX = numeric_limits<int>::max();

void getMinus(int& a)
{
	a *= -1;
}

class RMQ {
	int n;
	vector<int> rangeMin;

	int init(const vector<int>& array, int left, int right, int node)
	{
		if (left == right)
			return rangeMin[node] = array[left];
		int mid = (left + right) / 2;
		int leftMin = init(array, left, mid, node * 2);
		int rightMin = init(array, mid + 1, right, node * 2 + 1);

		return rangeMin[node] = min(leftMin, rightMin);
	}

	int query(int left, int right, int node, int nodeLeft, int nodeRight)
	{
		if (right < nodeLeft || nodeRight < left) return INTMAX;
		if (left <= nodeLeft && nodeRight <= right) return rangeMin[node];

		int mid = (nodeLeft + nodeRight) / 2;
		return min(query(left, right, node * 2, nodeLeft, mid),
			query(left, right, node * 2 + 1, mid + 1, nodeRight));
	}

	int update(int index, int newValue, int node, int nodeLeft, int nodeRight)
	{
		if (index < nodeLeft || nodeRight < index) return rangeMin[node];
		if (nodeLeft == nodeRight) return rangeMin[node] = newValue;

		int mid = (nodeLeft + nodeRight) / 2;
		
		return rangeMin[node] = min(update(index, newValue, node * 2, nodeLeft, mid),
			update(index, newValue, node * 2 + 1, mid + 1, nodeRight));
	}

public:
	RMQ(const vector<int>& array)
	{
		n = array.size();
		rangeMin.resize(n * 4);
		init(array, 0, n - 1, 1);
	}

	int query(int left, int right)
	{
		return query(left, right, 1, 0, n - 1);
	}

	int update(int index, int newValue)
	{
		return update(index, newValue, 1, 0, n - 1);
	}
};

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

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, Q;
		cin >> N >> Q;

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

		RMQ boardMin(board);

		for_each(board.begin(), board.end(), getMinus);

		RMQ boardMax(board);

		for (int i = 0; i < Q; i++)
		{
			int first, last;
			cin >> first >> last;


			cout << -boardMax.query(first, last) - boardMin.query(first, last) << endl;
		}
	}
}

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

[문제 링크]

알고리즘 문제해결 전략의 이진검색 트리를 공부하면서 풀게된 문제였다.

예전에 풀었던 백준: 신입사원 문제 와 거의 같은 유형의 문제라고 생각한다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

bool isDominated(map<int, int>& data, int p, int q)
{
	map<int, int>::iterator iter = data.lower_bound(p);

	if (iter == data.end()) return false;

	return iter->second > q;
}

void removeDominated(map<int, int>& data, int p, int q)
{
	map<int, int>::iterator iter = data.lower_bound(p);

	if (iter == data.begin()) return;
	iter--;

	while (1)
	{
		if (iter->second > q) return;

		if (iter == data.begin())
		{
			data.erase(iter); 
			break;
		}
		else
		{
			map<int, int>::iterator temp = iter;
			temp--;
			data.erase(iter);
			iter = temp;
		}
	}
}

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

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N;
		cin >> N;

		int cnt = 0;
		map<int, int> coords;

		for (int i = 0; i < N; i++)
		{
			int p, q;
			cin >> p >> q;

			if (isDominated(coords, p, q))
				cnt += coords.size();
			else
			{
				removeDominated(coords, p, q);
				coords[p] = q;
				cnt += coords.size();
			}
		}

		cout << cnt << endl;
	}

	return 0;
}

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

[문제 링크]

입력값이 작음에도 불구하고 완전탐색이 아닌 그리디 알고리즘으로 풀어볼려고 접근하다가 고생만 잔뜩 했다.

그냥 무난하게 모든 경우에 대해서 전부 시도해보면 되는 문제였다.

우선 거리 계산을 편하게 하기 위해 입력으로 주어지는 weak 배열의 각 지점 사이의 거리 차이를 계산해서 weakDist 배열에 저장하였다.

그다음 next_permutation() 함수를 통해 dist 배열로 만들 수 있는 모든 조합에 대해서 외벽 점검을 돌려 가장 최소 인원이 투입되는 경우를 구하면 된다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 987654321;

int solution(int n, vector<int> weak, vector<int> dist) {
	int answer = INF;

	vector<int> weakDist;

	for (int i = 0; i < weak.size(); i++)
	{
		if (i == weak.size() - 1)
			weakDist.push_back(n - (weak[i] - weak[0]));
		else
			weakDist.push_back(weak[i + 1] - weak[i]);
	}

	do
	{
		for (int i = 0; i < weakDist.size(); i++)
		{
			int pick = 0, pickDist = dist[0];

			int start = i;
			int end = start != 0 ? start - 1 : weakDist.size() - 1;

			while (start != end)
			{
				if (pickDist >= weakDist[start])
				{
					pickDist -= weakDist[start];
				}
				else
				{
					if (pick + 1 == dist.size()) break;

					pickDist = dist[++pick];
				}

				start = start + 1 == weakDist.size() ? 0 : start + 1;
			}

			if (start != end) pick = INF;

			answer = min(answer, pick + 1);
		}
	} while (next_permutation(dist.begin(), dist.end()));


	return answer == INF ? -1 : answer;
}

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

[문제 링크]

문제 접근에 따라 구현 난이도가 극심하게 달라질 수도 있다는 것을 깨닫게 해준 문제였다.

필자는 크기가 (n+1)X(n+1)인 board 배열을 하나 만든 다음 그 위에다 구조물을 설치하고 제거하는 식으로 구현하려했는데, 이 방법으로 구현할 경우 한 좌표에 기둥과 보가 설치되어 있는 경우를 추가로 고려해줘야하기 때문에 코드도 엄청 길어지고 디버깅하기도 쉽지 않아 한참을 고생했다.

단순하게 2차원 bool 배열을 2개 만들고 기둥이 설치된 정보가 담긴 배열과 보가 설치된 정보가 담긴 배열로 나눠서 관리하면 훨씬 코드도 간결하고 구현도 쉽게 할 수 있었다.

#include <string>
#include <vector>

using namespace std;

bool pillar[101][101];
bool bo[101][101];

bool check_pillar(int y, int x, int n)
{
	if (y == 0) return true;
	if (pillar[y - 1][x]) return true;
	if (x > 0 && bo[y][x - 1]) return true;
	if (bo[y][x]) return true;

	return false;
}

bool check_bo(int y, int x, int n)
{
	if (pillar[y - 1][x]) return true;
	if (x < n && pillar[y - 1][x + 1]) return true;
	if (x > 0 && (bo[y][x-1] && bo[y][x+1])) return true;

	return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) 
{	
	for (int i = 0; i < build_frame.size(); i++)
	{
		int xPos = build_frame[i][0];
		int yPos = build_frame[i][1];
		int isStruct = build_frame[i][2];
		int isWork = build_frame[i][3];

		if (isStruct == 0) // 기둥
		{
			if (isWork == 1) // 설치
			{
				if (check_pillar(yPos, xPos, n))
					pillar[yPos][xPos] = true;
			}

			else // 삭제
			{
				pillar[yPos][xPos] = false;

				if (yPos < n && pillar[yPos+1][xPos] && !check_pillar(yPos + 1, xPos, n))
					pillar[yPos][xPos] = true;

				else if (xPos < n && bo[yPos+1][xPos] && !check_bo(yPos + 1, xPos, n))
					pillar[yPos][xPos] = true;

				else if (xPos > 0 && bo[yPos+1][xPos-1] && !check_bo(yPos + 1, xPos - 1, n))
					pillar[yPos][xPos] = true;
			}
		}
		else // 보
		{
			if (isWork == 1) // 설치
			{
				if (check_bo(yPos, xPos, n))
					bo[yPos][xPos] = true;
			}

			else // 삭제
			{
				bo[yPos][xPos] = false;

				if (yPos < n && pillar[yPos][xPos] && !check_pillar(yPos, xPos, n))
					bo[yPos][xPos] = true;

				else if (yPos < n && xPos < n && pillar[yPos][xPos+1] && !check_pillar(yPos, xPos + 1, n))
					bo[yPos][xPos] = true;

				else if (xPos > 0 && bo[yPos][xPos-1] && !check_bo(yPos, xPos - 1, n))
					bo[yPos][xPos] = true;

				else if (xPos < n && bo[yPos][xPos+1] && !check_bo(yPos, xPos + 1, n))
					bo[yPos][xPos] = true;
			}
		}
	}

	vector<vector<int>> answer;
	
	for(int x = 0; x <= n; x++)
		for (int y = 0; y <= n; y++)
		{
			if (pillar[y][x])
				answer.push_back({ x,y,0 });

			if (bo[y][x])
				answer.push_back({ x,y,1 });
		}

	return answer;
}

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