본문 바로가기

전체 글

 (84)
Socket Programming (소켓 프로그래밍) (2) 지난 글에서는 server와 client의 연결, 그리고 메시지를 보내고 받는 함수들에 대해서 알아보았다. 본 글에서는 앞서 배운 과정과 함수들을 이용하여 직접 통신해보는 프로그램을 구현한다. 지난 글에서 알아본 과정은 다음과 같다. 만약 과정이 이해가 안된다면 이전글(링크)를 통해 이해하고 오자. TCP 다음 코드들은 메시지를 보내는 예시코드이다. TCP 서버코드 #define BUFSIZE 1024 void error_handling(char *message); int main(int argc, char **argv){ int serv_sock; int clnt_sock; char message[BUFSIZE]; int str_len; struct sockaddr_in serv_addr; struct..
C++ 백준 11066 (파일 합치기) 백준 11066 (파일 합치기) https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 전형적인 DP식 문제이다. 문제들을 풀면서 느낀 점인데 뭔가 문제를 보고 딱 떠오르는 알고리즘이 없으면 구현/DP인 것 같다. 설명 2차원 DP를 선언한다. dp[i][j]는 i부터 j파일까지 합쳤을 때 최소비용이다. 그렇게 되면 d[i][i] = 파일 i의 크기가 될 것이다. 아이디어는 다음과 같다. i~j까지의 파일을 합치는데 해당 파일들이 합쳐지기 전..
C++ 백준 11054 (가장 긴 바이토닉 부분수열) 백준 11054 (가장 긴 바이토닉 부분수열) https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net LIS를 이용하는 문제이다. 또한 LIS의 길이만 알면 된당. LIS의 길이에 대한 설명은 여기(링크)에 자세히 나와있으니 꼭 알고오자. LIS의 길이를 구하는 방법은 O(N^2)과 O(NlogN)로 구하는 두 가지의 방법이 있는데 본 글에서는 O(NlogN)방법을 이용한다. O(N^2)으로도 해봤는데 속도가 확실히 차이가 나는 것을 볼 수 있다. 밑에꺼가 O(N^2)이..
Socket Programming (소켓 프로그래밍) (1) API API란 시스템이 어플리케이션에 제공하는 인터페이스이다. API에는 여러 종류가 있는데 우리는 TCP/IP에서 쓰이는 다양한 API중 Sokcet에 대해 알아 볼 예정이다. TCP/IP에 쓰이는 API는 Socket말고도 TLK, XTI, Winsock, MacTCP등 여러 종류가 있다. Sokcet 소켓은 다섯개의 componet와 관련이 있다. 또한 아래의 함수들은 헤더파일과 헤더파일에 존재한다. 1. Protocol - 어떤 프토토콜을 사용할 건지 - socket()함수의 argument로 어떤 프로토콜을 사용할 건지 알려준다. 2. Source's address and port number - 보내는 곳의 주소와 포트넘버 - socket()함수는 socket descriptor(OS에서의 ..
CH3 : Transport Layer (5) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * Congestion Control 이미 여러번 언급했지만 이번강의에서는 congestion control에 대해 자세히 알아본다. Congestion 라우터가 처리할 수 있는 용량보다 많은 packet이 들어오게 되면 congestion이 일어난다. congestion이 일어나면 크게 두가지 상황이 발생한다. 1. packet loss (라우터의 buffer가 overflow가 나서 패킷이 로스된다) 2. long delays (라우터의 queue가 매우 혼잡하여 처리과정이 느리다) 이러한 문제가 발생하지 않게 사전에 예방을 해야하는데 방법은 sendring rate를 ..
CH3 : Transport Layer (4) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * Reliable Data Transfer - TCP는 SR ARQ방식과 비슷한 매커니즘을 사용한다. 그러나 SR처럼 WS를 정해놓지 않고 이 WS는 dynamic하게 변한다. 이때 이 WS는 flow control과 congestion control의 영향을 받는다. - cumulatvie ACK을 사용하고 다음에 받아야할 seq num을 보낸다 예를 들어 현재 seq num 1000번까지의 데이터를 받았다면 ack(1001)을 보낸다. - 재전송을 지원한다. timeout이 일어나면 재전송을 하는데 이때 이미 온 ACK에 대해서 똑같은 ACK이 3번오게되면 timeou..
CH3 : Transport Layer (3) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * 이전글에서는 UDP와 ARQ에 대해서 배웠다. 이번글에서는 TCP에 대해 자세하게 다룰 예정이다. TCP(Transmission Control Protocol) - 여러번 얘기했듯이 TCP는 연결지향형 프로토콜이다. 3-handshaking을 통해 상호간의 connection을 생성한 뒤 소통한다. - 1:1방식의 프로토콜이다. - full-duplex data 방식을 지원한다. full-duplex와 다른 개념에는 half-duplex, simplex가 있다. simplex : 단방향 통신, A는 B에게 또는 B는 A에게로만 통신할 수 있음 half-duplex : 양..
CH3 : Transport Layer (2) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * Reliable data transfer 데이터전송을 reliable하게 하는 방식에는 두가지가 있다. 1. Forward Error Correction (FEC) - 반복되는 bit를 더해 리시버가 에러를 체크하게끔 한다. - 예를들어 센더는 1을 보낼때 111을 보내고, 2를 보낼때 222를 보낸다. 만약 111이 가는중에 에러가 발생하여 101이 도착했다면 리시버는 많이나왔던 1을 실제로 온 데이터로 받아들여 1이라고 인식한다. 2. Retransmission - 에러가 나면 재전송하는 기능이다. - ARQ(Automatic Reapeat Request)라고도 하며..

티스토리툴바