검색 알고리즘(Search Algorithm)

검색 알고리즘에 대하여

 데이터를 검색만 한다면 계산 시간이 가장 짧은 것을 선택하는 것이 좋다. 그러나 검색뿐만 아니라 데이터를 추가하거나 삭제하는 작업까지 수행해야 한다면 검색 이외의 작업에 소용되는 비용까지 종합적으로 고려하여 알고리즘을 선택해야 한다. 고려 대상에는 목적, 용도, 실행 속도, 자료 구조 등이 있다.

 

데이터 추가 비용이 많이 든다는 의미

 배열 데이터의 중간에 새로운 데이터를 삽입하는 경우, 새로운 데이터가 들어가는 자리 이후의 데이터는 전부 한 칸씩 밀어내야 하는데 이 경우 데이터의 추가 비용이 많이 들게 된다.

 

선형 검색(linear search), 순차 검색(sequential search)

 요소가 직선 모양을 늘어서 있어 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다.

 

이진 검색(binary search)

 데이터가 키값으로 이미 정렬되어있다는 전제 조건이 있으며, 정렬된 데이터를 절반으로 나눠 분할 정복 기법으로 값을 찾아낸다. 선형 검색보다 좀 더 빠르게 검색할 수 있다.

 

검색 방법

1. 정렬된 배열의 가장 중간 인덱스를 지정한다.
2. 찾고 있는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료하고 아니면 다음 단계로 넘어간다.
3. 찾고 있는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인한다.
4. 찾고 있는 값이 있는 부분과 없는 부분으로 분리한다.
5. 찾고 있는 값이 있는 부분에서 처음으로 돌아가 반복한다.

 

해시 검색(hash search)

 데이터 검색뿐만 아리나 추가나 삭제 등을 효율적으로 수행할 수 있는 종합적인 방법이다. 데이터의 내용과 저장한 곳의 index를 연결시켜 짧은 시간 안에 탐색할 수 있다.

 

해시법(hashing)

 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하여 검색, 추가, 삭제를 수행한다. 이를 표에 정리한 값을 해시값(hash value)라고 한다. 해시값은 데이터에 접근할 때 사용한다.

 

해시 충돌

해시값을 인덱스로 하여 원래의 키값을 저장한 배열을 해시 테이블(hash table)이라고 한다. 이 해시 테이블의 요소를 버킷(bucket)이라고 하는데 중복된 해시값으로 인해 버킷이 저장될 인덱스가 이미 채워져 있는 경우를 충돌이 일어났다고 한다.

 

충돌 대처법

• 체인법 : 같은 해시값의 데이터를 사슬 모양의 연결 리스트로 연결하는 방법으로 오픈 해시법(open hashing)이라고도 한다.
• 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.