4. Sorting 4-3. Mergesort 합병 정렬 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있을 때 사용. 정렬 문제의 문제 복잡도 F(n) = O(n lgn) time 합병 정렬의 worst case complexity W(n) = O(n lgn) time W(n) = F(n) : Optimal algorithm 따라서 합병 정렬 알고리즘은 Optimal algorithm 이다. Merging Sorted Sequences Problem 오름차순으로 정렬된 두 리스트 A, B를 새로운 리스트 C로 합친다. Strategy A와 B..

소켓 생성 (전화기 생성) #include int socket(int domain, int type, int protocol); 성공 시 파일 스크립터, 실패 시 -1 반환 소켓의 주소 할당 및 연결 (전화기에 번호 부여) #include int bind(int sockfd, struct sockaddr *myaddr, socklen_t addrlen); sockfd: 소켓번호 struct sockaddr *myaddr: 주소(ip, port) 구조체 성공 시 0, 실패 시 -1 반환 연결요청이 가능한 상태로 변경 (전화 받기 가능) #include int listen(int sockfd, int backlog); 일반 소켓을 서버소켓으로 바꿔줌. 일반 소켓은 걸 수만 있고 받을 수는 없음. listen..

TCP: Transmission Control Protocol 9. Congestion Control Congestion 링크가 보낼 수 있는 Maximum 값이 100Mbps인 상황에서 TCP connection 1, 2에서 각각 100Mbps, 총 200Mbps가 들어오면 Congestion 발생 Packet delay and network load Delay 데이터 처리 속도가 얼마나 지연되는지 Load 데이터가 얼마나 들어가는지 input의 합이 100Mbps에 가깝게 되면 delay갑자기 증가 Throughput versus network load Throughput (=receiving rate) 데이터를 얼마나 빠르게 받고 있는지 Load 데이터가 얼마나 들어가는지 ex. 50Mbits 데이..

TCP: Transmission Control Protocol 8. Error Control Error Control TCP는 신뢰할 수 있는 transport layer 프로토콜이다. 즉, TCP로 데이터 스트림을 전송하는 응용 프로그램은 TCP에 의존해 전체 스트림을 반대쪽 끝에 있는 응용 프로그램에 오류 없이 순서대로 전달할 수 있다. TCP의 Error Control(오류 제어)는 checksum, acknowledgment, and time-out의 세 가지 tool을 사용하여 수행된다. 알아두기 ACK에 대한 ACK은 존재하지 않는다. 즉, 내가 보낸 ACK을 상대방이 잘 받았는지 확인하는 ACK은 존재하지 않는다. 데이터는 순서가 잘못된 상태로 도착하여 receiving TCP에 의해 일시적..

TCP: Transmission Control Protocol 7. Flow Control Flow Control 생산자가 데이터를 생성하는 속도와 소비자가 데이터를 사용할 수 있는 속도의 균형을 유지. sliding window Send window in TCP Sender는 Receiver가 Ack을 보내면서 알려준 rwnd 값을 통해 상대방 버퍼의 빈 공간을 파악하고, 그 빈 공간만큼을 Send window 사이즈로 정한다. window 사이즈는 Receiver가 한번에 받을 수 있는 데이터의 양이다. 데이터 전송 후, 보낸 데이터는 데이터 전송 오류를 대비하여 여전히 Sending Buffer에 남겨둔다. 상대방이 Ack을 보내 해당 데이터를 잘 받았다는 표시를 하면 해당 데이터를 Sending ..

1. Analyzing Algorithms and Problems: Principles and Examples 1-4. Searching on Ordered Array 정렬된 배열 탐색 Let's Divide-and-Conquer 개선된 알고리즘 → 분할과 정복 Problem and Strategy D K를 먼저 배열의 가운데에 있는 entry와 비교 한 번의 연산으로 절반의 entry를 제거할 수 있다. 동일한 전략을 재귀적으로 수행한다. Algorithm D: Binary Search (반드시 정렬된 array 여야 함) Input: E, first, last, and K→ first, …, last까지 정렬된 array E, K 는 찾아야 할 key 값, input 모두 정수 Output: firs..

TCP: Transmission Control Protocol 6. Windows in TCP stop & wait 방식 데이터 전송할 때마다 잘 받았는지 확인 신뢰성 보장 위한 가장 쉬운 접근 방식 데이터 전송을 화물 트럭으로 비유해 보자. 화물트럭 5대는 서울에서 출발해 부산에 화물을 운반 후 다시 서울로 돌아와 화물이 안전하게 도착했음을 보고해야 한다. stop & wait는 하나의 트럭이 서울-부산을 왕복해서 돌아온 후에 다음 번 트럭이 운행을 시작하는 방식이다. 서울에서 부산까지 왕복으로 10시간이 걸리기 때문에, 트럭 5대가 부산에 화물을 모두 운반하기까지는 50시간이 걸린다. 이는 매우 비효율적이다. 이러한 비효율성을 해결하기 위해 한꺼번에 트럭을 여러 대 보낼 수는 없을까?트럭을 여러 대 ..

TCP: Transmission Control Protocol 3. State transition diagram TCP 연결요청 / 수락 과정 State transition diagram Client / Server 동작 및 상태 설명 (왼: 클라이언트 / 오: 서버) Passive open 수동으로 서버를 열어놓음 [LISTEN] 연결요청 대기, 클라이언트로부터 SYN이 오기를 기다리는 상태 Active open / SYN Active open하기 위해 SYN을 서버에게 전송 [SYN-SENT] SYN을 전송한 뒤 서버로부터 SYN+ACK이 오기를 대기중인 상태 SYN / SYN + ACK 클라이언트로부터 SYN이 오면 클라이언트에게 SYN + ACK을 전송 [SYN-RCVD] 클라이언트로부터 SYN을..

1. Analyzing Algorithms and Problems: Principles and Examples 1-4. Searching on Ordered Array 정렬된 배열 탐색 Problem and Strategy A Problem: array search 배열 탐색 n개의 entry가 담긴 배열 E와 value K가 주어졌을 때, 배열에서 K=E[index]를 찾는다면 인덱스 값을, K를 찾지 못한다면 -1을 결과로 리턴한다. Strategy A input data와 자료구조: 정렬되지 않은 배열 sequential search(index 0부터 차례로 비교) Algorithm A int seqSearch(int []E, int n, int K) Analysis A W(n) = n //wors..