Algorithm

재귀가 성능에 영향을 미치는 경우

• Call Stack

• 중복되는 연산
  → 중복되는 연산을 저장하고, 같은 계산이 필요할 때 저장된 결과를 사용한다.
  → 함수 호출 수가 줄어듦.
  → 성능이 좋아진다.

Memoization

• 계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법

단점

• 속도를 위해서 메모리(저장 공간)를 사용한다.

• 재귀 함수이기 때문에 Call Stack을 차지하는 단점은 변하지 않는다.

Tabulation

• 상향식 계산 방식

• 계산에 필요하지 않을 수 있는 값도 미리 계산해 테이블에 저장하는 방식

Memoization vs Tabulation

• Memoization : 해결하기 힘든 문제를 하향식으로 접근하여 복잡한 문제를 쉽게 해결할 수 있다.

  • 분할 정복을 해결할 때 재귀가 더 직관적인 경우에 유리

• Tabulation

  • 재귀가 직관적이지 않은 경우에 유리

OS

File

• 저장장치에 저장된다.

구조

• Header

  • 파일의 속성이 담겨있다.

• Data

  • 데이터의 집합

데이터 집합 구성에 따른 분류

순차파일구조

• 파일의 내용이 연속적으로 이어진 형태
  ex) 카세트테이프

장점

• 모든 데이터가 순차적으로 기록되기 때문에 공간의 낭비가 없고, 구조가 단순하다.

단점

• 특정지점에 바로 이동이 어려워 데이터를 삽입하거나 삭제하려면 탐색하는데 시간이 오래 걸린다.

직접파일구조

• 저장하려는 데이터의 위치를 해시 함수를 통해 결정하는 구조

• 자료구조에서 Hash Table이라고 불린다.
  ex) JSON

장점

• 해시 함수를 사용하기 때문에 데이터 접근이 굉장히 빠르다.

단점

• 해시함수의 선정이 굉장히 중요하다.

• 저장공간이 낭비될 수 있다.

인덱스 파일 구조

• 순차접근과 직접접근 방식의 장점을 취한 구조

•  <탐색키, 레코드 포인터> 쌍으로 구성

  • 데이터 파일과는 별도로 저장되며, 빠른 검색을 위해 사용된다.

File System

• 파일을 관리하기 위해 OS가 둔 파일 관리자

• 파일 테이블을 이용하여 파일을 관리한다.

기능

• 파일과 디렉토리 생성

• 파일과 디렉토리 수정/삭제

• 파일 권한 관리

• 무결성 보장

• 백업과 복구

• 암호화

동작

• 블록 저장장치에 저장 → 전송 단위 : 블록

• 사용자가 바이트 단위로 파일에 접근이 가능하도록 지원한다.

File Descriptor(= File Control Block)

• OS가 파일을 제어하기 위한 정보를 보관하는 Block

• 파일마다 독립적으로 존재한다.

• 저장장치에 존재하다가 파일이 오픈되면 메모리로 이동한다.

• OS가 관리하고 사용자가 직접 참조할 수 없다.

• 사용자는 File Descriptor를 사용하여 File에 접근할 수 있다.

• 파일의 맨 앞에 위치해서 사용자가 쓰거나 읽기를 시작하면 처음부터 진행한다.

Directory

• 1개 이상의 파일과 자식 디렉토리를 가질 수 있다.

• 운영체제 마다 가장 최상단의 디렉토리 명칭이 다르다.

  • Windows : Partition Name(ex : C:)

  • Unix, Linux : Root('/')

• 디렉토리도 파일정보가 저장되어 있는 하나의 파일이다.

구조

• 디렉토리 헤더 : 디렉토리 정보가 시작하는 위치를 가리킨다.

다단계 디렉토리

• 어떠한 디렉토리에서도 하위 디렉토리를 만들 수 있는 트리 구조

File & Disk

• 전체 디스크 공간을 블록(일정한 크기를 갖는 공간)으로 나누고, 그 공간에 주소를 할당해 관리한다.
  - 일반적으로 한 블록의 크기는 1 ~ 8KB이다.
  - 하나의 파일은 여러개의 블록으로 이루어진다.
  

• 파일시스템은 파일정보를 파일테이블로 관리한다.

• 파일이 시작하는 블록의 위치정보가 담겨있다.
  

블록 연결 방식에 따른 분류

연속할당

• 파일을 구성하는 블록들을 디스크에 연속적으로 저장하는 방식

• 파일의 시작 블록만 알면 파일의 전체를 알 수 있다.

• 외부 단편화가 발생하여 실제로 사용하지 않는다.
  

불연속할당

• 디스크의 비어있는 공간에 데이터를 분산하여 저장하는 방식
  - 분산된 블록은 파일시스템이 관리한다.
  

연결 할당

• 파일에 속한 데이터를 연결리스트를 사용하여 관리한다.

• 파일테이블에는 시작 블록에 대한 정보만 저장하고 나머지는 연결리스트를 이용해 다른 블록에 접근한다.
  

인덱스 할당

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

• 데이터가 많아서 테이블이 꽉 찬경우 인덱스 블록을 더 만들어 연결하기 때문에 테이블 확장에 용이하다.

• 파일 크기가 작다면 데이터를 바로 참조하는 블록 포인터를 이용한다.

• 파일의 크기가 크다면 간접 포인터를 이용해 많은 데이터에 접근할 수 있다.

• i-node라는 방식으로 유닉스와 리눅스에서 많이 사용되고 있다.

Free Block List

• 파일시스템이 효율적인 공간 관리를 위해 빈 공간을 모아둔 목록

• 파일 시스템은 파일의 모든 정보를 지우는 것이 아니라 파일 테이블의 헤더를 삭제하고 Free Block List에 추가한다.
  → 포렌식을 통해 데이터를 복구할 수 있다.