춤추는초코칩의 일상, 게임, 재테크

 과목 : 데이터베이스

 SECTION043 파일 편성

1. 순차 파일(Sequential File) = 순서 파일

   장점

• 기록 밀도가 높아 기억공간을 효율적으로 사용
• 어떠한 매체에도 적용
• 취급이 용이

    단점

• 순차적으로 검색하기 때문에 검색 효율이 낮다-

2. 색인 순차 파일(Indexed Sequential File) :순차 처리와 랜덤 처리가 모두 가능. 키 값 순으로 정렬시켜 기록하고, 키 항목만을 모은 색인을 구성

• 기본 구역(Prime Area)
• 색인 구역(Index Area)
  • 트랙 색인 구역(Track Index Area)
  • 실린더 색인 구역(Cylinder Index Area)
  • 마스터 색인 구역(Master Index Area)
• 오버플로 구역(Overflow Area)

    장점

• 융통성 있게 처리
• 효율적인 검색 가능. 레코드 삽입, 삭제, 갱신이 용이
• 파일 전체를 복사할 필요가 없음

3.  직접 파일(Direct File) : 랜덤 파일(Random File), DAM(Direct Access Method) 파일

• 임의의 물리적 저장공간에 기록
• 해시 함수를 이요 물리적 상대 레코드 주소를 계산한수 해당 주소에 레코드 저장

 과목 : 데이터베이스

 SECTION041 검색-해싱(Hashing)

 해싱 : Hash Table이라는 기억공간을 할당하고 해시 함수(Hash Function)를 이용하여 레코드 키에 대한 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식

• Collision(충돌 현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
• Synonym : 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합

 Overflow 해결 방법

• 개방 주소법
• 패쇄 주소법
• 재해싱

 과목 : 데이터베이스

 SECTION040 검색(Search)

 제어 검색 : 반드시 순서화된 파일

• 이분 검색(이진 검색, Binary Search) : 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색하는 방식

 과목 : 데이터베이스

 SECTION039 내부 정렬

 삽입 정렬(Insertion Sort) : 정렬된 그룹과 정렬되지 않은 그룹으로 나누어 정렬되지 않은 그룹을 정렬된 그룹으로 삽입

 선택 정렬(Selection Sort) : 최소값을 첫 번째 레코드에 놓음

 버블 정렬(Bubble Sort) :  인접한 두 개의 레코드 키 값을 비교하여 제일 큰 값을 마지막 레코드에 놓음

 과목 : 데이터베이스

 SECTION038 정렬(Sort)의 개요

 정렬 방식

• 내부 정렬
  • 선택법 : 히프 정렬
  • 삽입법 : 삽입 정렬, 쉘 정렬
  • 교환법 : 버블 정렬, 선택 정렬, 퀵 정력
  • 병합법(합병법) : 2-Way Merge Sort
  • 분배법(분산법) : 기수 정렬(Radix Sort)
• 외부 정렬
  • 밸런스 병합 정렬
  • 캐스케이드 병합 정렬
  • 폴리파즈 병합 정렬
  • 오실레이팅 병합 정렬

 과목 : 데이터베이스

 SECTION037 그래프

 차수(Degree) : 진입 차수(Indegree) + 진출 차수(Outdegree)

 인접행렬(Adjacency Matrix) : 방향 간선이 있으면 행렬의 P_ij = 1, 없으면 P_ij = 0

 최소 비용 신장 트리(MST) : 사이클을 이루지 않도록 연결

 과목 : 데이터베이스

 SECTION036 이진 트리의 운행법

 트리의 운행법

• Preoder 운행 : Root → Left → Right
• Inorder 운행 : Left → Root → Right
• Postorder 운행 : Left → Right → Root

 수식의 표기법

• 전위 표기법(PreFix) : 연산자 → Left → Right
• 중위 표기법(InFix) : Left → 연산자 → Right
• 후위 표기법(PostFix) : Left → Right → 연산자

 * 시험에는 InFix를 PreFIX나 PostFix로 바꾸는 문제가 나옴

 과목 : 데이터베이스

 SECTION035 이진 트리

 이진 트리의 특성 : 레벨 i에서 최대 노드의 수는 2^i-1이다

 이진 트리의 종류

• 정이진 트리 : 전체 노드의 수는 2^k-1
• 전이진 트리
• 사향 이진 트리

 과목 : 데이터베이스

 SECTION034 트리(Tree)

• 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수
• 단말노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드
• 깊이(Depth, Height) : 트리에서 노드가 가질 수 있는 최대의 레벨

 과목 : 데이터베이스

 SECTION033 큐(Queue)와 데크(Deque)

 큐(Queue) : 선입선출(FIFO : First In First Out)

• 프러트(F, Front) 포인터 : 가장 먼저 삽입된 자료의 기억공간, 삭제 작업시 사용
• 리어(R, Rear) 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억장소, 삽입 작업시 사용
• 운영체제의 작업 스케줄링에 사용

 데크(Deque) : 삽입과 삭제가 양쪽 끝에서 발생