24.02.22 백준,KEYWORD

백준

2587 대표값2

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	vector<int> num_arr(5);
	int sum = 0;
	for (int i = 0; i < 5; ++i)
	{
		int tmp;
		cin >> tmp;
		sum += tmp;
		num_arr[i] = tmp;
	}
	sort(num_arr.begin(), num_arr.end());
	cout << sum/5 <<"\\n" << num_arr[2];
	
	return 0;
}

• sort 정렬로 쉽게 풀 수 있는 문제
• 들어오는 횟수가 정해져있기 때문에 더 쉽게 풀 수 있다.

25305 커트라인

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	vector<int> num_arr;
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; ++i)
	{
		int tmp;
		cin >> tmp;
		num_arr.push_back(tmp);
	}
	sort(num_arr.begin(), num_arr.end(),greater<int>());
	cout << num_arr[k - 1];
	return 0;
}

• sort 정렬로 쉽게 풀 수 있는 문제
• greater<void>() 를 쓰면 내림차순으로 정렬할 수 있다.

18870 좌표 압축

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	vector<long long> x1;
	vector<long long> x2;
	int n;
	cin >> n ;
	for (int i = 0; i < n; ++i)
	{
		long long tmp;
		cin >> tmp;
		x1.push_back(tmp);
		x2.push_back(tmp);
	}
	sort(x1.begin(), x1.end());
	x1.erase(unique(x1.begin(), x1.end()), x1.end());
	for (int i = 0; i < n; ++i)
	{
		cout << lower_bound(x1.begin(), x1.end(), x2[i]) - x1.begin() << " ";
	}
	return 0;
}

• 시간초과로 인해서 머리를 싸맸던 문제
• lower_bound라고하는 함수를 배워서 사용했다.
• sort, unique, erase, lower_bound를 사용하면 조금 더 쉽게 풀 수 있을 것 같다.

C++

unique함수와 erase함수를 통한 문자열 중복제거

• unique는 연속된 중복 원소를 vector의 제일 뒷 부분으로 쓰레기 값으로 보낸다.
• erase로 뒤에 붙은 쓰레기 값을 제거해주면 벡터의 중복원소를 제가하는데 성공한다.
• 필요한 라이브러리

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

• erase

v.erase(unique(v.begin(), v.end()),v.end());

lower_bound, upper_bound

• 이진 탐색으로 원소를 탐색하는 함수 제공.
• 찾으려는 key값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장 하는지 찾기위한 함
• 오름차순 정렬되어 있어야 한다.

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

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;

    // 결과 -> lower_bound(6) : 5

	return 0;
}

• lower_bound의 반환형은 iterator이므로 실제로 몇 번째 인덱스인지 알고 싶다면, 위 코드와 같이 lower_bound값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 된다.
• 벡터의 경우 arr.begin()을 빼면 된다.

KEYWORD

OSI 7 계층

• 네트워크에서 통신이 일어나는 과정을 7단계로 나눈 것을 말한다.

계층을 나눈 이유

• 통신이 일어나는 과정을 단계별로 파악할 수 있기 때문이다.
• 흐름을 한눈에 알아보기 쉽고, 이해하기 쉽고, 7단계 중 특정한 곳에 이상이 생기면 다른 단계의 장비 및 소프트웨어를 건들이지 않고도 이상이 생긴 단계만 고칠 수 있다.

OSI 7계층 단계

1계층 - 물리계층(Physical Layer)

• 주로 전기적, 기계적, 기능적인 특성을 이용해서 통신 케이블로 데이터를 전송하게 된다.
• 통신단위는 비트이며 이것은 1과 0으로 나타내어지는, 전기적으로 on,off상태를 의미한다.
• 단지 데이터를 전달만 할뿐 전송하려는(또는 받으려는)데이터가 무엇인지, 어떤 에러가 있는지 등에는 전혀 신경을 쓰지 않는다. 단지 데이터 전기적인 신호로 변환해서 주고받는 기능만 할 뿐이다. 이 계층에 속하는 대표적인 장비는 통신 케이블, 리피터, 허브등이 있다.
• 케이블, 리피터, 허브를 통해 데이터를 전송한다

2계층 - 데이터 링크계층(DataLink Layer)

• 물리계층을 통해 송수신되는 정보의 오류와 흐름을 관리하여 안전한 정보의 전달을 수행할 수 있도록 한다.
• 따라서 통신에서의 오류도 찾아주고 재전송도 하는 기능을 가지고 있다.
• 맥 주소를 가지고 통신한다.
  • MAC 주소(Media Access Control address) : 네트워크 세그먼트의 데이터 링크 계층에서 통신을 위한 네트워크 인터페이스에 할당된 고유 식별자이다.
  • 단 하나의 고유한 주소를 부여해서 통신을 할 수 있도록 만든 일종의 하드웨어 주소다.
  • 영구적이고 전역적인 고유 식별을 위해 고안되었지만 현대의 대부분의 하드웨어의 MAC 주소를 변경할 수 있다. MAC 주소를 변경하는 일은 네트워크 가상화에서 필수적이다. 보안 취약점을 활용하는 과정에도 사용할 수 있는데, 이를 MAC 스푸핑(MAC spoofing)이라고 한다.
• 데이터 링크계층에서 전송되는 단위를 프레임이라고 하고, 대표적인 장비로는 브릿지, 스위치 등이 있다. → 브릿지나 스윗치를 통해 맥주소를 가지고 물리계층에서 받은 정보를 전달한다.
• 데이터 링크 계층은 포인트 투 포인트(Point-to-Point) 간 신뢰성있는 전송을 보장하기 위한 계층으로 CRC 기반의 오류 제어와 흐름 제어가 필요하다. 네트워크 위의 개체들 간 데이터를 전달하고, 물리 계층에서 발생할 수 있는 오류를 찾아 내고, 수정하는 데 필요한 기능적, 절차적 수단을 제공한다.
  • CRC(cyclic redundancy check) 순환 중복 검사 : 네트워크 등을 통해 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식. 데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것임을 알 수 있다.
• 데이터 링크 계층의 가장 잘 알려진 예는 이더넷이다.
• 네트워크 브릿지나 스위치 등이 이 계층에서 동작하며, 직접 이어진 곳에만 연결할 수 있다.
• 프레임에 주소를 부여(MAC - 물리적주소), 에러검출/재전송/흐름제어를 한다.

3계층 - 네트워크 계층(Network Layer)

• 가장 중요한 기능은 라우팅이다.
  • 라우팅 : 데이터를 목적지까지 가장 안전하고 빠르게 전달하는 기능
  • 여기에 사용되는 프로토콜의 종류도 다양하고, 라우팅하는 기술도 다양하다.
• 경로를 선택하고 주소를 정하고 경로에 따라 패킷을 전달해주는 것이 이 계층의 역할이다.
  • 패킷(Packet) : 패킷 또는 네트워크 패킷은 네트워크를 통해 전송되는 형식화된 데이터 덩어리. 즉, 컴퓨터 네트워크에서 데이터를 주고받을 때 정해 놓은 규칙이다.
  • 정보를 보낼 때 특정 형태에 맞추어 보내는것을 의미한다.
• 대표적인 장비는 라우터이다.
• 네트워크 계층은 여러개의 노드를 거칠때마다 경로를 찾아주는 역할을 하는 계층으로 다양한 길이의 데이터를 네트워크들을 통해 전달하고, 그 과정에서 전송 계층이 요구하는 서비스 품질을 제공하기 위한 기능적, 절차적 수단을 제공한다.
• 라우팅, 흐름 제어, 세그멘테이션, 오류 제어, 인터네트워킹 등을 수행한다.
• 데이터를 연결하는 다른 네트워크를 통해 전달함으로써 인터넷이 가능하게 만드는 계층이다.
• 논리적인 주소 구조(IP), 곧 네트워크 관리자가 직접 주소를 할당하는 구조를 가지며, 계층적(hierachical)이다.
• 서브네트워크의 최상위 계층으로 경로를 설정하고, 청구 정보를 관리한다. 개방형 시스템들의 사이에서 네트워크 연결을 설정, 유지, 해제하는 기능을 부여하고, 전송계층 사이에 네트워크 서비스 데이터 유닛(NSDU : Network Service Data Unit)을 교환하는 기능을 제공한다.
• 주소부여(IP), 경로설정(Route)

IP계층

• TCP/IP 상에서 IP 계층이란 네트워크의 주소(IP 주소)를 정의하고, IP 패킷의 전달 및 라우팅을 담당하는 계층이다.
• OSI 7계층모델의 관점에서 보면 IP 계층은 네트워크 계층에 해당한다.
  • 패킷을 목적지까지 전달하는 역할 및 그에 수반되는 기타 역할을 한다.
• IP계층에서는 그 하위계층인 데이터링크 계층의 하드웨어적인 특성에 관계없이 독립적인 역할을 수행한다.
• IP계층 상에 있는 주요 프로토콜
  • 패킷의 전달을 책임지는 IP
  • 패킷 전달 에러의 보고 및 진단을 위한 ICMP
  • 복잡한 네트워크에서 인터네트워킹을 위한 경로를 찾게해주는 라우팅 프로토콜

IP 프로토콜

• TCP/IP 기반의 인터넷 망을 통하여 데이타그램의 전달을 담당하는 프로토콜
• 주요 기능
  • IP 계층에서 IP패킷의 라우팅 대상이 된다.
  • IP 주소 지정
• 주요 특징
  • 신뢰성(에러제어) 및 흐름제어 기능이 전혀없다. → Best-Effort Service
  • 비연결성데이터그램 방식으로 전달되는 프로토콜 → Connectionless
  • 패킷의 완전한 전달(소실, 중복, 지연, 순서바뀜이 없음)을 보장하지 않는다 → Unreliable
  • IP 패킷 헤더 내 수신 및 발신 주소를 포함한다 - IPv4, IPv6 , IP주소
  • IP 헤더 내 바이트 전달 순서 : 최상위 바이트(MSB)를 먼저 보낸다. → Big-endian
  • 경우에 따라, 단편화가 필요하다. → IP 단편화 참조
  • TCP, UDP, ICMP, IGMP 등이 IP 데이타그램에 실려서 전송된다.

4계층 - 전송 계층(Transport Layer)

• 통신을 활성화기 위한 계층이다. 보통 TCP 프로토콜을 이용하며, 포트를 열어서 응용프로그램들이 전송을 할 수 있게 한다. 만약 데이터가 왔다면 4계층에서 해당 데이터를 화나로 합쳐서 5계층에 던져 준다.
• 단대단 오류제어 및 흐름제어. 이 계층까지는 물리적인 계층에 속한다.(TCP/UDP 프로토콜을 사용한다.)
  • 단대단(end-to-end) : 망을 경유한 양 끝 단말간의 종단간 통신을 말한다.
• 양 끝단(end to end)의 사용자들이 신뢰성있는 데이터를 주고 받을 수 있도록 해 주어, 상위 계층들이 데이터 전달의 유효성이나 효율성을 생각하지 않도록 해준다.
• 시퀀스 넘버 기반의 오류 제어 방식을 사용한다.
• 전송 계층은 특정 연결의 유효성을 제어하고, 일부 프로토콜은 상태 개념이 있고(stateful), 연결 기반(connection oriented)이다. 이는 전송 계층이 패킷들의 전송이 유효한지 확인하고 전송 실패한 패킷들을 다시 전송한다는 것을 뜻한다.
• 패킷 생성 및 전송

TCP 프로토콜(Transmission Control Protocol)

• OSI 계층모델의 전송 계층(4계층)에 해당한다.
• 양종단 호스트 내 프로세스 상호 간에 신뢰적인 연결지향성 서비스를 제공한다.
  • IP의 비신뢰적인 최선형 서비스에다가 신뢰적인 연결지향성 서비스를 제공하게된다.
  • 신뢰적인 전송을 보장함으로써, 어플리케이션 구현이 한층 쉬워진다.
• 특징
  1. 신뢰성 있다(Reliable)
     1. 패킷 손실, 중복, 순서바뀜 등이 없도록 보장한다.
     2. TCP 하위계층인 IP 계층의 신뢰성 없는 서비스에 대해 다방면으로 신뢰성을 제공한다.
  2. 연결지향적(Connection-oriented)
     1. 연결 관리를 위한 연결설정 및 연결해제가 필요하다.

UDP 프로토콜(User Datagram Protocol)

• 전송 계층의 통신 프로토콜의 하나(TCP와 대비된다)
  • 신뢰성이 낮은 프로토콜로써 완정성을 보증하지 않으나, 가상회선을 굳이 확립할 필요가 없고 유연하며 효율적 응용의 데이타 전송에 사용된다.
• 특징
  • 비연결성이고, 신뢰성이 없으며, 순서화되지 않은 Datagram 서비스를 제공한다.
    • 확인응답 없음
    • 순서제어 없음
    • 흐름제어 없음
    • 오류제어 거의 없다 - UDP를 사용하는 프로그램 쪽에서 오류제어 기능을 스스로 갖추어야 한다.
  • 실시간 응용 및 멀티캐스팅 가능
    • 빠른 요청과 응답이 필요한 실시간 응용에 적합하다.
    • 여러 다수 지점에 전송 가능하다.(1:多)
  • 헤더가 단순하다
    • UDP는 TCP 처럼 16비트의 포트 번호를 사용하나, 헤더는 고정크기의 8바이트(TCP는 20바이트 사용) 만 사용한다. 즉, 헤더 처리에 많은 시간과 노력을 요하지 않는다.

5계층 - 세션 계층(Session Layer)

• 데이터가 통신하기 위한 논리적인 연결을 말한다.
• 세션 설정, 유지, 종료, 전송 중단시 복구 등의 기능이 있다.
• 세션 계층은 양 끝단의 응용 프로세스가 통신을 관리하기 위한 방법을 제공한다.
  • 동시 송수신 방식(duplex), 반이중 방식(half-duplex), 전이중 방식(Full duplex)의 통신과 함께, 체크 포인팅과 유휴, 종료, 다시 시작 과정등을 수행한다.
• 이 계층은 TCP/IP 세션을 만들고 없애는 책임을 진다.
• 통신하는 사용자들을 동시화하고 오류복구 명령들을 일괄적으로 다룬다.
• 통신을 하기 위한 세션을 확립/유지/중단 한다.

6계층 - 표현 계층(Presentation Layer)

• 데이터 표현이 상이한 응용 프로세스의 독립성을 제공하고, 암호화 한다.
• 표현 계층은 코드 간의 번역을 담당하여 사용자 시스템에서 데이터의 형식상 차이를 다루는 부담을 응용 계층으로부터 덜어준다. MIME 인코딩이나 암호화등의 동작이 이 계층에서 이루어진다.
  • EBCDIC로 인코딩된 문서 파일을 ASCII로 인코딩된 파일로 바꿔 주는 것
• 해당 데이터가 TEXT인지, 그림인지 구분하는것이 표현 계층의 몫이다.
• 사용자의 명령어를 완성 및 결과 표현. 포장/압축/암호화

7계층 - 응용 계층(Application Layer)

• 최종 목적지로서 HTTP, FTP,SMTP, POP3, IMAP, TELNET 등과 같은 프로토콜이 있다.
• 해당 통신 패킷들은 방금 나열한 프로토콜에 의해 모두 처리되며 우리가 사용하는 브라우저나, 메일 프로그램은 프로토콜을 보다 쉽게 사용하게 해주는 응용 프로그램이다. 한마디로 모든 통신의 양 끝단은 HTTP와 같은 프로토콜이지 응용프로그램이 아니다.
• 응용 계층은 응용 프로세스와 직접 관계하여 일반적인 응용 서비스를 수행한다.
• 일반적인 응용 서비스는 관련된 응용 프로세스들 사이의 전환을 제공한다.
• 네트워크 소프트웨어 UI 부분, 사용자의 입출력(I/O)부분

HTTP 프로토콜(HyperText Transfer Protocol)

• 웹 상에서 웹서버 및 웹브라우저 상호 간의 데이터 전송을 위한 응용 계층 프로토콜
• 처음에는, www 상의 하이퍼텍스트 형태의 문서를 전달하는데 주로 이용했다.
• 현재에는, 이미지,비디오,음성 등 거의 모든 형식의 데이터를 전송 가능하다.

1. 요청 및 응답의 구조
   1. 동작형태가 클라이언트/서버 모델로 동작
2. 메세지 교환 형태의 프로토콜
   1. 클라이언트와 서버 간에 ‘HTTP 메세지’를 주고받으며 통신한다
   2. HTTP의 응답 및 요청 메세지를 구성
   3. HTTP 메세지 내 헤더 항목들
3. 트랜잭션 중심의 비연결성 프로토콜
   1. 종단간 연결이 없다(Connectionless)
   2. 이전의 상태를 유지하지 않는다(stateless)
4. 전송계층 프로토콜 및 사용 포트 번호
   1. 전송 계층 프로토콜 : TCP
   2. 사용 포트 번호 : 80번

TCP/IP Layer

• TCP/IP 프로토콜 통신 과정에 초점을 맞추어 OSI 7계층을 좀 더 단순화 시킨 계층을 의미한다.
• TCP/IP 4계층은, 애플리케이션 계층, 전송 계층, 인터넷 계층, 네트워크 접근 계층으로 이루어져 있다.
• 데이터 전송 시 ,데이터는 상위 계층에서 하위 계층으로 이동하고, 계층 이동마다 필요한 정보(헤더)가 추가된다. - 캡슐화 라고 한다.
• 데이터 수신 시, 데이터는 하위 계층에서 상위 계층으로 이동하고, 계층 이동마다 추가된 헤더를 읽고 알맞은 행동을 취한 후, 헤더를 제거한다. - 역캡슐화 라고한다.

1계층 - 네트워크 액세스 계층

• 데이터를 전기신호로 변환한 뒤, 물리적 주소인 MAC를 사용해, 알맞은 기기로 데이터를 전달하는 계층이다.
• 프로토콜로는 Ethernet, Wi-Fi, PPP, Token Ring과 같은 프로토콜이 사용된다.

2계층 - 인터넷 계층

• 패킷을 최종 목적지까지 라우팅하는 계층이다.
• 프로토콜로는 IP, ARP, ICMP, RARP, OSPF가 사용된다.

3계층 - 전송 계층

• 통신 노드 간 신뢰성 있는 데이터 전송을 보장하는 계층이다.
• 역캡슐화 과정에서, 포트 번호를 사용해 데이터를 정확한 애플리케이션에 전달하는 역할도 한다.
  • 네트워크 액세스 계층과 인터넷 계층을 통해, 데이터가 목적지 기기까지 정상적으로 도착했다면, 전송 계층은 포트 번호를 사용해, 데이터를 목적지 기기 내 적절한 애플리케이션으로 전달한다.
• 프로토콜로는 TCP, UDP, RTP, RTCP가 있다.

4계층 - 애플리케이션 계층

• 사용자와 가장 가까운 계층으로, 사용자-소프트웨어 간 소통을 담당하는 계층이다.
• 애플리케이션을 실행하기 위한 데이터 형식이 작성된다.
• 프로토콜로는 HTTP, HTTPS, FTP, SSH, TELNET, DNS, SMTP가 있다.

클라이언트 서버 모델

• 서비스 요청자인 클라이언트와 서비스 자원의 제공자인 서버간에 작업을 분리해주는 분산 애플리케이션 구조이자, 네트워크 아키텍처를 나타낸다. 웹 시스템도 확장된 ‘클라이언트 서버 시스템’으로 분류되나, 일반적으로 클라이언트 서버 시스템이라고 하면 웹 시스템이 나오기 이전의, 사용자 PC에는 클라이언트가 설치되어 화면을 처리하고 서버에서는 자료를 처리하는 시스템을 일컫는다.
• 클라이언트는 서비스를 사용하는 사용자 혹은 사용자 혹은 사용자의 단말기를 가리키는 말이다.
• 서버란 서비스를 제공하는 컴퓨터이며, 다수의 클라이언트를 위해 존재하기 때문에 일반적으로 매우 큰 용량과 성능을 가지고 있었다. 그러나 웹 2.0에서는 클라이언트이자 동시에 서버인 환경이 많아지면서 변화가 일고 있다.
• 클라이언트 - 서버 구조로 된 네트워크 프로그램을 작성하거나, 특정 시스템이 클라이언트-서버 구조로 만들어져 있다는 것은 클라이언트와 서버가 각자의 역할에 맞게 구성됨을 말한다. 대표적인 예로는 월드 와이드 웹이 있다.