오래 못 할 짓 하지 않기

Storage에 File을 저장해야하는데 어떻게 해야 효율적으로 할 수 있을까?3가지 방법이 있다. ● Contiguous Allocation● Linked Allocation● Indexed Allocation  Contiguous Allocation 각각의 파일이 연속적인 Block의 세트를 차지한다. 어떤 파일이 어느 정도의 크기가 필요한지를 나타내고할당해주는 방식이다.  ● 장점 :최고의 Performance  ● 문제점 :- File을 위한 공간 찾기- File size 알아내기- External Fragmentation 해결하기 위해서는 Compaction이 필요하다.  Linked Allocation 각각의 파일이 Block 단위로 Linked 되어있다. 특징 :- 파일의 끝 = nil po..

Directory: 모든 파일에 대한 정보를 담고있는 node들의 집합 ● 특징- 효과적이다 : File 저장을 빠르게 할 수 있음- 이름 관리하기가 편하다 : 같은 파일이라도 다른 폴더에 있으면 이름이 같을 수 있다.- Grouping이 가능하다 : 파일을 묶음 단위로 저장 가능하다.  ● Tree Structure Directories 특1. 검색이 간편하다.2. 그룹핑 하기 좋다.3. 절대경로, 상대경로를 나타낼 수 있다. ( 경로 나타내기 문제 나올 듯 )  ● Acyclic - Graph Directories특징 : 디렉토리들이 서로의 subDirectories나 File들을 공유할 수 있다. Link를 사용해서 구현한다.= 이 때문에 absolute path가 여러 개 존재한다.   삭제 관련..

지금껏 비효율적인 String matching이 많았다.  이렇게  ababac의 패턴과 ababaa를 비교하는 중에 Mismatching이 발생하면다시 한 칸만 가서 비교하는 것이 아니라 ab단위로 움직여도 되지 않겠나 생각할 수 있다. 한 칸만 움직여서 다시 비교하는 게 아니라 몇 칸 더 가서 다시 비교를 시작해도 된다는 것이다. 여기에서 abaa와 abab를 비교할 때 마지막에서 또 Mismatch가 발생한다.그럼 p를 한 칸만 옮겨서 비교하면 바로 MisMatch인 게 눈에 훤하다.다시 a랑 비교를 시작해줘야 하기 때문에 아래와 같이 이동해야한다.   ※ 참고할 점Shift를 할 수 있는 숫자의 후보 중에서가장 조금만 Shift를 한다. s' + k = s + q 이다.둘 다 빨간 동그라미 a를 ..

https://twinw.tistory.com/109https://velog.io/@pjy05200/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B3%B5%EB%A3%A1%EC%B1%85-CH-11.-Mass-Storage-Structure Mass - Storage Structure많은 양의 데이터를 저장하는 Stroage 에는 2가지가 있다. 1. Hard Disk Drives ( HDDs )2. nonvolatile memory ( NVM )  Hard Disk Drives ( HDDs )자성을 가진 물체가 돌아가면서 작동하는 HardDisk ● Transfer time : 읽고 쓰는 시간 ● Positioning Time에는 2가지가 있는데 1. Seek delay  ..

1 . Basic Algorithm2.  Rabin - Karp Algorithm3.  String matching with finite automata  Basic AlgorithmString Matching 주어진 Text T에 Pattern P가 들어가는지 판단하는 것  T 의 길이는 nP 의 길이는 m ( 아마 n보단 작거나 같아야 할 것 같다. ) P가 T에 있다면 Valid Shift라고 한다. or Invalid   4번줄 do if 도 반복문으로 돌아야 한다. - 그에 대한 반복은 최소 1번 (첫 글자만 같은 경우) - 최대 m번 돈다 ( 다 같은 경우 ) 만약 m이 constant하다면? m = n/2라고 하면 O(n^2)이 나온다. 만약 aaab라는 패턴이 있을 때T에서 aaac이렇게 ..

Median = 중간값 ith Order static =  i 번째로 작은 값 ex) Minimum = 1st order statistic      Maximum = nth order statistic Median = 홀수면 (n+1) /2  , 짝수면 n/2 가볍게 생각해보기 좋은 것: n개의 숫자에 min과 max찾기> 'min과 max를 찾으려면 각각 n-1번 비교'총 2n-2'n-1번만 해서 두 개를' 구할 순 없을까? n이 짝수일 때, 한 쌍을 잡아두고, 거기에서 큰 걸 Max으로,  작은 걸 Min으로 해서두 쌍 중에 Min set와 Max set을 만든다. ex) 가위바위보 진 팀 , 이긴 팀 이렇게 나눈다면 각각의 set은 (n-2) / 2 가 되고, 그 안에서 각각 min과 max를 찾..

https://twinw.tistory.com/107Allocation of Frames: 정해진 양의 Free mem을 어떻게 여러 프로세스에 나눠줘야 할까?  ● Allocation 방법: 하나의 process에서 frame이 줄어든다면  → Page fault는 늘어나고 , Performance는 줄어든다.   1. Equal allocation : m개의 frame ,  n개의 process에게 준다면 각 프로세스 당 [ m/n 개 ] 의 프레임을 받는다.  2. Proportionalm 개의 frame에 대해 ai = 프로세스 pi 에게 할당된 프레임의 수si = pi의 크기S = 전체 프로세스의 크기 ai = si / S * m 하나의 프로세스에 할당된 프레임의 수= ( 해당 프로세스의 크기 ..

https://min-h-study-review.tistory.com/259Page Replacement   demand paging 의 문제점은 2가지가 있다. 1. Page replacement 알고리즘을 어떤 걸로 할건지 (우린 이걸 알아볼거임): page fault를 가능한 조금 내는 방향의 알고리즘 = Backing store에 접근하는 시간이 많이 걸리니까 그걸 최대한 줄이려는 것2. Frame allocation 알고리즘은 어떤 걸로 할건지: 한 프로세스당 얼만큼의 프레임을 줘야 할지  어느 프레임에 교체할지 Page replacement 알고리즘 ● 돌아가는 방식: Page fault 가 일어났을 때 Free frame이 없다면, 현재 사용되지 않는 frame을 찾아야 한다.   위 사진에..

Counting sortCounting sort의 원리는 간단하다. 하나의 배열(A)을 Input으로 받고하나의 배열(B)에 Result를 담고하나의 배열(C)에 A에 원소별 갯수를 담는다.  원리는 각 숫자별로 갯수를 count하여원소별로 자리를 지정해주는 것   ex) 나보다 먼저 온 사람이 5명이면 내 자리는 6번째 psuedo code를 보자    1~2 :  k = 해당 array에서 가장 큰 값            0~k까지의 index가 있는 array C를 만든다. 3~4 : A array를 돌면서, A array에 있는 각 숫자를 볼 때마다         C의 Index(=A에서 읽은 값) 에 +1해준다.   결과A 에서 a라는 item의 갯수= C[a] 의 값 5~6 : 2번째 인덱스부..

지금껏 우리가 배운 Sort는 Comparison sort이다. Comparison sort = @번째 Index와 비교해서 자리를 바꾸는 sort  이런 Comparison sort의 Time complexity는 오메가(n lg n)  = 최소 n log n 이상은 시간이 걸린다.  이렇게 n개의 item이 있을 때 sort를 한다고 했을 때 1 : 2 번째 인덱스를 비교 = 1번이 크면 오른쪽, 2번이 크면 오른쪽으로 가는 플로우다. - leaf의 수 = item의 permutation- algorithm의 running time = Path의 length와 관련있다.- Worst - case running time = height of tree  따라서, 비교를 통해서 sort를 하는 경우에는 T..