1. 아침 문제 풀이
1. 1966번 - 프린터 큐 - 2023.05.18
import sys
from collections import deque
testcase = int(sys.stdin.readline())
for _ in range(testcase) :
N, M = map(int, sys.stdin.readline().split())
priorty = list(map(int, sys.stdin.readline().split()))
queue = deque()
for i in range(N) :
queue.append((i, priorty[i])) # 원래 위치와 중요도를 같이 큐에 넣어준다.
count = 0
while queue :
flag = True #True일 경우 출력 가능 / False일 경우 재배치
idx ,cur = queue.popleft()
for i in range(len(queue)):
if cur < queue[i][1] : # 현재 우선순위보다 큰 우선순위가 존재하면
flag = False
queue.append((idx, cur))
break
if flag : # 출력가능하면
count += 1
if idx == M : #현재 문서가 M번에 있던 문서일 경우
break
print(count)
큐의 성질인 FIFO를 이해했다면 풀 수 있는 문제였다.
단, 중요한 것은 처음에 주어졌던 인덱스가 필요했어서 이를 저장해두어야 할 필요가 있었다.
그래서 큐에 우선순위와 인덱스를 같이 튜플로 저장해주었다.
이 문제를 통해 하나의 자료구조에 하나의 데이터만 그동안 쭉 넣어왔는데 이를 응용하여 필요한 데이터를 같이 넣어주는 연습을 하는 계기가 되었다.
2. 14425번 - 문자열 집합 - 2023.05.19
import sys
N, M = map(int, sys.stdin.readline().split())
S = {} # 문자열의 집합 -> 딕셔너리로 저장
for _ in range(N) :
S[sys.stdin.readline().strip()] = 1
count = 0
for _ in range(M) :
t = sys.stdin.readline().strip()
if t in S : #집합에 포함되어 있는지 확인
count += 1
print(count)
쉬워보여서 문제를 대충 읽었다가 틀릴뻔한 문제..!
아무리 쉬워 보여도 문제는 똑바로 읽자❗️
2. 클라이언트-서버 모델 (client-server model)
서비스 요청자인 클라이언트와 서비스 자원의 제공자인 서버 간에 작업을 분리해주는 분산 애플리케이션 구조이자 네트워크 아키텍처
- 한 개의 server 프로세스와 한 개 이상의 client 프로세스로 구성
- server process = 연결되기를 기다리는 프로세스
- client process = 연결을 시작하는 프로세스
- Transaction : 클라이언트와 서버가 수행하는 일련의 단계
- 클라이언트 → 서버 로 한 개의 Request를 보낸다.
- 서버 : Request를 해석하고 적절한 방법으로 응답을 할 수 있도록 한다.
- 서버 → 클라이언트로 Response를 보낸다.
- 클라이언트 : Response을 받고 이를 처리한다.
Server : https://ko.wikipedia.org/wiki/서버
🗒️ 웹 서버 개념 정리 🗒️
1. 웹 브라우저와 같은 클라이언트로 부터 HTTP 요청을 받아들이고 HTML 문서와 같은 웹페이지를 반환하는 컴퓨터 프로그램
2. 위의 기능을 제공하는 컴퓨터 프로그램을 실행하는 컴퓨터
https://ko.wikipedia.org/wiki/웹_서버
🗒️ 프록시 서버 개념 정리 🗒️
클라이언트가 자신을 통해서 다른 네트워크 서비스에 간접적으로 접속할 수 있게 해 주는 컴퓨터 시스템이나 응용 프로그램
Proxy : 서버와 클라이언트 사이에 중계기로서 대리로 통신을 수행하는 것
https://ko.wikipedia.org/wiki/프록시_서버
3. 네트워크
1. 호스트
컴퓨터 네트워크에 연결된 컴퓨터나 기타 장치
네트워크 주소가 할당된 네트워크 노드 = 네트워크 공간 상에 있는 모든 장치(device) 호스트
호스트에게 네트워크는 또다른 I/O 디바이스로 Network Adapter는 물리적인 인터페이스 제공
< 참고 > https://ko.wikipedia.org/wiki/호스트_(네트워크)
2. DMA
네트워크에서 수신한 데이터는 I/O와 메모리 버스를 거쳐서 adapter → memory로 DMA 전송으로 복사된다.
Direct Memory Access
: 특정 하드웨어 하위 시스템이 CPU와 독립적으로 메인 시스템 메모리에 접근할 수 있게 해주는 컴퓨터 시스템의 기능
장치 컨트롤러가 데이터의 한 블록을 이동시키는데 이 과정에서 DMA로 인해 CPU의 개입이 필요없게 된다.
< 참고 > https://ko.wikipedia.org/wiki/직접_메모리_접근
※ PIO (Programmed Input/Output)
: 네트워크 어댑터나 ATA 기억 장치와 같은 주변 기기와 중앙 처리 장치(CPU) 사이에서 데이터를 주고받는 방식
위의 DMA의 반대 개념이다.
3. 네트워크 계층
1. OSI 7계층
OSI (Open Systems Interconnection Reference Model)은 국제표준화기구(ISO)에서 개발한 모델로, 컴퓨터 네트워크 프로토콜 디자인과 통신을 계층으로 나누어 설명한 것, 네트워크 동작을 이해하기 위해 배우는 이론적인 모델
< 참고 > https://ko.wikipedia.org/wiki/OSI_모형
계층 | 설명 |
1계층 : 물리 (Physical, 물리계층) |
🔹 프레임 내부의 각 비트를 한 노드에서 다음 노드로 이동 🔹 하드웨어 전송 기술 (꼬임쌍선, 단일 모드 광케이블) |
2계층 : 링크 (Link, 데이터링크계층) |
🔹 경로 상의 한 노드에서 다른 노드로 패킷을 이동 = 전체 프레임을 한 네트워크 요소에서 이웃 네트워크 요소로 이동 = 포인트 투 포인트(Point to Point) 간 신뢰성있는 전송을 보장 🔹 MAC 주소 : 물리적 주소 🔹 Ethernet(이더넷) 🔹 계층 패킷 :frame |
3계층 : 네트워크 (network, 네트워크계층) |
🔹 한 호스트에서 다른 호스트로 데이터그램을 라우팅 하는 역할 전송 계층이 요구하는 서비스 품질(QoS)을 제공하기 위한 기능적, 절차적 수단을 제공 🔹 IP 프로토콜 : IP 데이터그램의 필드를 정의하며 종단 시스템과 라우터가 이 필드에 어떤게 동작하는지를 정의 🔹 라우팅 프로토콜 : 출발지와 목적지 사이에서 데이터그램이 이동하는 경로 결정 🔹 계층 패킷 : datagram |
4계층 : 트랜스포트 (transport, 전송계층) |
🔹 양 끝단(End to end)의 사용자들이 신뢰성있는 데이터를 주고 받을 수 있도록 해 주어, 상위 계층들이 데이터 전달의 유효성이나 효율성을 생각하지 않도록 해준다. 🔹 TCP 1. 애플리케이션에게 연결 지향형 서비스 제공 2. 메세지 전달 보장 3. 혼잡제어, 흐름 제어 기능 제공 🔹 UDP 1. 애플리케이션에게 비연결 지향형 서비스 제공 2. 위의 TCP와 다르게 많은 기능을 제공하지 않는 간단한 서비스 🔹 계층 패킷 : segment |
5계층 : 세션 (session, 세션계층) |
1. 데이터 교환의 경계와 동기화를 제공 2. 연결 세션의 체킹 포인트와 회복 방법을 세우는 수단 3. 동시 송수신 방식(duplex), 반이중 방식(half-duplex), 전이중 방식(Full Duplex) |
6계층 : 프레젠테이션 (presentation, 표현계층) |
1. 통신하는 어플리케이션들이 교환되는 데이터의 의미를 해석하도록 돕는 서비스를 제공 2. 데이터의 압축과 암호화 기능 3. 애플리케이션 프로그램이 데이터가 표현/저장되는 내부 포맷을 걱정하지 않아도 되도록 컴퓨터마다 다른 포맷을 사용해도 서로 통신이 되도록 데이터의 포맷을 변경시키는 역할을 수행 |
7계층 : 애플리케이션 (application, 응용계층) |
🔹 HTTP, FTP, SMTP와 같은 많은 프로토콜 포함 🔹 DNS(Domain Name Server) : 도메인 → ip주소 변환 🔹 애플리케이션 프로토콜은 한 종단 시스템에 있는 애플리케이션이 다른 종단 시스템에 있는 애플리케이션과 정보 패킷(Message)을 교환할 때 사용 |
2. TCP/IP 모델
계층이 많을 수록 일은 세분화되지만 결론적으로 더 복잡해 지고 처리 속도가 늦어질 수 밖에 없다.
따라서 실제로 인터넷 상에서 구현된 모델은 TCP/IP 모델이다.
4. Ethernet
컴퓨터 네트워크 기술의 하나로, 일반적으로 LAN, MAN 및 WAN에서 가장 많이 활용되는 기술 규격
▶ 물리 계층 : 신호, 배선 형식 정의
▶ 데이터링크 계층 : MAC 패킷과 프로토콜의 형식 정의
< 참고 > https://ko.wikipedia.org/wiki/이더넷
- LAN (Local Area Network)
- 가까운 지역을 한데 묶는 컴퓨터 네트워크 (근거리 통신망)
- 이더넷, wifi
- 이더넷 어댑터는 48비트 길이의 고유의 MAC 주소를 가지고 이를 이용해 상호간에 데이터를 주고 받을 수 있도록 한다.
- MAC (Media Access Control Address)
- 데이터링크 계층에서 통신을 위한 네트워크 인터페이스에 할당된 고유 식별자
- 이더넷 하드웨어 주소(Ethernet hardware address, EHA), 하드웨어 주소, 물리 주소라고도 한다.
- 🔗 https://ko.wikipedia.org/wiki/MAC_주소
- MAC (Media Access Control Address)
- Hub(허브)
- 여러 대의 컴퓨터, 네트워크 장비를 연결하는 장치이다.
- 한대의 허브를 중심으로 여러대의 컴퓨터와 네트워크장비가 마치 별 모양으로 서로 연결되며, 같은 허브에 연결된 컴퓨터와 네트워크 장비는 모두 상호 간에 통신할 수 있게 된다.
- 각 포트에서 수신한 모든 비트를 종속적으로 다른 모든 포트로 복사
- 즉, 허브로 연결된 네트워크에서는 한 컴퓨터에서 주고받는 데이터가 같은 허브에 연결된 다른 모든 컴퓨터에 전달된다.
- 브릿지형 이더넷
- 허브보다 더 높은 전선의 대역폭을 가지고 이더넷 세그먼트를 연결한다.
5. Router
컴퓨터 네트워크 간에 데이터 패킷을 전송하는 네트워크 장치
패킷의 위치를 추출하여, 그 위치에 대한 최적의 경로를 지정하며, 이 경로를 따라 데이터 패킷을 다음 장치로 전달
최적의 경로는 일반적으로는 가장 빠르게 통신이 가능한 경로
서로 다른 네트워크 간에 중계 역할을 해주는 장치
< 참고 > https://ko.wikipedia.org/wiki/라우터
- WAN (Wide Area Network)
- 2개 이상의 논리적 하위망 연결
- 비호환성 LAN을 라우터로 연결 = 네트워크 간 연결 구성
- internet은 매우 다르고 비호환적인 기술을 갖는 여러 가지 LAN과 WAN들로 이루어져 있다.
- 여러 가지 네트워크 간의 차이를 줄이기 = 프로토콜 소프트웨어 계층
- 명명법(Naming Scheme)
- 호스트의 주소를 위한 통일된 포맷 정의
- 각 호스트는 자신을 유일하게 식별하는 internet 주소가 최소한 한개가 할당된다.
- 전달 기법(Delivery Mechanism)
- 패키징
- 패킷을 보낼때 (헤더 + 데이터)로 헤더를 붙여서 보낸다.
- 캡슐화(encapsulation)
- 명명법(Naming Scheme)
6. Internet
- IPv4
- 32비트 IP주소 (32bit unsigned 정수)
- 패킷 헤더에 포함된 IP주소는 Big-endian Order 순서로 정의
- 인터넷 호스트들이 서로 다른 호스트 바이트 순서를 가질 수 있기 때문에
- 최상위 바이트(MSB)를 먼저 보내고, 최하위 바이트(LSB)는 맨나중에 보냄
- 🔗 http://www.ktword.co.kr/test/view/view.php?nav=2&no=2353&sh=빅+엔디안
- 사람이 보기 편한 방식 = Dotted Decimal
- 10.10.10.10 처럼 10진수로 .을 통해 구분하는 형식으로 제시된다.
- Internet Domain Name
- 도메인 이름
- 인터넷에서 이름을 정의할 수 있는 공간
- 🔗 http://www.ktword.co.kr/test/view/view.php?m_temp1=385&id=433
- 단어들의 배열로 .점으로 구분된다
- (ex) google.com
- 도메인 이름
- DNS (Domain Name System)
- 도메인과 IP 주소의 mapping 관리
- IP 주소와 Host 이름을 서로 연결시켜주는 분산 구조화된 트리구조
- 🔗 http://www.ktword.co.kr/test/view/view.php?nav=2&no=264&sh=DNS
- NSLOOKUP : 도메인으로 IP주소 알아보기
- hostname : IP 주소 알아보기
7. socket
- 인터넷 클라이언트와 서버는 연결(connection)을 통해서 바이트 스트림을 주고받는다.
- 두개의 프로세스를 연결 (point ot point)
- 데이터가 양방향으로 동시에 흐를 수 있다 (full - duplex)
- 소스 프로세스가 보낸 바이트 스트림이 보낸 것과 동일한 순서로 목적지프로세스에 수신된다.
- 소켓
- 연결의 종단점 = point to point에서 point라고 생각하면 된다.
- 소켓 주소 = 인터넷 주소 : 16비트 정수 포트
- 연결은 두 개의 종단점의 소켓 주소에 의해 유일하게 식별
- tuple = (cliaddr : cliport, servaddr : servport)
8. socket interface
1. 소켓 구조체
- sin_family : 주소 체계를 저장하는 필드
- 이 필드를 사용하는 이유 : 앞으로 하나의 프로토콜 체계 안에 여러 주소 체계가 사용될 수 있을 것이라는 예상했다.
- sin_port : 포트 정보 저장
- sin_addr : 주소 저장
- sin_zero : 사용하지 않는 필드 = 0으로 채워준다.
- https://jhnyang.tistory.com/261
2. socket 함수
소켓 식별자를 생성하기 위한 함수
- domain : 어떤 영역에서 통신할 것인지에 대해 지정
- AF_UNIX : 프로세스끼리 통신할 때
- AF_INET : IPv4
- AF_INET6 : IP6
- type : 어떤 서비스 타입의 소켓을 생성할 것인지
- SOCK_STREAM : TCP를 사용할 때
- SOCK_DGRAM : UDP를 사용할 때
- SOCK_RAW : tcp나 udp를 사용하지 않고 바로 IP계층을 사용할 때
- protocol : 소켓에 사용할 프로토콜
- IPPROTO_TCP : TCP 방식
- IPPROTO_UDP : UDP 방식
- 0 : type에서 미리 정해진 경우
3. connection 함수
클라이언트가 이 함수를 호출하여 서버와 연결을 만든다.
4. bind 함수
서버가 클라이언트와 연결을 수립하기 위해 사용되는 함수
커널에게 addr 에 있는 서버의 소켓 주소를 소켓 식별자 sockfd와 연결하라고 물어본다.
서버의 포트번호를 고정해준다.
- sockfd : socket() 함수에서 리턴받은 소켓 디스크립터
- file descriptor : 특정한 파일에 접근하기 위한 추상적인 키
- Unix OS에서 네트워크 소켓과 같은 파일이나 기타 입력/출력 리소스에 액세스하는 데 사용되는 추상표현
- 시스템으로 부터 할당받은 파일이나 소켓을 대표하는 정수 = 할당받은 포트번호
- https://code4human.tistory.com/123
- https://ko.wikipedia.org/wiki/파일_서술자
- addr : 서버의 소켓 주소
- addrlen : 주소의 길이
5. listen 함수
client : 연결을 요청하는 능동적인 개체
server : 연결 요청을 기다리는 수동적인 개체
기본적으로 socket함수로 만든 식별자는 능동 소켓으로 생각한다.
그러므로 listen 함수를 이용하여 server 소켓을 수동적인 소켓으로 바꿔주어야 한다 = 듣기 소켓
듣기 소켓 = 클라이언트로부터의 연결 요청을 수락할 수 있다.
즉, 외부의 컴퓨터에 요청이 왔을 때 수락할 수 있게 대기 상태로 들어가는 함수
- sockfd : 서버의 소켓 디스크립터
- backlog : 연결 대기열의 크기 지정
6. accept 함수
서버가 이 함수를 호출하여 클라이언트로부터 연결 요청을 기다린다.
- sockfd : 서버의 소켓 디스크립터
- addr : 클라이언트 주소 정보를 담은 구조체
- addrlen : 위의 구조체 길이
9. 호스트와 서비스 변환
1. getaddrinfo 함수
호스트 이름, 호스트 주소, 서비스 이름, 포트 번호의 스트링 표시를 소켓 주로 구조체로 변환한다.
socket(), connect(), bind() 함수에 인자를 넘겨줄 때 사용하면 좋다.
▶ addrinfo 구조체
▶ getaddrinfo(), freeaddrinfo(), gai_strerror() 함수
▶ ai_flag
- AI_ADDRCONFIG
- getaddrinfo가 로컬 호스트가 IPv4로 설정된 경우에만 IPv4 주소를 반환할 것을 요구
- AI_CANONNAME
- host의 공식 이름으로의 리스트 첫번째 addrinfo 구조체에서의 ai_cononname 필드를 가리키도록 한다.
- AI_NUMERICSERV
- service 인자가 port 번호여야 한다.
- AI_PASSIVE
- 서버들이 듣기 소켓으로 이용할 수 있는 소켓 주소 반환
응용 코드의 다른 어떠한 추가적인 조작없이 소켓 인터페이스에서 함수들로 직접 전달될 수 있다.
IP 프로토콜의 특정 버전에 의존하지 않으면서 클라이언트와 서버를 작성할 수 있다.
2. getnameinfo 함수
getaddrinfo() 함수의 역
소켓 주소 구조체를 대응되는 호스트와 서비스 이름 스트링으로 변환
▶ flag
- NI_NUMERICHOST
- host에서 숫자 주소 스트링 반환
- NI_NUMERICSERV
- 포트번호 반환
< 참고 >
🔗 https://velog.io/@fredkeemhaus/네트워크-프로그래밍-소켓-인터페이스
🔗 https://jhnyang.tistory.com/251
🔗 http://www.ktword.co.kr/test/view/view.php?nav=2&no=280&sh=소켓
'KraftonJungle2기 > Today I Learned' 카테고리의 다른 글
[TIL] CSAPP 11장 공부3 - 웹 서버 (0) | 2023.05.21 |
---|---|
[TIL] CSAPP 11장 공부2 - 예제 echo 서버 (1) | 2023.05.20 |
[TIL] CASPP 9장 공부5 - 간단한 할당기3(segregated) (0) | 2023.05.17 |
[TIL] CSAPP 9장 공부5 - segregated list(개념 공부) (0) | 2023.05.16 |
[TIL] CSAPP 9장 공부4 - 간단한 할당기2(Explicit, first-fit) (1) | 2023.05.15 |