본문 바로가기

Dev.Basic

 (54)
[Sorting] 2. Merge Sort 2. Merge SortSpace-Complexity = 입력 배열 크기의 보조 메모리를 사용한다. Time-Complexity = O(n log n) 원리기본적인 개념으로는 n개의 원소를 가진 배열을 정렬할 때, 정렬하고자 하는 배열의 크기를 작은 단위로 나누어 정렬하고자 하는 배열의 크기를 줄이는 원리를 사용한다. Divide and conquer라는, 분할하여 정복한다의 원리인 것이다. 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법이다. 단 분할(divide)해서 정복했으니 정복(conquer)한 후에는 결합(combine)의 과정을 거쳐야 한다. Merge Sort는 더이상 나누어지지 않을 때 까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우에는 ( 원소 하나인..
[Sorting] 1. Insertion Sort (삽입 정렬) / Bubble Sort (버블 정렬) 1. Insertion Sort Space-Complexity = In-place sort : O(1)의 보조 메모리를 사용한다. Time-Complexity = O(n^2) 원리n개의 원소를 가진 배열을 정렬할 때, i번째를 정렬할 순서라고 가정하면, 0부터 i-1까지의 원소들은 정렬되어있다는 가정하에, i번째 원소와 i-1번째 원소부터 0번째 원소까지 비교하면서 i번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서(i+1)의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해준다. c code>1234567891011121314151617//Insertion Sortvoid insertion_sort(int * arr,..
[3장] 1. 복수 서버에 리퀘스트를 분배한 서버의 부하 분산 3장 첫번째, 복수 서버에 리퀘스트를 분배한 서버의 부하 분산 1. 처리 능력이 부족하면 복수 서버로 부하 분산된다. 클라이언트로 부터 서버에 액세스가 증가할 때,유입되는 대량의 패킷을 서버의 처리 능력이 따라잡지 못할 수 있다. 이럴 경우에는 복수의 서버를 사용하여 서버 한 대당 처리량을 줄여야 하는데, 이러한 방법을 분산 처리라고 한다.그 중 가장 간단한 방법은 단순히 여러 대의 웹 서버를 설치하고 한 대가 담당하는 사용자 수를 줄이는 방법이 있다. 그러기 위해서는 클라이언트가 보내는 리퀘스트를 웹 서버에 분배하는 구조가 필요하다. DNS 서버에 적용되고 있는 분배하는 방법이 가장 간단하다. 서버에 액세스 할 때 DNS 서버에 조회하여 IP 주소를 조사하는데 이 때, DNS 서버에 같은 이름으로 여러..
[2장] 3. IP와 이더넷의 패킷 송 수신 동작 이 포스팅은 '성공과 실패를 결정하는 1%의 네트워크 원리' 책을 기반으로 작성되었습니다.2장 세번째, IP와 이더넷의 패킷 송 수신 동작 1. 패킷의 기본 IP 담당 부분이 어떻게 패킷을 상대에게 송신하는가? 패킷은 헤더와 데이터 두 부분으로 구성된다. 헤더에는 수신처 주소 등의 제어 정보가 들어있고 데이터 부분에는 그 자체로 데이터가 담긴다. 먼저 패킷의 송신처가 되는 기기가 패킷을 만든다. 그리고 가장 가까운 중계장치에 송신한다. 중계 장치는 도착한 패킷의 헤더를 조사하여 다음 목적지를 판단한다. 이 때 어느 수신처가 어느 방향에 있는지에 대한 정보를 기록한 표 같은 것을 사용한다. 헤더에 기록된 내용과 표에 등록된 내용을 결합하여 목적지를 판단하는 것이다. TCP/IP 패킷 구조는 이 기본에서 발..
[2장] 2. 데이터를 송 수신하는 과정 이 포스팅은 '성공과 실패를 결정하는 1%의 네트워크 원리' 책을 기반으로 작성되었습니다.2장 두번째, 데이터를 송 수신 한다. 1. 프로토콜 스택에 HTTP 리퀘스트 메시지를 넘긴다. 접속 동작을 마치게 되면 데이터 송 수신 동작에 들어간다.이 동작은 애플리케이션이 write를 호출하여 송신 데이터를 프로토콜 스택에 건네주는 곳부터 시작된다. 프로토콜 스택은 데이터롤 곧바로 송신하는 것이 아니라 내부이 있는 송신용 버퍼 메모리 영역에 저장을 해둔다. 그 이유는 송신 의뢰가 올 때마다 데이터를 송신하게 되면 네트워크 효율이 떨어지기 때문이다.그렇다면 어떤 기준으로 데이터를 저장하는가? 프로토콜 스택은 MTU라는 매개변수를 바탕으로 판단한다. MTU란 한 패킷으로 운반할 수 있는 디지털 데이터의 최대 길이..
[2장] 1. TCP/IP - 소켓을 작성하고 서버에 접속한다. 이 포스팅은 '성공과 실패를 결정하는 1%의 네트워크 원리' 책을 기반으로 작성되었습니다.2장. TCP/IP Outline1. 소켓을 작성하고 서버에 접속한다. 2. 데이터를 송수신 한다. 3. 서버에서 연결을 끊어 소켓을 말소한다. 4. IP와 이더넷의 패킷 송수신 동작 5. UDP 프로토콜을 이용한 송수신 동작 2장 첫번째. 소켓을 작성하고 서버에 접속한다. 1. 프로토콜 스택의 내부구성 프로토콜 스택 내부는 데이터 송수신을 담당하는 TCP, UDP와 패킷 송 수신 동작을 제어하는 IP로 나누어져 있다. 브라우저나 메일 등의 일반적인 애플리케이션이 데이터를 송수신 할 경우 TCP 프로토콜을 사용하며 DNS 서버에 대한 조회 등 짧은 제어용 데이터를 송수신 할 경우에는 UDP 프로토콜을 사용한다. IP..
[1장] 4. 프로토콜 스택에 메시지 송신을 의뢰한다. 이 포스팅은 '성공과 실패를 결정하는 1%의 네트워크 원리' 책을 기반으로 작성되었습니다.1장 네번째. 프로토콜 스택에 메시지 송신을 의뢰한다. 데이터 송 수신 동작의 개요이제 드디어 IP 주소를 알아냈다. 이제 이 IP 주소와 HTTP Request 메시지를 프로토콜 스택에 전달하여 메시지 송신을 의뢰해야 한다. 이 때도 Socket 라이브러리를 이용한다. 단, 의뢰를 할 때는 Socket 라이브러리 프로그램 부품을 결정된 순번대로 호출해야 한다. 데이터를 송수신은 기본적으로 '데이터 통로'를 통해 수행된다. 클라이언트와 서버 사이에 파이프 같은 것이 존재하여 파이프를 통해 데이터를 주고 받는 것이다. 송수신 동작을 하기 전에 송수신하는 양자 사이를 파이프로 연결해줘야 한다. 연결해줄 때의 요점은 소켓..
[1장] 3. 전 세계의 DNS 서버가 연대한다 이 포스팅은 '성공과 실패를 결정하는 1%의 네트워크 원리' 책을 기반으로 작성되었습니다.1장 세번째. 전 세계의 DNS 서버가 연대한다 1. DNS 서버의 기본 동작리졸버로부터 DNS서버가 받는 조회 메시지에는 다음과 같은 내용이 포함되어 있다. 이름 : 서버 or 메일 배송 목적지와 같은 이름 클래스 : 초창기 때는 인터넷 이외에도 네트워크를 이용하는 경우가 많았다. 따라서 이들을 구분해주기 위해 클래스라는 것을 이용했다. 그러나 지금은 인터넷 이외의 네트워크는 소멸되었으므로 클래스는 항상 인터넷을 나타내는 ‘IN’이라는 값이 된다. 타입 : 타입에 따라 클라이언트에 회답하는 정보의 내용이 달라진다. IP주소를 조회할 때는 A라는 타입(Address)을 이용하며, 메일 배송 목적지를 조회할 때는 MX..

티스토리툴바