[Java] 검색 알고리즘

본 포스팅은 'Do it! 자료구조와 함께 배우는 알고리즘 입문 Java편'을 스터디 한 내용입니다.

 

검색하기

- 특정 항목에 주목하는 것은 검색하기의 공통점이며, 특정항목은 키(Key)라고 함

- 국적을 검색하는 경우 국적이 키(key)이고, 나이를 검색하는 경우 나이가 키(key)임.

- 키(key)는 데이터 값 뿐만 아니라, 데이터의 '일부'임

 

배열에서 검색하기

배열 검색 이미지(글쓰는 개발자)

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행

2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행

3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행

    - 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법

    - 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

 

데이터 추가 비용

검색만하면 된다면 검색에 사용할 알고리즘 시간이 가장 짧은 것을 선택해도 무방함. 그러나 데이터 집합에 대한 검색 뿐만 아니라 데이터의 추가, 삭제 등을 자주하는 경우라면 검색 이외 작업에 드는 비용을 종합적으로 평가해 알고리즘을 선택해야 함. 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택할 것.

 

참고사항 : 데이터 추가비용이 많이 드는 경우

학생의 키(height)를 배열에 담고 검색하는 경우, 검색속도는 빠르지만 학생이 전학을 가거나 올 경우 이후 데이터를 밀어내야 하는 경우가 발생하기 때문에 이 경우, '배열 검색 속도는 빠르지만 데이터 추가를 위한 비용이 많이 든다.'라고 함.