이것 저것 &

문제링크:www.acmicpc.net/problem/1697

너무나도 간단한 bfs 문제입니다.

숫자 범위가 크기 때문에 bfs를 선택했고, 방문여부를 판단하는 배열을 만들어서 문제를 해결했습니다.

아래는 정답 코드입니다.

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

int n = 0, k = 0;
int result = 0;
int visited[100001] = { 0, };
queue <int> que;

int main() {
	iostream::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;

	que.push(n);
	visited[n] = 1;
	while (!que.empty()) {
		int p = que.front();
		que.pop();
		if (p == k) {
			cout << visited[p] - 1 << endl;
			return 0;
		}
		if (visited[p - 1] == 0 && (p - 1) >= 0 && (p - 1) <= 100000)
			que.push(p - 1), visited[p - 1] = visited[p] + 1;
		if (visited[p + 1] == 0 && (p + 1) >= 0 && (p + 1) <= 100000)
			que.push(p + 1), visited[p + 1] = visited[p] + 1;
		if (visited[p*2] == 0 && (p*2) >= 0 && (p*2) <= 100000)
			que.push(p*2), visited[p*2] = visited[p] + 1;
	}

	return 0;
}

위와 같은 형태를 가지고 있죠.

가변길이 구조체란 배열의 크기를 동적으로 할당하여 사용하는 것이다.

이때 2가지를 지켜야한다.

• 1. 사이즈가 0인 array는 가장 아래에 선언해야한다.
• 2. 동적할당을 하고 사용해야 한다.

동적할당하는 방법이나, 세부적인 내용은 아래 링크들을 참고하시면 감이 올거다.

그리고 논란인 char name[0] char name[]의 차이점은 

즉, 같은 문법으로 사용되고 있고, 표준은 []이 정확하다는 의견이다. c99 이후 버전을 사용한다면 []를 지향하자.

computersource.tistory.com/61blog.naver.com/PostView.nhn?blogId=sdi760210&logNo=70084541983&parentCategoryNo=63&viewDate=&currentPage=1&listtype=0

blog.naver.com/PostView.nhn?blogId=sdi760210&logNo=70084541983&parentCategoryNo=63&viewDate=&currentPage=1&listtype=0

www.forbes.com/sites/quora/2013/05/14/what-is-the-advantage-of-using-zero-length-arrays-in-c/?sh=660c8a2f213a

네트워크 소켓통신시에는 패킹이라는 것을 해야합니다.

우선, 왜써야 할까?

해당 구조체에서 Data 구조체의 크기는?    data[0]는 단순히 메모리 위치만은 가르키는 녀석이기 때문에 4+ 1+ 1+ 1 = 7 이어야 하지만, 8이 나오는 모습을 볼 수 있었다.

그 이유는 

바이트 패딩: 

몇몇 컴파일러는 구조체의 필드를 메모리에 위치시킬때 중간에 빈공간없이 쭉 이어서 할당하는 경우도 있지만 대부분의 컴파일러는 성능향상을 위해 CPU가 접근하기 쉬운 위치에 필드를 배치하는데(OS나 컴파일러에 따라 4바이트단위 또는 8바이트 단위로 끊는작업을 함) 이를 "바이트 패딩"이라고 하며, 그러다보니 중간이 빈 공간이 들어가게 되는데 이 빈 공간을 "패딩비트"라 한다.  

이녀석 때문이다.

패딩 비트를 제거해주고, 연속된 메모리에 데이터를 할당하고 소켓통신을 해야만 올바르게 데이터를 주고 받을 수 있다.

그렇기 때문에 소켓통신시에 패킹이 필요한 것이다.

사용방법은 간단!!

이런식으로 데이터를 묶어주면 된다.

헤더는 #include <stdio.h>

pack(push, 1) // 1바이트 크기로 정렬하겠다는 의미

pack(pop) // 정렬 설정을 이전 상태(기본값)로 되돌리겠다는 의미

해당방법은

• Visual Studio, GCC 4.0 이상

의 환경에서만 가능하다.

이전버전을 사용한다면( 그럴 일은 거의 없지만..) 혹은 다른 방법을 원한다면 아래 링크들을 참고

dojang.io/mod/page/view.php?id=432

www.vbflash.net/164

https://3dmpengines.tistory.com/1571 [3DMP]

epoll을 구현할 때 엣지 트리거와 레벨 트리거 2가지 방식으로 구현이 가능하다.  

두가지 개념을 설명하기 위해서 우선, 블록킹과 논블록킹 개념에 대해서 설명하겠다.

블로킹/논블로킹

작업을 수행할 때,

1. 자신의 작업을 하다가 다른 작업 주체가 하는 작업의 시작부터 끝까지 기다렸다가 다시 자신의 작업을 시작한다면 이는 블로킹

2. 다른 주체의 작업과 관계없이 자신의 작업을 계속한다면 이를 논블로킹

스레드 A가 어떤 작업을 하는 다른 대상을 호출하고, 그 대상이 가져온 결과물을 받아 다시 작업을 재개하고 있습니다. 예를 들자면 Java에서 JDBC를 사용하여 DB에 질의를 날리고 결과를 받아오는 작업을 블로킹 작업이라고 부를 수 있습니다. 이와 반대로 다른 주체에게 작업을 요청하고 그 결과를 받을 때까지 기다리지 않으며 자신의 작업을 한다면 이를 논블로킹이라고 할 수 있습니다.

siyoon210.tistory.com/147

deveric.tistory.com/99

blog.naver.com/n_cloudplatform/222189669084

결론부터 말하면 레벨 트리거와 엣지 트리거는 

Level-Triggered : 특정 조건이 유지되면 계속 감지

Edge-Triggered : 조건이 변할 때만 감지. ET

이다.

즉 엣지 트리거는 논블럭킹 방식이다.

엣지 트리거는 데이터 수신 시 딱 한번만 이벤트가 발생하기 때문에 이벤트가 발생했을 때 충분한 양의 버퍼를 마련한 다음에 모든 데이터를 다 읽어 들여야 한다. 즉, 데이터의 분량에 따라서 IO로 인한 DELAY가 생길 수 있다. 그래서 엣지 트리거에서는 넌-블로킹 IO를 이용한다. 입력 함수의 호출과 다른 작업을 병행할 수 있기 때문이다.

추가적으로 레벨 트리거 방식에서는 입력 버퍼에 데이터가 남아있는 동안에 게속해서 이벤트가 등록된다. 이는 비효율적이다. 하지만 엣지 트리거는 데이터가 수신되면 딱 한번 이벤트가 등록된다. 

논블로킹 모드로 만드는 이유는 엣지 트리거 방식의 특성상 블로킹 방식으로 동작하는 read & write 함수의 호출은 서버를 오랜 시간 멈추는 상황으로까지 이어지게 할 수 있기 때문이다.  

아래는 엣지 트리거 방식의 에코서버이다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <sys/epoll.h>

#define BUF_SIZE 4
#define EPOLL_SIZE 50
void setnonblockingmode(int fd);
void error_handling(char *buf);

int main(int argc, char *argv[])
{
	int serv_sock, clnt_sock;
	struct sockaddr_in serv_adr, clnt_adr;
	socklen_t adr_sz;
	int str_len, i;
	char buf[BUF_SIZE];

	struct epoll_event *ep_events;
	struct epoll_event event;
	int epfd, event_cnt;

	if(argc!=2) {
		printf("Usage : %s <port>\n", argv[0]);
		exit(1);
	}

	serv_sock=socket(PF_INET, SOCK_STREAM, 0);
	memset(&serv_adr, 0, sizeof(serv_adr));
	serv_adr.sin_family=AF_INET;
	serv_adr.sin_addr.s_addr=htonl(INADDR_ANY);
	serv_adr.sin_port=htons(atoi(argv[1]));
	
	if(bind(serv_sock, (struct sockaddr*) &serv_adr, sizeof(serv_adr))==-1)
		error_handling("bind() error");
	if(listen(serv_sock, 5)==-1)
		error_handling("listen() error");

	epfd=epoll_create(EPOLL_SIZE);
	ep_events=malloc(sizeof(struct epoll_event)*EPOLL_SIZE);

	setnonblockingmode(serv_sock);
	event.events=EPOLLIN;
	event.data.fd=serv_sock;	
	epoll_ctl(epfd, EPOLL_CTL_ADD, serv_sock, &event);

	while(1)
	{
		event_cnt=epoll_wait(epfd, ep_events, EPOLL_SIZE, -1);
		if(event_cnt==-1)
		{
			puts("epoll_wait() error");
			break;
		}

		puts("return epoll_wait");
		for(i=0; i<event_cnt; i++)
		{
			if(ep_events[i].data.fd==serv_sock)
			{
				adr_sz=sizeof(clnt_adr);
				clnt_sock=accept(serv_sock, (struct sockaddr*)&clnt_adr, &adr_sz);
				setnonblockingmode(clnt_sock);
				event.events=EPOLLIN|EPOLLET;
				event.data.fd=clnt_sock;
				epoll_ctl(epfd, EPOLL_CTL_ADD, clnt_sock, &event);
				printf("connected client: %d \n", clnt_sock);
			}
			else
			{
					while(1)
					{
						str_len=read(ep_events[i].data.fd, buf, BUF_SIZE);
						if(str_len==0)    // close request!
						{
							epoll_ctl(epfd, EPOLL_CTL_DEL, ep_events[i].data.fd, NULL);
							close(ep_events[i].data.fd);
							printf("closed client: %d \n", ep_events[i].data.fd);
							break;
						}
						else if(str_len<0)
						{
							if(errno==EAGAIN)
								break;
						}
						else
						{
							write(ep_events[i].data.fd, buf, str_len);    // echo!
						}
				}
			}
		}
	}
	close(serv_sock);
	close(epfd);
	return 0;
}

void setnonblockingmode(int fd)
{
	int flag=fcntl(fd, F_GETFL, 0);
	fcntl(fd, F_SETFL, flag|O_NONBLOCK);
}
void error_handling(char *buf)
{
	fputs(buf, stderr);
	fputc('\n', stderr);
	exit(1);
}

클라이언트 코드와 epoll에 대한 기본적인 설명은 아래 링크를 참고하자.

gusdnr69.tistory.com/220

TCP/IP Socket 기반 서버를 제작하는 방법은 크게 3가지가 있다.

• 1. 멀티 프로세싱
• 2. 멀티 쓰레싱
• 3. 멀티 플렉싱

1번과 2번은 클라이언트 마다 새로운 프로세스, 스레드를 생성하기 때문에 서버의 부하가 많이 이뤄진다. 그래서 성능을 높이기 위해서 멀티 플레싱방식을 사용한다.

이때 주로 사용하는 것은 OS별로

• linux: select, epoll, lip service
• window: iocp

이번 포스팅에서는 select과 epoll의 차이점과 간단한 epoll 예제에 대해서 설명하겠다.

select과 epoll 모두 하나의 구조체에 클라이언트의 파일 디스크립터를 모아놓고 동시에 이들을 관찰할 수 있는 구조이다.

select함수는 아주 예전에 개발된 방식으로 몇가지 문제점을 가진다.

• 1. 동시접속자수가 100안팍이다.
• 2. 모든 파일 디스크립터를 대상으로 반복문을 진행하기에 효율이 떨어진다.
• 3. select함수 호출시 매번 운영체제에게 관찰대상에 대한 정보를 전달해야 한다.

이러한 단점들 때문에 성능적인 문제점이 야기되었고, epoll이 등장했다.

epoll은 운영체제에게 관찰대상에 대한 정보를 딱 한번만 알려주고 관찰대상에 대한 변경이 있을 때 변경 사항만 알려주는 방식이다.

epoll의 장점

• 상태변화의 확인을 위한, 전체 파일 디스크립터를 대상으로 하는 반복문이 필요 없다.
• select 함수에 대응하는 epoll_wait 함수호출 시, 관찰대상의 정보를 매번 전달할 필요가 없다.

epoll의 함수

epoll_create : epoll 파일 디스크립터 저장소 생성

epoll_ctl : 저장소에 파일 디스크립터 등록 및 삭제

epoll_wait : select 함수와 마찬가지로 파일 디스크립터의 변화를 대기한다.

아래는 epoll 에코서버에 대한 간단한 예시이다.

server(linux)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <sys/epoll.h>

#define BUF_SIZE 100
#define EPOLL_SIZE 50
void error_handling(char *buf);

int main(int argc, char *argv[])
{
	int serv_sock, clnt_sock;
	struct sockaddr_in serv_adr, clnt_adr;
	socklen_t adr_sz;
	int str_len, i;
	char buf[BUF_SIZE];

	struct epoll_event *ep_events;
	struct epoll_event event;
	int epfd, event_cnt;

	if(argc!=2) {
		printf("Usage : %s <port>\n", argv[0]);
		exit(1);
	}

	serv_sock=socket(PF_INET, SOCK_STREAM, 0);
	memset(&serv_adr, 0, sizeof(serv_adr));
	serv_adr.sin_family=AF_INET;
	serv_adr.sin_addr.s_addr=htonl(INADDR_ANY);
	serv_adr.sin_port=htons(atoi(argv[1]));
	
	if(bind(serv_sock, (struct sockaddr*) &serv_adr, sizeof(serv_adr))==-1)
		error_handling("bind() error");
	if(listen(serv_sock, 5)==-1)
		error_handling("listen() error");

	epfd=epoll_create(EPOLL_SIZE);
	ep_events=malloc(sizeof(struct epoll_event)*EPOLL_SIZE);

	event.events=EPOLLIN;
	event.data.fd=serv_sock;	
	epoll_ctl(epfd, EPOLL_CTL_ADD, serv_sock, &event);

	while(1)
	{
		event_cnt=epoll_wait(epfd, ep_events, EPOLL_SIZE, -1);
		if(event_cnt==-1)
		{
			puts("epoll_wait() error");
			break;
		}

		for(i=0; i<event_cnt; i++)
		{
			if(ep_events[i].data.fd==serv_sock)
			{
				adr_sz=sizeof(clnt_adr);
				clnt_sock=
					accept(serv_sock, (struct sockaddr*)&clnt_adr, &adr_sz);
				event.events=EPOLLIN;
				event.data.fd=clnt_sock;
				epoll_ctl(epfd, EPOLL_CTL_ADD, clnt_sock, &event);
				printf("connected client: %d \n", clnt_sock);
			}
			else
			{
					str_len=read(ep_events[i].data.fd, buf, BUF_SIZE);
					if(str_len==0)    // close request!
					{
						epoll_ctl(
							epfd, EPOLL_CTL_DEL, ep_events[i].data.fd, NULL);
						close(ep_events[i].data.fd);
						printf("closed client: %d \n", ep_events[i].data.fd);
					}
					else
					{
						write(ep_events[i].data.fd, buf, str_len);    // echo!
					}
	
			}
		}
	}
	close(serv_sock);
	close(epfd);
	return 0;
}

void error_handling(char *buf)
{
	fputs(buf, stderr);
	fputc('\n', stderr);
	exit(1);
}

client(linux)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>

#define BUF_SIZE 1024
void error_handling(char *message);

int main(int argc, char *argv[])
{
	int sock;
	char message[BUF_SIZE];
	int str_len;
	struct sockaddr_in serv_adr;

	if(argc!=3) {
		printf("Usage : %s <IP> <port>\n", argv[0]);
		exit(1);
	}
	
	sock=socket(PF_INET, SOCK_STREAM, 0);   
	if(sock==-1)
		error_handling("socket() error");
	
	memset(&serv_adr, 0, sizeof(serv_adr));
	serv_adr.sin_family=AF_INET;
	serv_adr.sin_addr.s_addr=inet_addr(argv[1]);
	serv_adr.sin_port=htons(atoi(argv[2]));
	
	if(connect(sock, (struct sockaddr*)&serv_adr, sizeof(serv_adr))==-1)
		error_handling("connect() error!");
	else
		puts("Connected...........");
	
	while(1) 
	{
		fputs("Input message(Q to quit): ", stdout);
		fgets(message, BUF_SIZE, stdin);
		
		if(!strcmp(message,"q\n") || !strcmp(message,"Q\n"))
			break;

		write(sock, message, strlen(message));
		str_len=read(sock, message, BUF_SIZE-1);
		message[str_len]=0;
		printf("Message from server: %s", message);
	}
	
	close(sock);
	return 0;
}

void error_handling(char *message)
{
	fputs(message, stderr);
	fputc('\n', stderr);
	exit(1);
}

문제링크: www.acmicpc.net/problem/1949

• '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
• 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
• 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

위

3가지 조건을 통해서 점화식을 도출해야 합니다.

문제 접근 방법:

1. 모든 경우의 수를 비교해주어야 하는 것을 인지

2. 수의 범위가 10000임으로 일반적인 dfs 를 쓰면 시간 초과가 남을 인지

3. dp방식을 통해서 한번 확인한 마을이라면 마킹을 해두며 진행해야함을 인지

점화식은 

일반 마을 = 인접 마을 중에서 최대값

우수 마을 = 인접 마을 중에서 일반 마을들의 최대값 

이고 up-down방식으로 구현했습니다.

아래는 정답 코드입니다.

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

int n = 0;
bool visited[10001] = { 0, };
int cost[10001] = { 0, };
vector <int> arr[10001];
int dp[10001][2];
void dfs(int current) {
	if (visited[current])
		return;
	
	visited[current] = 1;
	int& normal = dp[current][0];
	int& greated = dp[current][1];
	normal = 0;
	greated = cost[current];
	for (int i = 0; i < arr[current].size(); i++) {
		int num = arr[current][i];
		if (visited[num] == 1) continue;

		dfs(num);
		normal += max(dp[num][1], dp[num][0]);
		greated += dp[num][0];
		
	}
}



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

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

	for (int i = 0; i < n - 1; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		arr[t1].push_back(t2);
		arr[t2].push_back(t1);
	}

	dfs(1);

	cout << max(dp[1][0],dp[1][1]) << endl;

	return 0;
}

dfs를 먼저 호출하고 해당 값들에 넣어주어야지 값들이 올바르게 들어갑니다.

1. TCP란?

전송제어 프로토콜로 OSI 7계층중에서 전송계층에 해당하는 프로토콜입니다.

데이터 전송을 할 때 신뢰성을 보장하는 프로토콜입니다.

즉, 네트워크상에서 발생할수 있는 데이타 누락, 패킷의 순서 뒤바뀜 등의 데이터 검사 및 교정과 관련된 기능이 있습니다.

인터넷 프로토콜 스위트(IP)의 핵심 프로토콜 중 하나로, IP와 함께 TCP/IP라는 명칭으로도 널리 불립니다. TCP는 근거리 통신망이나 인트라넷, 인터넷에 연결된 컴퓨터에서 실행되는 프로그램 간에 일련의 옥텟을 안정적으로, 순서대로, 에러없이 교환할 수 있게 합니다. TCP는 전송 계층에 위치합니다. 네트워크의 정보 전달을 통제하는 프로토콜이자 인터넷을 이루는 핵심 프로토콜의 하나로서 국제 인터넷 표준화 기구(IETF)의 RFC 793에 기술되어 있습니다.

이메일 전송, 파일 전송에 주로 사용됩니다. TCP의 안정성을 필요로 하지 않는 애플리케이션의 경우 일반적으로 TCP 대신 비접속형 사용자 데이터그램 프로토콜(User Datagram Protocol)을 사용합니다. 이것은 전달 확인 및 순차 보장 기능이 없는 대신 오버헤드가 작고 지연시간이 짧다는 장점이 있습니다.

이메일 전송, 파일 전송에는 TCP가 주로 사용되고 실시간 서비스와 같이 속도가 중요한 서비스에는 UDP를 많이 사용합니다. TCP의 안정성을 필요로 하지 않는 애플리케이션의 경우 일반적으로 TCP 대신 비접속형 사용자 데이터그램 프로토콜(User Datagram Protocol)을 사용합니다. 이것은 전달 확인 및 순차 보장 기능이 없는 대신 오버헤드가 작고 지연시간이 짧다는 장점이 있습니다.

아래는 TCP와 UDP 프로토콜의 차이점입니다.

아래는 TCP소켓의 동작 절차입니다.

socket()을 통해서 소켓을 생성합니다. 서버에서는 bind함수를 통해서 주소할당, listen함수를 통해서 연결요청 대기를 하게 됩니다. 클라이언트에서는 connect함수를 통해서 서버에 연결요청을 전달하게 되고 accpet를 통해서 연결요청을 허용하게 됩니다. 연결이 이루어진 후에 send/receive를 통해 소켓을 주고받게 됩니다. 

데이터 전송을 끝내고 close함수를 통해서 소켓을 종료하게 되는 구조입니다.

2. TCP 세그먼트 구조

TCP 세그먼트는 세그먼트 헤더와 데이터의 두 섹션으로 구성됩니다. TCP 헤더는 10개의 필수 필드 및 옵션 확장 필드(표 하단의 주황색 부분)들을 포함합니다.

헤더 뒤에는 데이터 섹션이 따라 옵니다. 그 내용은 애플리케이션의 페이로드 데이터입니다. 

Source port (16 비트): 송신 포트, 출발지 포트번호를 표시한다.

Destination port (16 비트): 수신 포트, 목적지 포트번호를 표시한다.

Sequence number (32 비트): SYN 플래그가 (1)로 설정된 경우, 이것은 초기 시퀀스 번호가 된다. 실제 데이터의 최초 바이트 값과 그에 상응하는 ACK 번호는 이 값에 1을 더한 값이 된다. SYN 플래그가 (0)으로 해제된 경우, 이것은 현재 세션의 이 세그먼트 데이터의 최초 바이트 값의 누적 시퀀스 번호이다.

Acknowledgment number (32 비트): ACK 플래그가 설정된 경우 이 필드의 값은 수신자가 예상하는 다음 시퀀스 번호이다. 이것은 모든 선행하는 바이트들(존재할 경우)에 대한 수신에 대한 확인응답이 된다. 한쪽이 보낸 최초의 ACK는 반대쪽의 초기 시퀀스 번호 자체에 대한 확인응답이 되며, 데이터에 대한 응답은 포함되지 않는다.

Data offset (4 비트): 32-bit 워드 단위로 나타낸 TCP 헤더 크기값이다. 헤더의 최소 크기는 5 워드이며 최대 크기는 15 워드이다. 따라서 최솟값은 20바이트, 최댓값은 60바이트가 되며, 헤더에 선택 값을을 위해 최대 40 바이트가 더 추가될 수 있다. 데이터 오프셋이라는 명칭은 이것이 실제 데이터 상에서의 TCP 세그먼트의 시작 위치의 오프셋이기 때문에 붙여졌다.

Reserved (3 비트): 미래에 사용하기 위해 남겨둔 예비 필드이며 0으로 채워져야 한다.

Flags (9 bits) (혹은 Control bits): 9개의 1-비트 플래그를 포함

NS (1 비트) – ECN-nonce 은폐 보호(RFC 3540에 의해 헤더에 추가).

CWR (1 비트) – 혼잡 윈도 축소(Congestion Window Reduced) 플래그는 송신측 호스트에 의해 설정되는 것으로, 호스트가 ECE 플래그가 포함된 TCP 세그먼트를 수신했으며 혼잡 제어 메커니즘에 의해 응답했음을 알리는 역할을 한다(RFC 3168에 의해 헤더에 추가).

ECE (1 비트) – ECN-Echo는 다음을 나타낸다.

SYN 플래그가 (1)로 설정된 경우, TCP 상대가 명시적 혼잡 통지(Explicit Congestion Notification, ECN)가 가능함을 의미한다.

SYN 플래그가 (0)으로 해제된 경우, IP 헤더 셋에 혼잡 경험(Congestion Experienced) 플래그가 설정된 패킷이 정상적인 전송 중에 수신되었다는 것을 의미한다(RFC 3168에 의해 헤더에 추가).

URG (1 비트) – Urgent pointer 필드의 값이 유효함을 나타낸다.

ACK (1 비트) – Acknowledgment 필드의 값이 유효함을 나타낸다. 클라이언트가 보낸 최초의 SYN 패킷 이후에 전송되는 모든 패킷은 이 플래그가 설정되어 있어야 한다.

PSH (1 비트) – 푸시 기능. 수신 애플리케이션에 버퍼링된 데이터를 푸시해 줄지 여부를 질의하는 역할을 한다.

RST (1 비트) – 커넥션 리셋

SYN (1 비트) – 동기화 시퀀스 번호. 양쪽이 보낸 최초의 패킷에만 이 플래그가 설정되어 있어야 한다. 다른 일부 플래그들의 의미가 이 플래그의 값에 따라 바뀌며, 일부 플래그들은 이 플래그가 설정되어 있을 때만 유효하고, 또 다른 일부 플래그들은 이 플래그가 해제되어 있을 때에만 유효하다.

FIN (1 비트) – 남은 송신측 데이터 없음

Window size (16 비트): 수신 윈도의 크기. 해당 세그먼트의 송신측이 현재 수신하고자 하는 윈도 크기(기본 단위는 바이트). acknowledgment 필드의 시퀀스 번호보다 큰 값이어야 한다.

Checksum (16 비트): 헤더 및 데이터의 에러 확인을 위해 사용되는 16 비트 체크섬 필드

Urgent pointer (16 비트): URG 플래그가 설정된 경우, 이 16 비트 필드는 시퀀스 번호로부터의 오프셋을 나타낸다. 이 오프셋이 마지막 긴급 데이터 바이트를 가리킨다.

Options (가변 0–320 비트, 32의 배수): 이 필드의 길이는 데이터 오프셋 필드에 의해 결정된다. 이 부분은 Option-Kind (1 바이트), Option-Length (1 바이트), Option-Data (가변) 이렇게 최대 3개의 필드로 구성될 수 있다. Option-Kind 필드는 옵션의 종류를 나타내며, 세 가지 필드 중 유일하게 필수값이다. 옵션의 종류에 따라 나머지 두 개의 필드가 설정될 수 있다. Option-Length 필드는 옵션의 전체 길이를 나타내며, Option-Data 필드는 적용 가능한 경우 해당 옵션의 값을 나타낸다. 예를 들어, Option-Kind 바이트 값이 0x01인 경우 이는 패딩의 용도로만 사용되는 옵션없음(No-Op) 옵션을 의미하며, 이 때에는 뒤따라 오는 Option-Length나 Option-Data 값이 존재하지 않는다. Option-Kind 바이트 값이 0인 경우 이는 옵션종료(End Of Options) 옵션을 의미하며, 전자와 마찬가지로 뒤따라 오는 추가 옵션 필드가 없다. Option-Kind 바이트 값이 0x02인 경우 이것은 최대 세그먼트 크기(Maximum Segment Size) 옵션을 의미하며, 그 뒤에는 MSS 필드의 길이값(0x04여야 함)이 따라오게 된다. 이 길이값은 Option-Kind와 Option-Length를 포함한 주어진 옵션 필드의 전체의 길이를 나타내는 것이다. 따라서 MSS 값은 일반적으로 2 바이트로 표현되며, 해당 필드의 길이는 4 바이트(kind와 length의 2바이트를 더한 값)가 된다. 실제 예를 들어 설명하면, 0x05B4라는 값을 갖는 MSS 옵션 필드는 (0x02 0x04 0x05B4)의 형태로 TCP 옵션 섹션에 나타날 것이다.

일부 옵션은 SYN 플래그가 설정되어 있을 때에만 송신된다. 이러한 옵션은 아래에 [SYN]으로 표시되어 있다. Option-Kind 및 기본 Option-Length는 (Option-Kind, Option-Length)으로 표시되었다.

0 (8 비트) – End of options list

1 (8 비트) – No operation (NOP, Padding) 이것은 속도 향상을 위해 옵션 필드를 32 비트 길이에 맞추기 위해 사용될 수 있다.

2,4,SS (32 비트) – Maximum segment size (최대 세그먼트 크기 참조) [SYN]

3,3,S (24 비트) – Window scale (윈도 조정 참조) [SYN][5]

4,2 (16 비트) – Selective Acknowledgement permitted. [SYN] (선택적 확인응답 참조)[6]

5,N,BBBB,EEEE,... (variable bits, N is either 10, 18, 26, or 34)- Selective ACKnowledgement (SACK)[7] 이 첫 2 바이트 뒤에는 선택적 확인응답을 받는 1-4개 블럭의 리스트가 따라오게 되며, 이들은 32 비트 시작/종료 포인터로 구분된다.

8,10,TTTT,EEEE (80 비트)- Timestamp and echo of previous timestamp (see TCP 타임스탬프 참조)[8]

14,3,S (24 비트) – TCP Alternate Checksum Request. [SYN][9]

15,N,... (가변 비트) – TCP Alternate Checksum Data.

(이외의 옵션들은 더이상 사용되지 않거나, 시험용이거나, 아직 표준화되지 않았거나, 또는 할당되지 않은 것들임)

Padding: TCP 헤더 패딩은 TCP 헤더의 종료 지점과 데이터의 시작 지점을 32 비트 단위 길이에 맞추기 위해 사용된다. 패딩의 값은 0이다.

3.TCP 프로토콜의 작동

 TCP 프로토콜의 작동은 크게 세 가지 흐름으로 구분한다.

1)     연결 생성 (Connection establishment)

2)     자료 전송 (Data transfer)

3)     연결 종료 (Connection termination)

연결할 때, 3 way handshaking을 진행한다.

신뢰성 있는 연결이 생성되어야 하며, 그 후 자료를 전송하고, 마지막으로 연결을 종료하면서 할당된 자원을 반납한다.

연결 생성

연결을 생성하기 위해, 3방향 핸드셰이크를 사용한다.

SYN: 클라이언트가 서버에게 SYN 메시지를 보낸다. 이 메시지에 포함된 시퀀스 번호는 클라이언트가 임의로 설정한 값 A.

SYN-ACK: 서버가 클라이언트에게 SYN-ACK 메시지로 응답한다. 이 메시지에 포함된 시퀀스 번호는 서버가 임의로 설정한 값 B, 응답 번호는 (A + 1).

ACK: 클라이언트가 서버에게 ACK 메시지를 보낸다. 이 메시지에 포함된 응답 번호는 (B + 1).

연결 종료

연결을 종료하기 위해, 4방향 핸드셰이크를 사용한다.              

1)     클라이언트가 연결을 종료하겠다는 FIN플래그를 전송한다.

2)     서버는 일단 확인메시지를 보내고 자신의 통신이 끝날때까지 기다리는데 이 상태가 TIME_WAIT상태다.

3)     서버가 통신이 끝났으면 연결이 종료되었다고 클라이언트에게 FIN플래그를 전송한다.

4)     클라이언트는 확인했다는 메시지를 보낸다.

4. TCP/IP 기반의 프로토콜

HTTP

HTTP(Hypertext Transfer Protocol)는 인터넷상에서 데이터를 주고 받기 위한 서버/클라이언트 모델을 따르는 프로토콜이다. HTTP는 어떤 종류의 데이터든지 전송할 수 있도록 설계돼 있다. HTTP로 보낼 수 있는 데이터는 HTML문서, 이미지, 동영상, 오디오, 텍스트 문서 등 여러종류가 있다.

FTP

서버와 클라이언트 사이의 파일 전송을 하기 위한 프로토콜이다.

SMTP

일반적으로 전자 메일 전송을위한 표준 프로토콜이다.

RTP

RTP(Real-time Transport Protocol)는 실시간 음성과 영상 및 데이터를 IP 네트워크로 전송하는 표준 프로토콜입니다.

RTP는 IETF RFC 3350 A Transport Protocol for Real-Time Applications 권고 안에서 정의하고 있습니다.

RTP는 RTCP(Real-time Control Protocol)를 이용하여서 데이터의 전달 상황을 감시 및 최소한의 제어 기능과 미디어 식별 등을 제공하고 있습니다.

4. TCP 패킷의 흐름제어, 오류제어, 혼잡제어

포스팅이 너무 길어져서 오류제어, 흐름제어, 혼잡제어는 포함하지 않았습니다.

아래 링크에 정리가 잘 되어 있으니 궁금하신 분들은 참고해주세요.

evan-moon.github.io/2019/11/22/tcp-flow-control-error-control/

출처: ko.wikipedia.org/wiki/%EC%A0%84%EC%86%A1_%EC%A0%9C%EC%96%B4_%ED%94%84%EB%A1%9C%ED%86%A0%EC%BD%9C

문제링크:www.acmicpc.net/problem/2606

기본적인 bfs, dfs 문제입니다.

vector를 통해서 양방향 그래프를 구현하고 완전탐색을 통해서 연결된 갯수를 파악하면 되는 문제입니다.

기본중에 기본문제입니다. 

이제 알고리즘을 입문하시는 분들이라면 그냥 코드자체를 외우듯이 이해하시면 될 것 같습니다.

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

int n = 0, m = 0, result = 0;
vector <int> vec[101];
bool visited[101] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		vec[t1].push_back(t2);
		vec[t2].push_back(t1);

	}

	queue <int> que;
	visited[1] = 1;
	que.push(1);

	while (!que.empty()) {
		int num = que.front();
		que.pop();

		for (int i = 0; i < vec[num].size(); i++) {
			int next = vec[num][i];
			if (visited[next] == 1) continue;
			que.push(next);
			visited[next] = 1;
			result++;
		}
	}

	cout << result << endl;
	return 0;
}