Do Something Do Something

이진 탐색(Binary Search)이진 탐색정렬된 데이터에서 사용할 수 있다.탐색 범위를 절반씩 줄여가면서 원하는 데이터를 찾는 방식이다. 탐색 과정데이터 중앙에 있는 요소 선택선택된 중앙 요소가 목표값인지 확인목표값보다 작으면 왼쪽 부분에서, 목표값보다 크면 오른쪽 부분에서 이진 탐색을 한다.목표값을 찾을 때까지 1~3번을 반복이진탐색의 성능데이터 크기: n탐색 반복 횟수: x이진 탐색은 탐색을 반복할 수록 데이터 크기가 절반(1/2)씩 줄어든다.$$데이터\;크기 * (1/2)^{탐색\;반복\;횟수} = 데이터\;범위$$ 최악의 경우데이터 범위가 1까지 오는 상황$$n * (1/2)^x = 1$$$$=> n=2^x$$$$=> x=log_2{n}$$ 따라서 시간 복잡도는 O(logN)  [코드 - C]..

배열(Array)배열(array)같은 타입의 데이터를 연속적인 메모리 공간에 저장할 수 있는 자료구조메모리가 연속적이어서 임의 접근이 가능하다.임의 접근 (random access): 데이터가 저장된 위치에 상관없이 직접 데이터에 접근하는 기능인덱스 및 주소를 통해 가능요소(element)와 인덱스(index)로 구성된다.요소(element): 배열에 저장된 데이터를 말한다.인덱스(index): 요소의 위치를 나타낸다.고정된 크기의 자료구조이다.장점구현이 간단하다.데이터에 접근하는 속도가 빠르다.메모리가 연속적으로 되어있고, 인덱스를 통해 빠른 접근이 가능단점배열의 크기를 변경할 수 없다.데이터 삽입 및 삭제 시 오버헤드가 생긴다.필요한 크기보다 크게 만들 경우, 메모리 낭비를 초래할 수 있다.기본 연산..

퀵 정렬(Quick Sort) 정렬 방식분할 정복을 바탕으로 해서, 큰 범위의 정렬을 작은 범위 정렬로 분할시켜서 정렬시킨다.정렬 과정1. 기준 요소 선정 및 정렬대상 분류기준 요소(pivot)를 선정하고 해당 값보다 작으면 기준 요소 왼쪽, 크면 오른쪽으로 옮긴다.해당 글에서는 기준요소를 배열 안 첫번째 값으로 한다.기준 요소 선정은 무작위로 선정할 수도 있고 처음 3개의 요소를 중간 값으로 하는 등 여러 방법이 있다.2. 정렬대상 분할기준 요소 기준으로 왼쪽은 기준 요소보다 작은 그룹들이 생긴다.기준 요소 기준으로 오른쪽은 기준 요소보다 큰 그룹들이 생긴다.각 그룹에서 1번 과정을 반복한다.3. 반복각 그룹 안에서 1과 2를 반복한다.그룹 크기가 1이하로 되어 분할할 수 없을 때까지 진행재귀적으로 수..

선택 정렬(Selection Sort) 정렬 방식리스트의 범위 안에서 최솟값을 찾아 맨 앞으로 보내면서 정렬하는 방식이다.정렬 과정해당 예제에서는 오름차순으로 한다.리스트의 정해진 범위 안에서 최솟값을 찾는다.처음에는 리스트 전체를 탐색하고, 이후 패스마다 앞부분(이미 정렬된 부분)을 제외하고 탐색 범위를 줄인다.찾은 최솟값을 현재 범위의 첫 번째 값과 교체한다.탐색 범위를 하나씩 줄이며 이 과정을 반복한다.   선택 정렬 성능최악의 경우맨 앞부분부터 최솟값을 채워나가는데, 각 루프마다 최솟값을 찾기 위해 (위치가 확정되지 않은 요소들 수)-1만큼 비교를 수행한다.$$ (n-1)+(n-2)+...+2+1 = n(n-1)/2 => O(n^2) $$$$ ∵ 시간 복잡도: O(n^2) $$ 최선의 경우최선의 ..

삽입 정렬(Insort Sort)정렬 방식리스트에서 순차적으로 순회하면서 정렬이 안 된 부분을 찾고, 해당 부분을 적절한 위치에 삽입하여 정렬하는 방식이다.정렬 과정해당 예제에서는 오름차순으로 한다.정렬 대상 범위 선정정렬 대상의 범위는 2개로 시작해서 '자료구조 크기-1'로 1씩 커진다.마지막 요소가 정렬 범위 안에서 최댓값인지 아닌지 확인한다.최댓값이면 그대로 둡니다.최댓값이 아니면 정렬 범위 안에서 위치시킬 곳을 찾은 다음, 해당 부분의 오른쪽 데이터들을 범위 안에서 1칸씩 오른쪽으로 옮기고 빈 부분에 데이터를 삽입합니다.2번째 루프는 이미 정렬이 되어있다.삽입 정렬의 성능최악의 경우 - 역순으로 정렬될 경우루프마다 범위 안 데이터를 모두 비교하고 위치 변경을 한다.$$ 비교 횟수: 1+2+..+(..

정렬의 목적은 '탐색' => 데이터를 빠르고 쉽게 찾기 위함버블 정렬(Bubble Sort)물 속 깊은 곳에서 수면을 향해 올라오는 거품의 모습처럼 데이터를 정렬해서 버블 정렬이라고 불린다.정렬 방식자료구조를 순회하면서 이웃한 요소들끼리 데이터를 교환하며 정렬한다.정렬 과정해당 예제에서는 오름차순으로 한다.한번의 루프가 끝나면 가장 큰 수는 맨 아래로 가기 때문에 비교 범위를 하나씩 줄인다. 버블 정렬의 성능$$ 비교 횟수: (n-1)+(n-2)+...2+1 = n(n-1)/2 => O(n^{2}) $$$$ 시간 복잡도: O(n^{2}) $$ 코드[언어 - C]#include int main(void){ int data[] = {4,2,5,3,1}; int length = sizeof(data..

FUSE(Filesystem in userspace)- root가 아닌 유저가 커널 코드 수정없이 사용자 공간 내에서 파일 시스템을 쉽게 구현할 수 있도록 해주는 소프트웨어 인터페이스  FUSE는 내부 구현이 복잡해서 이를 추상화하여 libfuse 라이브러리로 개발자에게 제공한다. 장점- 디버깅을 편리하게 해준다.- 개발 속도를 빠르게 해준다.- 유연한 파일 시스템 작성이 가능하다. 단점- 기존 시스템과 비교했을 때, 속도가 최대 83%까지 느려질 수 있다.    매 요청마다 유저 레벨로의 RTT(round trip time)이 필요    데이터를 커널과 유저가 공유하기 위해서 복사본을 사용 FUSE에서 제공하는 라이브러리 2가지- high-level API (fuse.h)- low-level API (..

파일(File)- 컴퓨터 시스템에서 데이터를 저장하고 관리하기 위한 기본 단위- 주로 프로그램(소스, 목적 프로그램)과 자료를 나타낸다.- 보조저장장치 같은 물리적 저장 장치에 저장된다.  디렉터리(Directory)- 컴퓨팅에서 파일을 분류하기 위해 사용하는 이름공간- 다른 디렉터리와 파일을 둘 수 있다.- 디렉터리는 디렉터리 안에 또 다른 디렉터리(서브 디렉터리)를 둘 수 있어 트리 구조를 형성한다.  파일 시스템(File System)- 컴퓨터에서 파일, 자료 등을 쉽게 찾고, 접근할 수 있도록 관리하기 위한 구조 및 체제- 구현은 저장장치 상에서 된다. 파일 시스템 확인Windows에서 파일 시스템 확인 방법- Win + R로 실행 창 열고 diskmgmt.msc 입력하기ex) NTFS Linux..