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. 해쉬 생성
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
          2. 프로그래밍 기법
      1.   프로그래밍 언어론
      2.   구조적 프로그래밍
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 알고리즘 설계
            3. 계산 복잡도
            4. 하노이 탑
            5. 순서도
            6. 재귀 호출
        1.   알고리즘 종류
              1. 알고리즘 분류
              2. 그래프 알고리즘
          1.   기초 알고리즘
          2.   정렬 알고리즘
          3.   검색 알고리즘
            1.   1. 탐색 알고리즘
                2. 해싱 탐색
                3. 해쉬 생성
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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