Mohand's code block

링크

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

해설

최소 신장 트리 문제입니다.

그런데 다른 문제들과는 조금 다르게 모든 노드들이 다 연결되어있는 상태라

기존의 방법대로 kruskal 알고리즘을 적용시키면 약 N^2 개의 공간이 필요해서 메모리 초과가 됩니다.

이 문제의 특징은 x y z 축의 값중 가장 작은 값이 최소 비용이 된다는 것입니다.

즉 kruskal 알고리즘을 적용할 때 모든 노드를 볼 필요가 없고 근처에 있는 후보가 될만한 것들 만 골라서

적용시켜야 합니다.

이 근처에 있는 후보들을 뽑는 방법이 각 축에 대해 정렬하게되면 바로 옆에 있는 노드들이 후보가 되게 됩니다.

각 축에 대해 후보들을 모두 뽑아서 kruskal 알고리즘을 적용하면 됩니다.

아래 코드에 모두 구현되어있습니다.

코드

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

struct edge {
	int len, a, b;
};

bool operator < (edge& _a, edge& _b) {
	return _a.len < _b.len;
}

struct xyz {
	int x, y, z, idx;
};

bool comp_x(xyz _a, xyz _b) {
	return _a.x < _b.x;
}

bool comp_y(xyz _a, xyz _b) {
	return _a.y < _b.y;
}

bool comp_z(xyz _a, xyz _b) {
	return _a.z < _b.z;
}

int N, DIST = 0, parent[100000], set_size[100000];
xyz TABLE[100000];

int abs(int _a) {
	if (_a < 0)
		return -_a;
	return _a;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> TABLE[i].x >> TABLE[i].y >> TABLE[i].z;
		TABLE[i].idx = i;
		parent[i] = i;
		set_size[i] = 1;
	}

	vector<edge> list;
	list.reserve(N * 3);

	sort(TABLE, TABLE + N, comp_x);
	for (int i = 1; i < N; ++i)
		list.push_back({ abs(TABLE[i].x - TABLE[i-1].x), TABLE[i].idx, TABLE[i - 1].idx });
	
	sort(TABLE, TABLE + N, comp_y);
	for (int i = 1; i < N; ++i)
		list.push_back({ abs(TABLE[i].y - TABLE[i - 1].y), TABLE[i].idx, TABLE[i - 1].idx });

	sort(TABLE, TABLE + N, comp_z);
	for (int i = 1; i < N; ++i)
		list.push_back({ abs(TABLE[i].z - TABLE[i - 1].z), TABLE[i].idx, TABLE[i - 1].idx });
	
	sort(list.begin(), list.end());

	for (int i = 0; i < list.size(); ++i) {
		int left_p = list[i].a, right_p = list[i].b;

		while (left_p != parent[left_p])
			left_p = parent[left_p];

		while (right_p != parent[right_p])
			right_p = parent[right_p];

		if (left_p == right_p)
			continue;

		if (set_size[left_p] > set_size[right_p])
			swap(left_p, right_p);
		parent[left_p] = right_p;
		DIST += list[i].len;
		set_size[right_p] += set_size[left_p];
		if (set_size[right_p] == N)
			break;
	}

	cout << DIST;

	return 0;
}

링크

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

해설

1717 집합의 표현 문제와 상당히 유사한 문제입니다.

다만 차이점은 노드 구별자가 숫자가 아니라 최대 20길이의 대소문자 문자열 이기 때문에 해슁이 필요합니다.

직접 해쉬를 구현할 수도 있으나 그와 비슷한 역할을 할 수 있는 STL map 을 사용해서 풀었습니다.

map 을 사용하는것 이외에는 1717 번 문제와 똑같으므로 따로 해설은 적지 않았습니다.

코드

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

typedef struct {
	string name;
	int num;
} parent;

map<string, parent> TABLE;
int T, F;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> T;
	for (int test_case = 0; test_case < T; ++test_case) {
		cin >> F;
		TABLE.clear();
		for (int i = 0; i < F; ++i) {
			string left, right;
			cin >> left >> right;

			if (TABLE.find(left) == TABLE.end()) {
				TABLE.insert({ left, { left, 1 } });
			}
			if (TABLE.find(right) == TABLE.end()) {
				TABLE.insert({ right, { right, 1 } });
			}

			while (left != TABLE[left].name)
				left = TABLE[left].name;

			while (right != TABLE[right].name) {
				string name = TABLE[right].name;
				TABLE[right].name = left;
				right = name;
			}
			if (left != right) {
				TABLE[right].name = left;
				TABLE[left].num += TABLE[right].num;
			}
			cout << TABLE[left].num << "\n";
		}
	}

	return 0;
}

링크

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

해설

12015 가장 긴 증가하는 부분 수열 2 와 상당히 유사합니다.

이 풀이는 12015 의 풀이내용을 제외한 수열을 찾는 방법에 대한 해설만 적혀있으므로 

12015 를 풀어보지 않았다면 위의 글을 먼저 읽고오시길 바랍니다.

12015 의 풀이대로 풀면 계속 수열을 덮어씌우는 방법으로 갯수를 늘려나가서

원래의 수열을 찾기는 쉽지 않습니다.

그러나 각 입력별로 몇번째 idx 자리에 들어갔는지를 알고있다면

현재 idx 에서 왼쪽으로 탐색하다가 처음으로 만나는 idx - 1 인 값은 현재값보다 반드시 작을 것 입니다.

이것을 이용하면 간단히 풀 수 있습니다.

알고리즘을 요약하자면

1. 입력을 받을 때 이 값의 idx 값 또한 저장해둔다.

2. idx 값을 저장해둔 배열을 뒤에서 부터 탐색하면서 idx, idx - 1, idx - 2, ... 인 값들을 스택에 차례로 저장

3. 스택에서 값을 차례로 빼내면 정답

백준의 예제를 예로 들어보겠습니다.

10 20 10 30 20 50 의 idx 값들은

위와 같이 나올 것 입니다.

그러면 알맞은 수열을 찾기위해 위의 알고리즘을 적용하면

6번째 idx = 4

idx = 4

같으므로 스택에 저장합니다. ( idx-- )

스택 : 50

5번째 idx = 2

idx = 3 다르므로 패스

스택 : 50

4번째 idx = 3

idx = 3

같으므로 스택에 저장합니다. ( idx-- )

스택 : 50 30

3번째 idx = 1

idx = 2 다르므로 패스

스택 : 50 30

2번째 idx = 2

idx = 2

같으므로 스택에 저장합니다. ( idx-- )

스택 : 50 30 20

1번째 idx = 1

idx = 1

같으므로 스택에 저장합니다. ( idx-- )

스택 : 50 30 20 10

스택을 뒤집으면 정답인 10 20 30 50 이 나오게됩니다.

아래 코드에 모두 구현되어있습니다.

코드

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

int N, IN[1000000], idx = 0, TABLE[1000000], STACK[1000001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	STACK[0] = -1000000001;
	for (int i = 0; i < N; ++i) {
		cin >> IN[i];
		if (IN[i] <= STACK[idx]) {
			int* bound = lower_bound(STACK, STACK + idx, IN[i]);
			*bound = IN[i];
			TABLE[i] = bound - STACK;
		}
		else {
			STACK[++idx] = IN[i];
			TABLE[i] = idx;
		}
	}

	cout << idx << "\n";

	int looper = N - 1;
	vector <int> stk;
	while (idx != 0) {
		if (TABLE[looper] == idx) {
			stk.push_back(IN[looper]);
			idx--;
		}
		looper--;
	}

	while (!stk.empty()) {
		cout << stk.back() << " ";
		stk.pop_back();
	}

	return 0;
}

링크

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

해설

위상정렬로 분류되있는 문제이긴한데 크게 중요하진 않은 것 같습니다.

생각보다 간단하게 해결했습니다.

그냥 입력을 받고 각 노드의 왼쪽에 있어야하는 노드들을 모두 저장해둡니다.

그리고 모든 노드들에 대해 DFS 를 하며 가장 왼쪽부터 차례대로 출력을 하면 됩니다.

코드에 모두 구현되어있습니다.

코드

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

int N, M;
vector<vector<int>> TABLE;
bool visit[32001];

void DFS(int _num) {
	if (visit[_num])
		return;
	visit[_num] = true;
	int now_size = TABLE[_num].size();

	for (int i = 0; i < now_size; ++i) {
		DFS(TABLE[_num][i]);
	}
	cout << _num << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	TABLE.resize(N + 1);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		TABLE[b].push_back(a);
	}

	for (int i = 1; i <= N; ++i)
		DFS(i);

	return 0;
}

링크

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

해설

이 문제는 DFS와 BFS 모두 사용할 수 있습니다.

그러나 BFS 가 메모리도 적게사용하고 시간도 약간 더 빨라 해설에서는 BFS를 사용하였습니다.

DFS버전이 궁금하시면 >> 깃허브 << 에 올려두었습니다.

골드문제에서는 주로 정적배열만으로 해결이 다 됬었는데 플레티넘으로 넘어가니 동적배열을 사용해야하네요.

2차원 vector 을 이용해서 각 노드별로 연결된 노드들의 숫자를 다 입력해둡니다.

그 후 BFS 를 이용해서 각 노드들의 깊이(depth) 를 구합니다.

골드문제인 11437 LCA 는 그냥 깊이를 맞추고 상승시켜가면서 같은걸 찾으면 되지만

이 문제같은 경우는 훨씬 노드가 많기때문에 O(N) 의 복잡도를 이용하면 시간초과가 나게됩니다.

보통 O(N) 보다 더 낮은 시간복잡도를 가지려면 이분탐색을 이용하는데 여기도 똑같습니다.

PARENT 배열에 각 노드의 2^0 , 2^1 , 2^2 , ... 위의 노드들을 저장해 두고 사용합니다.

이렇게 탐색을 하면 O(log N) 만에 찾을 수 있습니다.

코드를 보시면

PARENT[next][i] = PARENT[PARENT[next][i - 1]][i - 1]

위와 같은 코드를 보실 수 있는데

이코드의 의미는 현재 노드의 2^i 위의 부모는 2^(i - 1) 위 부모의 2^(i - 1) 위 부모와 같다는 뜻입니다.

그림과 같이 4 위의 노드는 2위의 노드의 2위 노드 와 같다는 것이죠.

그렇게 모든 2^i 위 노드들을 다 구해두고 입력이 들어올 때 마다 LCA 함수를 이용해서 값을 구해줍니다.

두 값의 깊이를 또 이분탐색을 이용해서 더 얕은것에 맞춰주고 아까 구해뒀던 PARENT 배열을 이용해

LCA 를 찾을 때 까지 이동을 하다가 찾으면 return 하면됩니다.

코드에 모두 구현되어있습니다.

코드

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

int N, M, DEP[100001], PARENT[100001][18];
bool visit[100001];
vector<vector<int>> LIST;
queue<int> que;

int LCA(int _a, int _b) {
	if (DEP[_a] < DEP[_b]) swap(_a, _b);

	int looper = 0;
	while (DEP[_a] != DEP[_b]) {
		++looper;
		if ((DEP[_a] - (1 << looper)) < DEP[_b]) {
			_a = PARENT[_a][looper - 1];
			looper = 0;
		}
	}
	while (_a != _b) {
		looper = 1;
		while (PARENT[_a][looper] != PARENT[_b][looper])
			++looper;
		_a = PARENT[_a][looper - 1];
		_b = PARENT[_b][looper - 1];
	}
	return _a;
}

void BFS() {
	que.push(1);
	while (!que.empty()) {
		int now = que.front();
		que.pop();
		for (int i = 0; i < LIST[now].size(); ++i) {
			int next = LIST[now][i];
			if (visit[next])
				continue;
			visit[next] = true;
			que.push(next);
			DEP[next] = DEP[now] + 1;
			PARENT[next][0] = now;
			for (int i = 1; i < 18; ++i) {
				PARENT[next][i] = PARENT[PARENT[next][i - 1]][i - 1];
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	LIST.resize(N + 1);
	for (int i = 0; i < N - 1; ++i) {
		int a, b;
		cin >> a >> b;
		LIST[a].push_back(b);
		LIST[b].push_back(a);
	}

	DEP[1] = 1;
	visit[1] = true;
	BFS();

	cin >> M;
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		cout << LCA(a, b) << "\n";
	}

	return 0;
}

링크

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

해설

어떤 분류의 문제다 라고 딱 설명드리기 어려운 문제입니다.

문제를 푸는 키 알고리즘은 아니긴 한데 lower_bound라는 이분 탐색을 이용해서 위치를 찾긴 합니다.

알고리즘은 다음과 같습니다.

1. 입력을 받습니다.

2. 입력받은 값이 현제 리스트의 끝값보다 작거나 같으면 lower_bound를 이용해 찾은 곳에 덮어 씌웁니다.

3. 입력받은 값이 현제 리스트의 끝 값보다 크면 리스트 뒤에 추가합니다.

알고리즘만 보면 이게 뭐 하는 건지 싶습니다.

간단하게 설명을 드리자면 배열을 하나 사용하고 증가하는 부분 수열을 계속 덮어 씌우다가

결국 튀어나가면 그때가 최대 크기의 수열인 것입니다.

간단한 예를 들어보겠습니다.

10, 50, 60, 20, 30, 40, 50

위의 예를 알고리즘을 적용하면

3번째인 60까지는 위와 같이 순차적으로 쌓이게 됩니다.

그런데 이때 이 예의 가장 긴 증가하는 부분 수열인 10 20 30 40 50 의 뒷 파트 20 30 40 50 이 들어오는 것을 잘 보시면

마치 원래 있던 수열 10 50 60 을 덮어쓰는 것처럼 보이게 됩니다.

이게 핵심입니다.

이 배열에 계속 후보가 될만한 것들을 덮어 씌우다가 결국 맨 마지막에 수열의 크기를 측정하면

입력에서 나올 수 있는 가장 긴 증가하는 부분 수열이 되는 것입니다.

모두 코드에 구현되어있습니다.

코드는 배열이 비어있다는 예외를 없애기 위해서 0번째에 가장 작은 값 0을 삽입하였습니다.

배열 대신 vector을 사용해서 구현해도 됩니다.

그러면 정답은 vector.size() - 1 이 됩니다. ( 맨 앞에 0을 넣으므로 )

코드

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

int N, TABLE[1000001], idx = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	TABLE[0] = 0;
	for (int i = 0; i < N; ++i) {
		int temp;
		cin >> temp;

		if (temp <= TABLE[idx])
			*lower_bound(TABLE, TABLE + idx, temp) = temp;
		else
			TABLE[++idx] = temp;
	}

	cout << idx;

	return 0;
}

링크

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

해설

해설에 앞서 이분 그래프란?

인접한 vertex의 색이 모두 다르게 칠하는데 단 2가지 색으로만 칠할 수 있는 그래프를 말합니다.

한마디로 특정 버텍스에서 어떤 곳으로 든 이동시 퐁 당 퐁 당 이 되어야 한다는 뜻입니다.

핵심은 BFS를 이용하는 것입니다.

위의 설명대로 퐁 당 퐁 당 이 되어야 하기 때문에 BFS로 탐색 시 임의 값 0, 1 이 번갈아 나오면 됩니다.

알고리즘을 정리하면

1. BFS 를 실시하는데 연결된 모든 vertex의 value는 현재 vertex의 value와 다른 값이 되어야 한다.

2. 모든 vertex에 대해 BFS를 실시하였음에도 불구하고 모두 만족하면 YES 아니면 NO

아래 코드에 모두 구현되어있다.

코드의 경우 방문하지 않은 곳은 -1  방문할 경우 각 위치에 맞는 value 인 0 or 1 이 들어가게 된다.

vertex 방문 시 항상 인접한 모든 vertex를 검사해서 내 value와 다른지 확인한다.

코드

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

int K, V, E;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> K;

	for (int i = 0; i < K; ++i) {
		cin >> V >> E;
		vector <vector <int>> v(V, vector<int>());
		vector <int> table(V, -1);
		for (int j = 0; j < E; ++j) {
			int a, b;
			cin >> a >> b;
			a--; b--;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		queue <pair <int, int>> que;
		que.push({ 0, 0 });
		while (true) {
			while (!que.empty()) {
				int vtx = que.front().first, value = que.front().second;
				if (table[vtx] != -1) {
					if (table[vtx] != value)
						break;
					else {
						que.pop();
						continue;
					}
				}
				que.pop();
				table[vtx] = value;
				value = value == 0 ? 1 : 0;
				for (int j = 0; j < v[vtx].size(); ++j)
					que.push({ v[vtx][j] , value });
			}
			if (!que.empty()) {
				cout << "NO" << "\n";
				break;
			}
			else {
				int i = 0;
				for (; i < V; ++i) {
					if (table[i] == -1)
						break;
				}
				if (i == V) {
					cout << "YES" << "\n";
					break;
				}
				que.push({ i, 0 });
				
			}
		}
		
	}

	return 0;
}

링크

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

해설

tree의 root를 이용해서 집합을 구별하는 문제입니다.

이 문제는 알면 쉬우나 모르면 발상을 해내는 것이 어려운 문제입니다.

처음에는 단순히 tree의 root를 계속 바꿔주면서 했더니 타임아웃이 났습니다.

그래서 root 를 찾을 때 찾아 올라가면서 들렸던 모든 수들의 현재 상위 노드 또한 root로 바꿔주었습니다.

알고리즘은 다음과 같습니다. ( a = 왼쪽 값 , b = 오른쪽 값)

입력이 0 일때

1. a의 root를 찾습니다.

2. b의 root 를 찾고 b의 root 를 a의 root로 연결시킵니다.

 (이때 각 root를 찾는 동안 들렸던 노드들의 상위 노드 또한 각자의 root로 갱신시켜줍니다.)

입력이 1 일 때

1. a의 root와 b의 root 가 같은지 확인합니다.

코드

#include <iostream>
using namespace std;

int N, M, TABLE[1000001];

int find_top(int _num) {
	if (TABLE[_num] == _num)
		return _num;
	return TABLE[_num] = find_top(TABLE[_num]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> M;

	for (int i = 0; i <= N; ++i)
		TABLE[i] = i;
	
	for (int i = 0; i < M; ++i) {
		int temp, a, b;
		cin >> temp >> a >> b;
		if (temp) {
			if (find_top(a) == find_top(b))
				cout << "YES" << "\n";
			else
				cout << "NO" << "\n";
		}
		else
			TABLE[find_top(b)] = find_top(a);
		
	}


	return 0;
}