본문 바로가기

Computer Science50

Sorting I - Insertion Sort 정렬된 데이터는 정렬되지 않은 데이터에 비해 여러가지 장점이 있다. 탐색도 정렬되지 않은 데이터는 O(n), 정렬된 데이터는 O(logn)으로 정렬된 데이터가 훨씬 빠르다. 이 외에도 여러 장점 때문에 데이터를 정렬할 필요가 있다. 정렬 방식에 어떤 것들이 있고, 복잡도는 어떤지 하나씩 알아보자. Insertion Sort 삽입 정렬은 element 하나씩 적절한 위치로 삽입하며 정렬하는 알고리즘이다. Example 위와 같은 정수 배열을 삽입 정렬을 통해 오름차순으로 정렬해보자. 먼저 첫번째 element는 정렬이 되어있다고 가정한다. 다음으로 정렬되지 않은 element, 2를 올바른 위치에 삽입해준다. 배열의 맨 앞에 오거나(index=0) 앞의 element보다 key 값이 클 때까지(E[cur-.. 2021. 4. 15.
Searching - Sequential Search, Binary Search 배열에서 원하는 값을 찾는 탐색 방법은 여러가지가 있다. 배열 안의 데이터가 정렬되어 있는지, 아닌지에 따라 많은 시간 차이가 발생하기도 한다. 어떤 탐색 방법들이 있고, 각각의 상황에 어떤 방법이 적합한지 분석해보자. Sequential Search 가장 단순히 생각할 수 있는 방법인 순차 탐색 알고리즘이다. 순차 탐색은 말 그대로 목표한 값을 찾을 때까지 배열 안의 모든 데이터를 순차적으로 비교하는 방법이다. int seqSearch(int* E, int n, int K) { int ans = -1; for (int i = 0; i 6 찾고자 하는 값이 더 작기 때문에 가운데 값 7의 왼쪽까지로 구역을 좁혀 다시 반복한다. 다음 중간값은 2로 찾고자 하는 값 6이 더 크기 때문에 중간값 2의 오른쪽까.. 2021. 4. 14.
Algorithm Analysis - Correctness, Complexity, Optimality 컴퓨터 알고리즘이란 문제를 해결하기 위해 정의한 Instruction Sequence를 말한다. 알고리즘을 작성했다면 알고리즘이 문제의 요구조건을 만족하는지(Correctness), 얼마나 많은 연산이 필요한지(Complexity), 문제의 복잡도와 얼마나 가까운지(Optimality) 분석해야 한다. 그럼 이제 알고리즘을 세워보고 어떻게 분석하는지 알아보자. Algorithm n개의 entry를 갖는 non-ordered array E에서 index 값이 K인 entry를 찾는 문제를 해결해보자. int seqSearch(int* E, int n, int K) { int ans, index; ans = -1; for (index = 0; index < n; i++) { if (K == E[index]).. 2021. 4. 10.
Electronic Mail (SMTP, POP3, IMAP / MIME) E-Mail Protocols 우리가 사용하는 이메일 또한 네트워크를 이용한 응용 프로그램이다. 따라서 메일을 주고 받을 때 사용하기 위한 여러 종류의 프로토콜들이 정의되어 있으며, 대표적으로는 TCP/IP 모델의 응용 계층에 속한 SMTP, POP3, IMAP 등이 있다. SMTP SMTP란 Simple Mail Transfer Protocol의 약자로, 간단한 메일 전송 프로토콜이라는 뜻이다. TCP 25번 포트를 통해 통신하며, 클라이언트에서 서버 또는 서버에서 서버로 메일을 전송할 때 사용한다. POP3 POP3란 Post Office Protocol 버전 3를 말한다. TCP 110번 포트를 사용하며, 서버에서 클라이언트로 수신된 메일을 전송할 때 사용한다. 이 때, 클라이언트로 전송한 메일은 .. 2020. 7. 17.
File Transfer Protocol (FTP) FTP란? FTP란 File Transfer Protocol의 약자로, 파일 전송 프로토콜을 말한다. HTTP와 마찬가지로 TCP/IP 모델의 응용 계층(Layer 4)에 속한 프로토콜이며, 네트워크를 통한 클라이언트와 서버 간 파일 전송을 위한 프로토콜이다. File Transfer FTP를 통해 파일을 전송할 때는 먼저 클라이언트가 서버의 21번 포트로 연결 요청을 보내고, 21번 포트를 통해 서버와 연결되면 다시 다른 포트로 연결하여 데이터를 주고 받게 된다. 이 때 서버에서 지정한 포트 번호로 클라이언트가 연결해 데이터를 보내면 Active Mode(능동 모드), 클라이언트가 자신의 포트 번호를 보내 서버에서 해당 포트로 데이터를 보내면 Passive Mode(수동 모드)이다. 각각의 과정을 좀 .. 2020. 7. 15.
HyperText Transfer Protocol (HTTP) HTTP란? HTTP란 HyperText Transfer Protocol의 약자이며, 그대로 해석하면 하이퍼텍스트 전송 규칙이다. 여기서 하이퍼텍스트란 html과 같이 정보를 효과적으로 전달하기 위한 문서를 말한다. 즉, HTTP란 html과 같은 문서를 전송할 때 따라야 하는 규칙들을 정의해놓은 것이다. HTTP는 TCP/IP 모델의 응용 계층(Layer 4)에 속한 프로토콜이며, 주로 서버와 클라이언트 사이에서 html 문서를 교환할 때 사용된다. 문서를 전송할 때는 TCP와 UDP를 통해 전송하며, 80번 포트를 사용한다. HTTP는 클라이언트에서 서버로 요청(request)을 보낼 때 따라야 할 형식, 서버에서 클라이언트로 응답(response)을 보낼 때 따라야 할 형식을 각각 정의하고 있다. .. 2020. 7. 15.
OSI Model & TCP/IP Model OSI Model이란? OSI(Open Systems Interconnection) 모델이란 ISO에서 computer networking 과정을 정의한 모델이다. OSI 모델은 networking 과정을 크게 7개로 나누어 분류하여 정의하며, 각각의 단계를 layer라고 한다. 이 layer에는 어떻게 데이터를 가공하여 전송할 지 정의된 protocol들이 속해있다. 각각의 protocol들은 하위 layer의 기능을 사용할 수 있으며, 이를 바탕으로 상위 layer에게 기능을 제공한다. 이제 7개의 layer들은 각각 무슨 역할을 하며, 어떤 protocol들이 속해있는지 알아보자. OSI Layers Layer 1 - Physical Layer (물리 계층) 물리 계층은 하드웨어를 통한 데이터의 물.. 2020. 6. 30.
Query Processing & Cost Measuring Query Processing이란? 데이터베이스에서 데이터를 가져오거나 데이터를 삽입할 때 사용하는 언어를 Query라고 한다. Query Processing이란 우리가 보낸 Query를 데이터베이스가 처리하는 과정을 말한다. Basic Step 기본적으로 query를 처리하는 과정은 다음과 같다. 1. 입력받은 query를 parser와 translator가 relational-algebra 형태로 변환한다. 2. optimizer가 데이터의 통계 정보를 바탕으로 query 실행 계획을 세운다. 3. evaluation engine이 세워진 계획을 바탕으로 query를 실행하여 결과를 반환한다. Query Cost Measuring query optimization이란 query를 실행 가능한 계획 중.. 2020. 6. 24.
Hash Index Hash Index란? hash index란 데이터의 위치를 hashing을 통해 index를 저장하는 방식을 말한다. hashing이란 특정한 hash function를 정의하여 이를 통해 key 값을 일정한 범위의 수로 변환하는 작업이다. 따라서 hash function에 key 값을 통과시키면 바로 index의 위치를 얻을 수 있기 때문에 별도의 공간이 필요하지 않다. index entry들은 일정한 크기의 bucket이라는 단위로 나뉘어 저장되게 되는데, 이 때 hashing을 통해 각각의 index entry들은 어떤 bucket에 들어가게 될 지 결정되게 된다. hashing은 이 bucket을 할당하는 방식에 따라 static hashing(정적 해싱)과 dynamic hashing(동적 해.. 2020. 6. 24.

티스토리툴바