3-1장 검색 알고리즘 - 검색과 키 그리고 배열

 

해당 내용은 Do it! 자료구조와 함께 배우는 알고리즘 입문 C 언어 편 (전면 개정판)을 기반으로 작성되었습니다.

---

3-1장 검색 알고리즘 - 검색과 키 그리고 배열

검색 알고리즘이란

- 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 것

 

검색과 키

검색(searching) 과정

1. 국적이 한국인 사람을 찾는다
2. 나이가 21세 이상 27세 미만인 사람을 찾는다
3. 어떤 낱말과 발음이 가장 비슷한 이름의 사람을 찾는다. 

 

이때 검색의 공통점은 특정 항목에 주목한다는 점이다. 여기서 주목하는 특정 항목을 키(key)라고 한다.

데이터가 단순한 정수값이면 데이터값을 키값이라고 생각해도 좋지만 대부분의 경우에서 키는 데이터의 '일부'이다. 

1. 키값과 일치하도록 지정한다. (한국)
2. 키값의 구간을 지정한다. (21세 이상 27세 미만)
3. 키값과 비슷하도록 지정한다. (발음이 가장 비슷한 이름)

 

배열 검색 종류 3가지

1. 선형 검색
- 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다.
2. 이진 검색
- 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다. 
3. 해시법 
- 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다. 
- 데이터 검색을 비롯해 추가나 삭제들을 더 효율적으로 수행하는 종합적인 방법이다. 
- 해시법 종류
   1. 체인법: 같은 해시값의 데이터를 선형 리스트로 연결하는 방법
   2. 오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법

각 검색은 다음 장에서 자세히 다룹니다.

 

5. 검색 종류가 왜 이렇게 많은가?

- 데이터 집합이 있을 때 '검색만 하면 되지!' 라고 생각한다면 검색에 사용할 알고리즘은 계산 시간이 짧은 알고리즘을 선택하면 된다.

- 만약 데이터 집합을 검색 + 데이터 추가, 삭제 등을 자주할 것이라면, 검색 이외의 작업에 소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야한다. 

- 데이터 추가를 자주하는 경우 검색이 빠르더라도 데이터 추 가 비용이 많이 들어가는 알고리즘은 피해야 한다. 

검색만 필요한 데이터 집합일 경우 : 계산 시간이 짧은 알고리즘 선택

검색 + 데이터 추가, 삭제, 수정 등이 필요한 데이터 집합일 경우 : 데이터 추가 비용이 적은 알고리즘 선택

 

 

6.  알고리즘 선택 방법

용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택해야 한다.