해나의 컴공생존기

파일 시스템은 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() 는 그 노드..

1. vector Vector: Variable-Size Array(사이즈가 늘어나고 줄어들 수 있는 배열) Sorted Search: O(log n), Insert: S+ O(n) , Delete: S+ O(n) Unsorted Search: O(n), Insert: S + O(1), Delete: S + O(1) 2. Dummy Nodes Standarad Linked List에 대부분 포함되는 구조. 처음에 만들때 노드를 두개 만들고 하나는 마이너스 무한대 하나는 플러스 무한대 값을 집어넣는다. 이 두 값은 실제로 사용하는 값은 아니고, 미리 경계를 정해놓는 것이다. 이렇게 해놓으면 못찾았을때 (실패했을 때), P와 L이 NULL인 경우가 없어지게 된다. 3. Circular List Circula..

Linked List 연속적인 노드 Node : unit of storage (item) Nodes are linked with pointers Linked list는 배열과 다르게 메모리 아무데나 있을 수 있다. 대산 한 노드에 가면(=한 노드의 주소를 알아서 그곳의 내용을 읽으면) 다음에 갈 노드의 주소가 적혀있다. 즉 노드들이 포인터들도 연결이 되어 있는 것이다. Linked List의 노드의 구조를 살펴보면 다음과 같다. Whole List 이런식으로 구성이 되어있다. (화살표 등은 사람이 보기 쉽게 표현한것이다.) 마지막 노드에는 더이상 갈 곳이 없으므로 null값을 넣는다. 첫번째 노드로 갈때는 어쩔수 없이 그 노드가리키는 포인터를 가지고 있어야 한다. Code for List class No..

Equivalence Relation 정의 관계의 정의 Given a set A, a Relation on A is any subset of AxA Ex) A = {1, 2, 3, 4}, R = {(1,3), (3,4), (1,1), (2,2)} We write 1R3 to mean (1,3) ∈ R An extreme example Relation '

Queue Insert/Delete만 제공 First in, First out( 먼저 들어오는게, 먼저 나가는 것) 성능: Insert O(1) , Delete O(1) Queue 구현 Stack과 다르게 Queue는 Head와 Tail 두개가 필요하다. 앞서 다룬 stack보다 좀더 생각할 거리가 늘어나게 된다. 만약 새 값이 insert 될때 Tail과 Head는 어떻게 될까? head는 그대로 있고 Tail은 위로 한칸 움직일 것이다. 반대로 값이 delete 되면 Head가 위로 한칸 올라갈것이다. 그렇다면 다음과 같은 상황에서 Tail에 새 값이 새로 insert가 되면 어떻게 될까? 간단하다 제일 밑의 빈공간에 Tail이 가리키게 된다. 아래의 그림과 같이 말이다. 그러면 이 상황에서 좀 더 ..

Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First out(나중에 들어오는게, 먼저 나가는 것) 성능: Push: O(1), Pop: O(1)(넣는것을 push, 빼는것을 pop) Stack 구현 Stack Pointer는 값이 다음에 들어올 자리를 뜻한다. Stack Code int Stack[N]; int SP; int init() {SP = 0} int isEmpty() {return SP == 0;} int Push() { Stack[SP] = x; SP++; } int Pop() { SP--; return Stack[SP]; }​ # 미로찾기 이런 미로 문제를 해결하는 알고리즘 중에 DFS 와 BFS가 있다. 오늘은 DFS로 미로를 찾는 과정을 알아볼..

Problem Defintion Text : 간단한 문자열 Pattern: 간단한 문자열 To Do : 패턴을 발생하는 곳 찾기 Text : abababcabcabcdabccbaabdabcabcdabcd 다음과 같은 text에서 abcabcd 를 찾는 문제라고 생각해보자. 사람이라면 한글자 한글자 보겠지만 굉장히 느린방법이고 사람중심적인 방법이다. 1) Naive 알고리즘 Naive 알고리즘은 아까 위에서 설명한 사람이 한 것과 같은 방식의 알고리즘이다. 사람이 할때는 패턴을 하나씩 옮겼지만 컴퓨터로 이를 구현할때 어떻게 표현해야 할까? 코드로 표현하면 다음과 같다. // n 은 문자열의 길이 // m은 패턴의 길이, output은 결과 int naivematch ( char T[], int n, cha..