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

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

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

  ㅇ 검색 문제의 해  :  결국, 원소의 위치


2. 검색 알고리즘의 특징

  ㅇ 자료구조에 의존 함
     - 例) 배열(가장 기초적), 리스트, 트리(이진 검색 트리 등), 그래프, 문자열, 해시 테이블 등

  ㅇ 시간 복잡도를 고려한 최적화 중요
     - 例) 선형 검색 : O(n), 이진 검색 : O(log n), 해시 검색 : O(1) 등

  ㅇ 공간 복잡도와의 상충관계
     - 例) 해시 테이블은 빠른 검색(O(1))을 제공하지만, 추가적인 메모리 필요

  ㅇ 최악의 경우를 고려한 설계 필요
     - 例) 해시 테이블은 충돌이 많아지면 최악의 경우 O(n)까지 성능이 저하될 수 있음

  ㅇ 탐색 이외의  연산도 필요  :  탐색, 정렬, 삽입, 삽입, 삭제 등 
     - 例) BST는 삽입,삭제를 잘 관리해야 검색 성능이 유지됨 (즉, 균형 유지 필요)

  ※ (참고 용어)
     - 키 (Key)         :  다른 원소와 구별할 수 있는 요소
        . (키 : 자료를 정렬하는데 기준이 되는 값들  ☞ 키(Key) 참조)
     - 레코드 (Record)  :  1 이상의 요소들이 서로 관련지어 모여진 자료 집합


3. 검색 알고리즘 종류

  ㅇ 순차 탐색 (sequential search) / 선형 탐색 (linear search)
     * (가장 간단하고 직접적인 탐색 방법)
     - 실행 방식
        . 처음 위치부터 순차적으로 살펴보면서 값이 있는지 보는 가장 단순한 검색 방법
     - 시간복잡도  :  O(n)
        . 탐색 성공시, 평균 (1 + 2 + ... + n)/n = (n+1)/2번의 비교 필요
        . 탐색 실패시, 최악 n번의 비교 필요
     - 적용 : 정렬된 자료와 정렬되지 않은 자료 모두 가능
     - 비 정렬 순차 검색  :  원하는 키값이 나올때까지 처음부터 끝까지 수행
     - 기 정렬 순차 검색  :  중도에 키값 보다 큰 키값이 나오면 수행 중지

  ㅇ 이진 탐색 (binary search)                              
     - 실행 방식
        . 기 정렬되어있는 순서 리스트에서 만 가능한 검색 방법
        . 중앙 위치로부터 탐색 범위를 반씩 줄이면서 자료를 찾는 방법   ☞ 분할 정복법 참조
     - 시간복잡도  :  O(log n)
     - 적용  :  정렬된 자료 만 가능

  ㅇ 탐색 트리에 의한 방법
     - 이진 검색 트리의 탐색
     - B 트리 등

  ㅇ 그래프 탐색
     - 깊이 우선 탐색 (Depth First Search, DFS)
     - 너비 우선 탐색 (Breadth First Serach, BFS)

  ㅇ 해싱 탐색