1. 검색/탐색 알고리즘 (Searching Algorithm)
ㅇ 검색 문제
- 순서 리스트(ordered list) 또는 비순서화된 리스트 등에서,
- 어떤 원소/대상의 존재 및 그 위치를 찾는 것
ㅇ 검색 문제의 해 : 결국, 원소의 위치
2. 검색 관련 용어
ㅇ 키 (Key) : 다른 원소와 구별할 수 있는 요소
ㅇ 레코드 (Record) : 1 이상의 요소들이 서로 관련지어 모여진 자료 집합
3. 검색 알고리즘 종류
※ 검색 기법은, 자료구조에 의존 함
- 例) 배열, 선형 리스트, 이진 검색 트리, 문자열 등
. 주로, 배열에서 원하는 데이터를 찾는 알고리즘 : 순차 탐색, 이진 탐색, 해시탐색
ㅇ 순차 탐색(sequential search)/선형 탐색(linear search)
- 실행 방식
. 처음 위치부터 순차적으로 살펴보면서 값이 있는지 보는 가장 단순한 검색 방법
- 시간복잡도 : O(n)
- 적용 : 정렬된 자료와 정렬되지 않은 자료 모두 가능
- 비 정렬 순차 검색 : 원하는 키값이 나올때까지 수행
- 기 정렬 순차 검색 : 중도에 키값 보다 큰 키값이 나오면 수행 중지
ㅇ 이진 탐색 (binary search)
- 실행 방식
. 기 정렬되어있는 순서 리스트에서 만 가능한 검색 방법
. 중앙 위치로부터 탐색 범위를 반씩 줄이면서 자료를 찾는 방법 ☞ 분할 정복법 참조
- 시간복잡도 : O(log n)
- 적용 : 정렬된 자료 만 가능
ㅇ 이진 검색 트리의 탐색
- ... (작성중) ...