Searching Algorithm, Search Algorithm   탐색 알고리즘, 검색 알고리즘

(2019-02-11)

순차 탐색, 순차 검색, 선형 검색, 이진 검색

1. 탐색/검색 알고리즘 (Searching Algorithm)

  ㅇ 탐색 문제 
     - 순서 리스트(ordered list) 또는 비순서화된 리스트에서,
       어떤 원소/대상의 존재 및 그 위치를 찾는 것

  ㅇ 탐색 문제의 해 : 원소의 위치


2. 탐색 관련 용어키(Key)        : 다른 원소와 구별할 수 있는 요소
  ㅇ 레코드(Record) : 1 이상의 요소들이 서로 관련지어 모여진 자료 집합


3. 탐색 알고리즘 종류

  ※ 보통, 자료구조 형태에 따라 구분됨

  ㅇ 순차 탐색(sequential search)/선형 탐색(linear search)  ☞ 순차검색 구현 예시
     - 처음 위치부터 순차적으로 살펴보면서 값이 있는지 보는 가장 단순한 검색 방법
     - 시간복잡도 : O(n)
     - 구분
        . 비 정렬 순차 검색 : 원하는 키값이 나올때까지 수행
           .. (의사코드 구현 例)
              
Input  : arr[1,2,...,n], int n, int key
Output : int location

int sequential_search (arr[], n, key) {
   location = 1;
   while ( location <= n )
      if ( arr[location] == key )
         return location;
      location++;
   if ( location > n )
      return NULL;
} 
. 기 정렬 순차 검색 : 중도에 키값 보다 큰 키값이 나오면 수행 중지 ㅇ 이진 탐색 (binary search) - 기 정렬되어있는 순서 리스트에서 만 가능한 검색 방법 . 중앙 위치로부터 탐색 범위를 반씩 줄이면서 자료를 찾는 방법 - 시간복잡도 : O(log n) - 알고리즘 구상/설명 . ① 먼저 상한(high),하한(low)을 정함 . ② 최초 하한은 배열의 첫째값, 상한은 배열의 끝값 . ③ 상한,하한 사이에 중간값을 찾는 루프 .. ⓐ 중간값 지정 (상한,하한의 가운데) .. ⓑ 찾던 값이 중간값 보다 큰지 작은지에 따라, 하한 또는 상한을 재지정 .. ⓒ 찾던 값이 중간값 이면, 검색 끝냄 . ④ 상한,하한 구간을 줄여가는 중에 역전되면, 이 배열에 찾는 값이 없는 것임 - (코드 구현 例) ☞ 이진검색 구현 예시


[검색 알고리즘] 1. 탐색 알고리즘 2. 해싱 탐색 3. 해쉬 생성

 
        최근수정     요약목록     참고문헌