인프런 워밍업 클럽2 cs <day14> 끝!

드디어 마지막 복습 ㅜㅜ 하라고 할 때 안해서 이번주 수요일까지 숙제가 생겨버렸다..

할 때 하자... 시간 더들이지말고

알고리즘

동적프로그래밍 - 메모이제이션

• 앞서 재귀식을 배웠다. 재귀식은 콜스택에 함수를 계속해서 쌓고쌓고 하는 방식이였다.=> 자리차지하고 비효율적이다.
  피보나치 수열을 이용해서 재귀식에서 상향식으로 효율적이고 빠르게 연산하는 방식을 알아보려고한다.

• 피보나치 수열 : 첫번째 수와 두번째 수를 더해 세번째 수를 만들고 두번째 수와 세번째 수를 더해 네번째 수를 만든다.
  이렇게 무한하게 배열을 이룰 수 있는 수열이다.

• 피보나치 수열을 재귀식으로 만들어보자

function fibo1(n){
  if(n==0||n==1) return n;
  return fibo1(n-2) + fibo1(n-1);
}

그림으로 쉽게 배우는 알고리즘 - 감자

• 하지만 수가 커지면 커질수로 중복되는 계산도 많아진다.
  아래와 같이 초록색은 계산중인 부분, 노란색은 중복이 되는 부분이다.
  => 효율성이 떨어진다. 이런 효율성을 보완하기 위해 메모이제이션을 사용하게 된다.

  
  

• 메모이제이션 : 계산을 저장해서 같은 방식의 계산을 방지한다. 계산했을 때 저장되어있지않으면 그 결과를 저장한다.
  -> 해시테이블 이용해서 key는 계산하고자 하는 데이터, value는 결과를 저장한다.
  - 재귀식으로 인해서 중복 계산이 많은 것을 결과를 저장하는 방식으로 단점을 해소했다.
  역시 메모이제이션도 재귀식이다.

function fibo2(n, memo){ k
  if(n==0||n==1) return n;
  if(memo[n] == null)  {
    memo[n] = fibo2(n - 2, memo) + fibo2(n - 1, memo);//  value 결과를 저장
  //이런 식으로 값을 만들어서 결과값을 나타내기 때문에 그냥 함수에 변수 넣은 게아니다.
  }
  return memo[n];
}

• 재귀식 vs 메모이제이션

  • 재귀식 : 재귀만을 사용해서 중복되는 것들이 있다.

  • 메모이제이션 : 검색하고 없으면 저장하여 결과값

동적프로그래밍 - 타뷸레이션

• 타뷸레이션 : 메모이제이션도 재귀식보다는 효율적이지만, 하나의 함수만 호출하는 것보다는 비효율적이였다.
  타뷸레이션은 상향식을 이용해서 하나의 함수만 호출해서 값을 얻을 수있다.
  이 때 객체를 만들어서 해시테이블처럼 이용해서 계산에 필요한 모든 값들을 저장해놓고 꺼내 쓸 수있도록한다.

• 상향식방식의 피보나치 수열 구하긔
  

  function fibo3(n){
    if(n<=1) return n;
    let table =[0,1];
    for(let i=2; i<=n; i++){
      table[i] =table[i-2] + table[i-1];
    }
    return table[n];
  }

• 재귀식(O(n^2))< 메모이제이션(O(n))<=타뷸레이션(O(n))
  메모이제이션은 메모리를 사용해 성능을 향상시킬 수있다.

• 동적 프로그래밍이 필요한 분할 정복 문제를 풀 때 상황에 따라 다르겠지만

  
  다루기 어려운 메모리는 재귀식으로 쉽게 해결할 때가 있다.

  • 메모이제이션을 사용해야할 때는 - 재귀식으로 직관적으로 해결할 수 있는 메모리를 하향식으로 해결하고 더많은 메모리를 이용해서 성능을 향상시킨다.

  • 타뷸레이션을 사용하기 적할 할 때는 - 재귀가 직관적이지 않을 경우 상향식인 타뷸레이션으로 접근한다.

  아니 알고리즘 방금했는데 메모이제이션이랑 타뷸레이션 특성을 헷갈려함 빡대가리니 그렇게 달달 외울라고 하니까 이게 이거였나? 하고 헷갈리지 진짜 어이가 없네. 메모이제이션어캐쓰게됐는지 그래서 기존보다 어떤게 나아졌고 뭐는 나빠졌으며 하면서 이어져야되는데 특성! 외우고 아 이게 메모이제이션이엿나,, 이 특성이 타뷸레이션이였나? 이러니까 머리에 안들어오지

운영체제

파일과 파일 시스템

• 파일을 사용자가 저장하려고 할 때 운영체제를 거쳐서 하드디스크에 저장된다.
  파일 시스템 (=운영체제) : 운영체제가 파일을 관리하기위해 만듦
  파일엔 파일테이블이 있는데 페이지테이블은 비슷하다.

• 파일 시스템의 기능
  파일과 디렉토리 생성/수정/삭제,
  파일권한관리 - 다중 사용자 기능을 지원하는 요즘 다른 사용자로부터 파일 보호를 위해서이다.
  무결성 보장 - 파일의 내용이 손상되지 않도록한다.
  백업과 복구
  암호화

• 주변 장치( 캐릭터와 블록으로 전송단위를 나눌 수있다)

  • 파일 시스템은 하드디스크나 flash memory(보조기억장치)에 저장되기 때문에 전송단위는 블록이다.

  • 사용자는 바이트 단위로 접근, 파일관리자가 중간에서 변환해준다.

• 뒤에 확장자를 붙여 (.exe, .txt)확장자에 알맞는 프로그램을 실행시켜 파일을 본다.
  (사진-포토샵, 텍스트 파일 - 메모장 ..)

• 파일은 헤더와 데이터로 이뤄져있다.
  파일의 헤더는 파일의 속성들이 저장되어있다.

• 파일제어 블록(File Control Block) : 파일 관리를 위해 정보를 저장 해놓은 블록이다.
  파일 디스크립터라고도 부르고 파일마다 존재한다. 저장장치에 저장되어있다가 파일이 오픈 시 메모리로 이동된다.
  파일 시스템이 파일 디스크립터를 관리한다.
  사용자는 파일을 파일 시스템이 메모리에 건내준 파일 디스크립터를 이용해서 파일을 볼 수있다.

• 4번째 줄 코드에서 open()했을 때 파일디스크립터,fd를 메모리에 이동시켰다.
  5번째 줄 close()fd를 참조해 파일을 안전하게 닫았다.
  

• 파일은 데이터의 집합이다.
  데이터 집합이 어떻게 이뤄지는지에 따라 종류를 나눌 수있다.

  • 순차파일 구조 : 파일의 내용이 연속적으로 이어진 상태 (카세트 테이프)
    파일디스크립터를 사용해서 처음부터 순차적으로 데이터를 확인할 수있다.
    lseek()함수를 이용해 보고자 하는 데이터의 위치로 파일 디스크립터 위치를 옮긴다.
    - 장점 : 순차적 기록, 단순 구조. 단편화 현상없음
    - 단점 : 특정지점으로 이동 어려움. 데이터 삽입,삭제,탐색에 시간이 많이 걸린다.
    lseek(fd, 10,SEEK_CUR);// 현재 위치에서 10번 앞으로 파일디스크립터를 이동시킨다.
    

  • 직접파일 구조 : 저장하려는 데이터를 해시함수로 저장위치를 정한다.
    - hashTable 자료구조를 이용하고 요즘 사용이 많은 .JSON에서 사용한다.
    - 해시함수처럼 한번에 데이터를 찾을 수있지만 공간낭비가 있을 수있다.

  • 인덱스파일구조 : 순차접근 +직접파일접근 장점 데리고왔다~
    - 순서대로 접근도 할 수 있고 직접 파일에 접근도 할 수있다.
    인덱스 테이블을 만들어서 노래를 클릭했을 때 순차적인 데이터를 참조해서 바로 노래를 들을 수있고
    순차데이터를 이용해서 노래재생을 해 순차적으로 노래를 들을 수 있다.
    

디렉토리

• 파일의 파일. 파일들을 모아둔 파일들

• 관련있는 파일들을 모아둔다.

• 루트디렉토리와 자식디렉토리가 존재한다.

• 유닉스와 리눅스는 루트디렉토리를 /로, 경로도 / 로 표시한다.
  원도우는 루트디렉토리를 c:으로 디렉토리와 디렉토리 경계구분은 \ 로 구분한다.

• 디렉토리는 파일과 같은 구조이다.

  
  파일은 데이터가, 디렉토리는 파일 정보가 저장되어있다.

• 디렉토리도 헤드가 있다!
  루트 디렉토리 헤더 : 디렉토리 정보가 시작하는 위치를 가리키고
  000디렉토리 헤더 는 해당 프로그램의 정보가 시작하는 위치를 가리킨다.

  • 루트디렉토리는 상위 디렉토리가 없어서 ..은 본인을 나타낸다.

• 디렉토리 구조
  초기 파일 시스템의 디렉토리는 루트디렉토리에만 디렉토리가 존재해서 단순했다.
  -> 파일들이 많아지면서 다단계 디렉토리가 생겼다. 일반 디렉토리에서 하위 디렉토리를 만들수 있는 트리구조가 되었다.

  • 바로가기 기능때문에 운영체제는 트리구조에서 순환이 생긴다.

   

파일과 디스크

• 파일시스템은 메모리와 비슷하게 일정한 크기로 나누고 나눈 공간을 블록이라 부른다.
  메모리에선 페이지!

  • 한블록을 1~8KB 로 쪼갠다.

     

  • 파일 제어 테이블 : 파일이 시작하는 블록의 위치 정보도 담고 있다.

• 하나의 파일은 여러 개의 블록으로 이뤄져있고 어떻게 블록을 잇느냐에 따라
  연속할당과 불연속할당으로 나눌 수 있다.

  • 연속할당 : 블록들을 디스크에 연속적으로 저장한다.
    파일 시작블록만 알면 모든 데이터를 접근할 수 있다.

  • 불연속할당 : 비어있는 디스크 공간에 데이터를 분산시켜서 저장하는 방식이다.
    분산된 블록은 파일 시스템이 관리

• 불연속할당의 연결할당 : 자료구조의 연결리스트방식
  NULL을 만날 때까지 데이터를 참조해 모든 데이터를 얻을 수 있다.
  

• 불연속할당의 인덱스 할당

  • 테이블의 블록포인터가 데이터 블록에 직접연결이 아닌 데이터들의 인덱스를 가지고 있는 인덱스 블록을 연결한다.

  • 이 인덱스블록은 파일 테이블의 블록포인터가 가리키게된다.

  • 찾는 것이 블록이아니고 나는 데이터 0,3,4번이 필요해 했을 때 어떤 인덱스를 참조해야되지?하고 찾는것같다.파일 c를 찾을래 위치는1 이구나 그럼 1번 블록으로 ..가 아니고

  • 인덱스 블록에 있는 0,3,4번블록을 참조하면 데이터를 모두 찾을 수있다.

  • 인덱스 할당은 데이터가 많아 테이블이 꽉 찬 경우 인덱스 블록을 더 만들어 연결해 테이블 확장에 용이하다.

     

  •  

    이해가 안가는데 왜 데이터블록이랑 인덱스블록이랑 똑같이 해놨음? 그럼 파일 B는 어캐 인덱스블록에 연결하나?

• 디스크의 크기

  • 디스크의 블록 수를 잘게 자를 수록 공간을 낭비없이 사용가능하지만 각자 신경쓸 블록이 많아진다.
    또 디스크를 크게 자를 경우 내부단편화가 생겨 낭비가 생긴다.

  • ->그럼 디스크의 빈공간을 찾아야되나?
    그럼 처음부터 끝까지 메모리를 뒤져 빈 공간을 확인해야하므로 비효율적이다.

    
    free Block list로 이문제를 해결했다.

  • Free Block List : 디스크의 빈공간을 모아둔 리스트.
    - 그럼 데이터 삭제하면 free block list로 가겠군녀
    => 특정파일 삭제시 실제 모든 데이터를 지우는 게아니고 파일 테이블의 헤더를 삭제하고
    블럭을 free block list에 추가한다.

  • 사용했던 블럭의 데이터는 여전히 남아 포렌식을 이용해 복구하면 데이터 사용이 가능하다.

    
    ex) a파일을 지웠는데 파일에 해당하는 4, 11, 14 블록은 리스트에 올라간다.
    = a파일에 해당하는 블록은 4,11,14블록으로 흩어져있다.

복습할 때 시간이 정말 많이 걸린다. 하루 수업을 두시간동안 복습한거같다. 왤캐 오래걸리지...흑흑