[필기] 정보처리기사 8강

TOPIC / 정렬 & 검색 중 검색 파트

1.검색 (SEARCH)

DEF : 갖고있는 데이터 중 있느냐 없느냐 찾아가는 과정의미

1. 검색의 종류
   • 순차검색 (Sequential Search)
     • DEF / 원하는 데이터를 찾으려면 몇 번 검색해야하게?
     • 차례대로 키를 비교해가며 검색하는 방식, 처음부터 끝까지 찾아보는 것이 특징
   • 이진검색 (Binary Search)
     • POINT / 반드시 기본적으로 정렬 돼있음을 상정함
     • UP & DOWN 형식 생각하기 (내가 생각한 숫자가 큰가요 작은가요?)
     • 중간 레코드 번호 M = (L+H)/2
       최소값 L = LOW
       최대값 H = HIGH
     • M과 찾는 값 A를 비교, M>A 이면 H는 M-1로 대체, M<A이면 L은 M+1로 대체..
       이 과정을 반복해서 M=A 일 때 까지 찾는 것
2. 파일의 구조
   • 직접파일 (Direct File)
     • 순차구조와 유사, 출제는 많이 안됨. 읽어보기만 하기.
   • 해싱 (Hashing)
     • 용어를 주로 물어본다.
     • 버킷 (Bucket)/ 하나의 주소를 갖는 파일의 한 구역 / 레코드 수 = 버킷의 크기
     • 슬롯 (Slot)/ 한 개의 레코드를 저장할 수 있는 공간 / 슬롯 * n = 버킷
     • 충돌 (Collision)/ 두 개의 상이한 레코드가 똑같은 버킷으로 해싱될 때 의미
   • 색인 된 순차파일 (Indexed Sequential File)
     • 주로 묻는 토픽 : 인덱스 구역과 종류를 물어봄
       1. 트랙 인덱스
       2. 실린더 인덱스
       3. 마스터 인덱스 
     • 색인된 순차파일의 장단점
       • 장점 :
         1. 순차처리와 랜덤기능의 통용, 융통성있는 처리 가능,
         2. 효율적인 검색과 레코드 삽입삭제갱신 등이 용이하다.
       • 단점
         1. 별도의 기억공간이 필요하다 (색인구역, 오버플로우구역)
         2. 파일 정렬리 필수적이다.
   • 순차파일 (Sequential File)
     • 색인 된 놈하고 안된 놈의 차이점을 생각. 일괄처리에 알맞으며 기억공간의 낭비 X
       
       • 장점:
         • 기억공가느이 효율적인 사용
       • 단점 :
         • 레코드 삽입, 삭제, 수정 시 속도가 느리다.