[은행 필기대비 자료구조-06] 검색 알고리즘★순차★이진★해싱★

1. 순차 검색(Linear Search)

==> 대상 데이터를 순서대로 하나씩 비교하면서 원하는 데이터를 찾는 검색 방식

 

==> 자료의 범위를 모르거나 자료가 정렬되어 있지 않아도 검색이 가능하다.

 

==> (n+1) /2

 

2. 제어 검색(Controlled Search)

 1) 이진 검색(Binary Search)

==> 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

 

==> 중간 값을 임의의 값으로 정하고, 그 값과 찾고자 하는 값의 대소비교를 하는 방식

 

==> 정렬된 리스트에서만 사용, 검색을 반복 할때마다 목표 값을 찾을 확률이 2배가 되므로 속도가 빠르고 효율이 좋다.

 

 

EX)  17, 28, 43, 67, 88, 92, 100 ==> 오름차순 ==> 43 찾기

 

1. 임의의 중간값 67 선정

 

2. 67 > 43 ==> 43이 왼쪽에 위치

 

3. (17 , 28 , 43) ==> 중간값 28 선정

 

4. 28< 43 ==> 43이 오른쪽에 위치

 

5. (43) ==> 중간값 43 선정

 

6. 43 == 43 완료

 

 

추후 PYTHON CODE 첨부 예정

 

장점 :

 

1. 탐색 효율이 좋고, 탐색 기간이 적게 소요

 

2. 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어든다.

 

 

3. 해싱(Hashing Search)

 

==> 레코드의 참조 없이 키 변환에 의해 원하는 레코드에 직접 접근할 수 있도록 구성, 키 변환 값이 같은 경우 오버플로우가 발생

 

==> 찾는 레코드의 키 값을 주소 변환하여 해당 위치에서 검색 ==> 조사 횟수가 적다.

 

 

1> 해싱 관련 용어 

 

Bucket : 해싱(Hashing) 함수에 의해 계산되는 홈 주소(Home Address)에 의해 만들어지는 해시 테이블 내의 공간 의미

 

 

DAM(Direct Access Mehtod):  는 레코드에서 임의의 키 필드를 정해서 해싱 함수에 의해 주소로 변환 , 해당 위치에 레코드 저장

 

 

 

2> 해싱 함수 

 

==> 키 값을 이용해서 레코드를 저장할 주소를 산출해 내는 수학식 

 

폴딩 방법(중첩법) :

 

숫자를 키로 사용할 때 자릿수를 기준으로 몇 부분으로 나눈 다음 각 부분을 겹쳐서 더해서 해시 주소 얻음

 

==> 배타적 논리합(XOR) 사용!

 

 

제산법 : 레코드의 키 값을 임의의 소수(배열의 크기)로 나누어 그 나머지 값을 해시 값

 

기수 변환법 :레코드의 키 값을 임의의 다른 기수 값으로 변환하여 그 값을 홈 주소로 사용

 

무작위법 :난수 생성 프로그램을 이용하여 각 키의 홈 주소 얻는 방법

 

중간 제곱법 : 값을 제곱하여 결과값 중 중간 자릿수를 선택하여 그 값을 홈 주소로 사용

 

숫자 분석법 : 주어진 모든 키 값들에서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 선택

 

 

3> 오버플로(OverFlow) 처리 방식

 

개방 주소(Open Addressing) 방식 : 충돌이 일어난 자리에서 그 다음 버킷을 차례로 검색하여 처음 나오는 빈 버킷에 데이터를 넣는 방식

 

재해싱(Rehashing) 방식 : 여러 개의 해싱 함수를 준비한 후 충돌이 발생하면 새로운 해싱 함수 이용하여 새로운 홈 주소 구하기

 

폐쇄 주소: 해시 테이블에서 서로 다른 키 값의 데이터가 해시 함수에 의해 같은 버킷에 배치되어 충돌 ==> 포인터와 같은 해시 함수 값을 갖는 레코드를 연결 리스트로 연결