Mohand's code block

네트워크란?

Network 는 net 와 work 의 합성어입니다. 여러 컴퓨터들이 그물망처럼 연결되어 통신을 하기에 붙여진 이름입니다.

네트워크에는 여러 종류가 있습니다.

• PAN (Personal Area Network) 개인 통신망
  가장 작은단위의 통신망입니다. 사실 통신망이라고 하기도 좀 그렇습니다. 예를 들자면 핸드폰과 블루투스로 연결된 이어폰이나 핫스팟 같은 기능으로 이어져있는 통신망 등이 이에 해당합니다.
  
  
• LAN (Local Area Network) 근거리 통신망
  집집마다 있는 공유기를 통해 형성되는 통신망입니다. 많이 들어본 이름일 것입니다. 게임을 하거나 여러 프로그램을 통해 통신을 하다보면 같은 공유기내의 기기와 연결할 때가 있는데 이럴 때 주로 LAN 이라는 이름으로 되어있을 것입니다. 주로 한 주택이나 사무실 단위입니다.
  
  
• MAN (Metropolitan Area Network) 도시권 통신망
  처음 통신망이라는 개념이 생길때는 없던 개념입니다. 그러나 휴대전화의 보급으로 인해 도시마다 기지국이 생기면서 해당 기지국을 통해 통신망을 구축하게 됐고, 이 통신망을 위한 새로운 개념이 필요해졌기 때문에 생겼습니다. 주로 도시단위입니다.
• WAN (Wide Area Network) 광역 통신망
  가장 넓은 개념의 통신망입니다. 대부분의 통신이 이 광역 통신망을 통해 이루어집니다.

통신망의 구조

그렇다면 통신을 대체 어떻게 한다는 뜻일까요?

여기에 5대의 컴퓨터가 있다고 가정해봅시다. 이 5대의 컴퓨터를 서로 연결시키려면 어떻게 하는게 가장 좋을까요?

물론 5개의 컴퓨터를 모두 각자 연결시키는게 가장 좋을 것입니다.

그러나 만약 컴퓨터가 5대가 아니라 10대, 20대, 50대 여러 컴퓨터들을 연결한다면 어떻게 될까요?

5대의 컴퓨터를 연결하는대만 !4 = 10개의 연결이 필요한데 개수가 늘어나면 엄청나게 많은 비용이 필요할 것입니다.

그래서 나온 것이 바로 라우터입니다.

라우터를 이용한다면 추가되는 기기가 있더라도 적은 비용으로 연결을 할 수 있게 됩니다.

그리고 이런 라우터 간에 연결을 통해 네트워크를 구성한다면 매우 효율적으로 구성할 수 있습니다.

실제로 여러분의 집에서 이용되는 공유기도 하나의 라우터입니다.

여러 기기들이 공유기에 연결되어서 외부와 통신을 하고 있습니다.

그렇다면 이렇게 연결해서 어떤 정보를 보내서 어떻게 누구에게 통신을 하는 걸까요?

이것을 알려면 먼저 네트워크의 계층에 대해 알고 이것이 어떻게 동작하는지 알아야합니다.

이것은 다음글 에서 알아보겠습니다.

들어가기 전..

이 글은 matplotlib 에 대한 글입니다.

matplotlib 가 설치되어 있어야 합니다.

만약 설치되어 있지 않다면

pip install matplotlib

pip install numpy

위 두 줄을 터미널에서 실행해서 설치해주시기 바랍니다.

그리고 항상 코드를 배울 때는 레퍼런스를 함께 봐야 합니다.

https://matplotlib.org/3.5.0/index.html

위의 레퍼런스를 참조하면서 배우시기 바랍니다.

기본 그래프 그리기

import matplotlib.pyplot as plt

X= [1, 2,  3,  4,  5]
Y1 = [1, 4,  9, 16, 25]
plt.plot(X, Y1, color='red', marker='o', alpha=0.5, linewidth=2)

plt.title("mohand's code block")
plt.xlabel("x example")
plt.ylabel("y example")
plt.show()

위의 코드를 실행하면

이런 창이 하나 뜰 것입니다.

matplotlib 을 이용한 가장 기초적인 그래프를 그린 것입니다.

그럼 이제 한줄한줄에 대한 설명을 해드리겠습니다.

import matplotlib.pyplot as plt

matplotlib 중에 pyplot 을 사용할 것이고 이 이름을 plt 으로 붙이겠다 는 뜻입니다.

X= [1, 2,  3,  4,  5]
Y1 = [1, 4,  9, 16, 25]

X 축과 Y축의 값을 세팅하는 과정입니다.

이렇게 하나하나 직접 넣어줘도 되고 나중에 numpy 를 이용해 자동으로 생성시켜도 됩니다.

plt.plot(X, Y1, color='red', marker='o', alpha=0.5, linewidth=2)

plt 의 plot 이라는 그래프를 이용하겠다는 뜻입니다.

https://matplotlib.org/3.5.0/plot_types/index.html

위의 레퍼런스 사이트에서 plot types 를 보면 어떤 종류의 그래프를 그릴 수 있는지 다 나옵니다.

해당 그래프를 만들 때 넣어야 하는 arg도 적혀있습니다.

나머지 arg 들을 살펴보겠습니다.

color : 줄의 색상

줄의 색상은 'red' 같은 표기방법 말고도 '#aabbcc' 같이 RGB로도 설정할 수 있습니다.

marker : 점의 모양

'o' 외에도 많은 marker 들이 있습니다. 레퍼런스에서 확인할 수 있습니다.

https://matplotlib.org/3.5.0/api/markers_api.html#module-matplotlib.markers

alpha : 투명도

0 ~ 1 까지의 값으로 투명도를 설정합니다.

일반적으로 1로 완전 불투명으로 하기보다는 0.5 정도의 값을 사용합니다.

linewidth : 선의 굵기

원하는 값을 넣으면 해당 선의 굵기로 설정합니다.

정수뿐만 아니라 소수도 가능합니다.

arg들은 주로 사용하는 몇 가지만 적어봤습니다. 더 원하는 옵션 등은 레퍼런스에서 확인하실 수 있습니다.

https://matplotlib.org/3.5.0/api/_as_gen/matplotlib.axes.Axes.plot.html#matplotlib.axes.Axes.plot

plt.title("mohand's code block")
plt.xlabel("x example")
plt.ylabel("y example")
plt.show()

그래프의 제목과 x, y축의 라벨 문장을 설정하는 코드입니다.

그리고 최종적으로 show() method 를 실행하게 되면 그래프를 그려줍니다.

결론

이번 글에서는 matplotlib 를 이용해 기초적인 그래프를 그려보았습니다.

다음 글에서는 더 다양한 그래프를 다뤄보겠습니다.

개요

pip install 실행 시 SyntaxError: invalid syntax 가 뜨는 오류를 해결하기 위한 방법입니다.

해결방법

간단합니다. pip는 python 내에서 실행하면 안 됩니다.

제가 사용 중인 pycham 같은 경우 하단의 Python Console 말고 Terminal 에서 pip install 을 실행하면 잘 될 것입니다.

pycharm 같은 경우는 자체 파이썬을 사용해서 위의 사진과 같이 설치하면 되지만

다른 IDE는 직접 설치해야 할 수도 있습니다.

이러면 명령 프롬프트를 이용해야 합니다.

명령 프롬프트를 이용해서 pip install 을 했는데 위와 같이

'pip'은(는) 내부 또는 외부 명령, 실행할 수 있는 프로그램, 또는 배치 파일이 아닙니다.

라는 오류가 나오면 파이썬을 환경변수에 등록하여야 합니다.

환경변수에 프로그램을 등록하는 방법 >> 클릭 <<

위의 방법으로

파이썬 위치

파이썬 위치\Scripts

이 두 가지를 추가해줘야 합니다.

제 컴퓨터는 파이썬이 설치된 위치가 다음과 같아서 아래의 두 개를 추가했습니다. (Python 3.9.1 기준)

C:\Users\사용자이름\AppData\Local\Programs\Python\Python39\

C:\Users\사용자이름\AppData\Local\Programs\Python\Python39\Scripts\

환경변수가 제대로 추가되어있다면 위와 같이 설치가 잘 됩니다.

링크

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;
}

여러 가지 문제를 풀다 보면 stack 자료구조를 이용해야 할 때가 많이 있습니다.

그런데 vector 도 마치 stack처럼 사용할 수 있는데 혹시 vector를 사용하면 안 될까 라는 생각에

vector를 사용해 보았는데 stack 보다 더 빠른 결과가 나왔습니다.

그래서 이번에는 c++ 의 여러 가지 자료구조들의 속도를 한번 측정해 보았습니다.

측정에 사용된 코드입니다.

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <time.h>
using namespace std;

#define looper 1000000

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

	clock_t start, end;
	double result;


	vector <int> v;

	start = clock();
	for (int i = 0; i < looper; ++i) {
		v.push_back(i);
	}
	while (!v.empty()) {
		v.pop_back();
	}
	end = clock();
	result = (double)(end - start);
	cout << "vector : " << result << "\n";
	

	stack<int> stk;

	start = clock();
	for (int i = 0; i < looper; ++i) {
		stk.push(i);
	}
	while (!stk.empty()) {
		stk.pop();
	}
	end = clock();
	result = (double)(end - start);
	cout << "default stack : " << result << "\n";


	stack<int, vector<int>> v_stk;

	start = clock();
	for (int i = 0; i < looper; ++i) {
		v_stk.push(i);
	}
	while (!v_stk.empty()) {
		v_stk.pop();
	}
	end = clock();
	result = (double)(end - start);
	cout << "vector stack : " << result << "\n";


	deque<int> dqu;

	start = clock();
	for (int i = 0; i < looper; ++i) {
		dqu.push_back(i);
	}
	while (!dqu.empty()) {
		dqu.pop_back();
	}
	end = clock();
	result = (double)(end - start);
	cout << "deque : " << result << "\n";


	return 0;
}

백만번씩 push pop 한 실행 결과입니다.

일단 vector 와 stack을 비교해보면 무려 1.2 초 가량 차이가 나는 것을 볼 수 있습니다.

왜 이런 결과가 나오는 것일까요?

보통 생각대로라면 vector 보다 stack 이 훨씬 단순한데 stack 이 더 빨라야 하는 것 아닐까요?

이 이유를 알려면 stack 에 대해 알고 있어야 합니다.

stack 은 사실 따로 stack이라는 내부 컨테이너가 있는 것이 아닙니다.

vector, deque, list container 같은 내부 컨테이너들을 그대로 사용하되 마치 stack처럼 동작하게 해 둔 것입니다.

그러니까 사실 stack을 선언하면 기본값으로 deque로 선언이 됩니다.

그래서 결과를 보시면 default stack과 deque의 시간 차이가 그렇게 크지 않습니다.

stack의 내부 컨테이너로 vector를 사용하게 되면 vector와 거의 비슷한 결과가 나옵니다.

그런데 같은 내부 컨테이너를 사용해도 그냥 vector와 vector stack , deque와 deque stack을 보면 stack 이 뭔가 조금 더 느립니다.

그래서 알고리즘 문제를 풀 때는 그냥 vector를 사용해서 푸는 게 훨씬 빠릅니다.

그러나 나중에 어떤 프로젝트에 참여하게 되시거나 프로그램을 만들게 될 때 vector를 사용하게 되면 사용 용도가 모호해지는 현상이 발생할 수 도 있으므로 vector stack을 사용하시는 것을 추천드립니다.

결론

1. 알고리즘 문제를 풀 때는 vector 가 제일 빠르다.

2. 그러나 대형 프로그램을 짤 때는 용도가 모호해질 수 있으므로 vector stack을 사용하자.

링크

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;
}