해나의 컴공생존기

앞으로 자주 쓰일 자료구조들을 한번 복습해볼 것이다. 1. Array 동일한 type의 데이터를 연속된 주소에 저장하는 자료구조이다. 갯수를 미리 정해야하고 중간에 용량을 늘리기는 불가하다. 인덱스만 알면 데이터에 접근하기 슂다는 장점을 가지고있다. ex) A[7] = 400 + 7*4 = 428 Search, Delete, Insert 입장에서 효율이 좋지 않다. sorting이 되어있다면 Binary Search O(log N)가능하다. 2. Stack insertO(1) / DeleteO(1)만 제공한다. Search x Last in, First out 수식 계산에 사용 ex (3+7)*2 + (6-3)/5 3. Queue insert O(1) / Delete O(1)만 제공한다. Search x..

1. Quick Sort 이는 merge sort와 다르게 추가 배열을 만들지 않아도 된다. quick sort의 알고리즘은 아래와 같다. 1. 배열에서 어느 한 값을 pivot으로 설정한다. 2. pivot을 기준으로 왼쪽은 pivot보다 작게 오른쪽은 pivot보다 큰 숫자가 들어가도록한다. 3. pivot을 기준으로 왼쪽과 오른쪽을 나눠서 재귀를 실행시킨다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]

1. Merge Algorithm sorting된 두개의 배열을 앞에서부터 각각 하나씩 비교하며 한 배열에 순서대로 합치는 알고리즘. 이 알고리즘의 단점은 하나의 배열을 새로 만들어야한다는 것이다 2. Recursive Merge Sort 위 코드를 간단히 설명해보자면 먼저 a[]와 똑같은 b[]를 만든다. h는 배열 전체 길이의 절반이다. b[0]부터 b[h-1] 까지 sort하는 함수를 한번 호출하고 b[h]부터 b[n-h-1]까지 sort하는 함수 하나를 호출한다. 끝까지 한 다음에는 마지막에 a로 sorting되며 합쳐진다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야..

1. sorting의 조건 정확하게 sorting이 되기 위해서는 아래의 두가지 조건이 성립되어야한다. 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야한다. 조건2. 배열 b는 b[0]n−1 일 때 sort 함수가 성공한다고 가정하자. 항상 재귀 실행 전에 a[0]에 최소값이 들어간 후 실행된다. 따라서 재귀로 들어가기 전부터 ∀x((x>0)→(a[0]a[0]

1. Binary Search 이진탐색트리 코드이다. l은 왼쪽 끝 ,r은 오른쪽 끝 ,m은 중간이다. 기본 적인 아이디어는 sorting된 배열의 중간을 찾아 크기를 비교해가며 원하는 값을 찾는 것이다. 처음에는 0번째 배열을 l , 마지막 배열을 r로 두고 탐색을 시작한다. 탐색은 l과 r이 만나면 종료된다. m은 l과 r의 중간이고 (l+r)/2 로 두었다. 이게 성립하나를 위해 몇가지 예시를 보겠다. 1) n=2 l=0, r=1, m=0 으로 모두 탐색 가능하고 2) n-3 l=0, r=2, m=1 으로 모두 탐색 가능하다 a[m]과 x를을 비교해서 x가 작다면 왼쪽을 탐색하고 x가 크다면 오른쪽을 탐색하고 x와 같다면 종료된다. 왼쪽 탐색을 위해서는 r을 m의 바로 전 인덱스로 설정되고 오른쪽 ..

컴퓨터를 사용하다보면 시스템이 출돌하거나 전원이 차단될수도 있다. 디 때 다시 정상적으로 유지하기 위해서 어떻게 할지에 대한 내용이다. 파일을 작성할 때에는 3가지에 정보가 업데이트된다. 1. Data bitmap 2. inode 3. data block 이 정보를 업데이트하다가 오류가 났고 세개 중 하나만 업데이트 되었을 때 무슨일이 일어나는지 봐보자. 1) 데이터 블록에만 적혔을 때 이 때는 파일은 존재하지만 그 파일에 대한 정보는 존재하지 않는다. inode와 data bitmap의 정보 불일치는 일어나지 않아 그나마 괜찮다. 2) inode 만 업데이트 됐을 때 데이터가 유효하다고 적혀있는데 입력이 되어있지 않아 디스크에서 쓰레기 값을 읽게 된다. inode와 data bitmap의 정보 불일치가..

파일 시스템은 100퍼센트 소프트웨어 프로그램이다. 이는 단지 더 잘 실행될 수 있기 위해 하드웨어의 기능을 추가하지 않았다. 1. Data structures 아래 그림은 파일 시스템의 데이터 구조을 나타낸 그림이다. 위 그림을 보며 하나하나 설명해보겠다. 1.1 Block 디스크의 단위이다. 전체적으로 데이터는 연속적은 Block으로 이루어져 있다. 위에 보면 D 가 적혀 있는 박스 하나가 한 Block이다. 1.2 Data region 이 블록들을 위해 디스크에는 고정된 부분이 있다. 이는 그림에서 D로 표현되어있으며 데이터가 저장되어있다. 1.3 Metadata Metadata란 데이터들을 위한 데이터를 의미한다. 인덱스 3번부터 7번 까지를 보면 I 라고 되어있다. 이는 inode table이라..

파일 - 바이트의 선형 배열 - 각 파일의 가장 기본적인 이름은 inode - OS는 확장자를 보고 파일의 구조를 알지 못한다. Directory - 사용자가 읽을 수 있는 이름과 하위 수준의 이름 쌍을 포함한다. (foo , 10) - 디렉토리의 inode도 있다. 1. Creating files /* open */ int fd = open("foo", O_CREAT|O_WRONLY|O_TRUNC, S_IRUSR|S_IWUSR); O_CREAT : 똑같은 이름의 파일이 없다면 생성, 있다면 open O_WRONLY : 오직 쓰기 위해 open O_TRUNC : 파일이 이미 있는 경우 덮어쓴다 S_IRUSR|S_IWUSR : 사용자 권한 지정, 이 경우 소유자가 파일을 읽고 쓸 수 있도록한다. 2 Acc..

AVL Tree Idea 아이디어는 다음과 같다. 위의 tree 구조를 살펴 보자. 보기에 아름다운(?) 구조 인가? 아마 대부분 그렇게 생각하지 않을것이다. Tree 가 왼쪽으로 쏠려 있는 모양을 하고 있기 때문이다. 그럼 위의 그림을 직관적으로 봤을떄 어떻게 고치면 높이가 최소화된 Tree 모양이 나올까? 아마 4가 root인 모양으로 변형 시키면 높이가 좀더 낮아질것이라고 생각했을 것이다. 어떤가 ? 아까 Tree 에 비해 좀더 height가 낮아진 균형이 잡힌 tree 구조로 보일 것이다. 이런식으로 tree구조를 만들어 나가는 과정을 가지게 될것이다. AVL Tree Definition Each Node has Two Labels: L and R L : Height of Left Subtree,..

Definition of Binary Search Tree 값은 아무거나 넣을 수 있다. 노드 3개를 묶어서 보았을 때 중간 노드의 값보다 큰 값은 오른쪽 작은 값은 왼쪽으로 들어가게되는 형태이다. Code for Node class Node { int k; Node *l, *r; };​ Search Algorithm Node *Search(Node *N, int x) { if (N == Null) return NULL; if (N -> k == X) return N; else if (N->k r,X) else return Search(N->1, X); };​ Search Correctness To Prove : 만약 x가 노드에 있다면 Search() 는 그 노드..