탐색 알고리즘 (Search Algorithm)

◎ 탐색 알고리즘

• 수많은 데이터 중에서 원하는 데이터를 찾아낼 때 사용하는 알고리즘
• 탐색 알고리즘의 종류
  • Linear Search Algorithm(선형 탐색 알고리즘)
  • Binary Search Algorithm(이진 탐색 알고리즘)
  • Hash Search Algorithm(해시 탐색 알고리즘)
  • 기타등등

◎ 이진 탐색(Binary Search)

• 이진 탐색 알고리즘(Binary Search Algorithm)

  • 정렬된 데이터에서 사용
  • 작동 방식
    • step1. 정렬된 배열의 정 가운데의 인덱스 지정
    • step2. 찾으려는 값과 일치하면 종료
    • step3. 중간 인덱스의 값과 비교하여, 필요없는 데이터를 분리
    • step4. 처음부터 반복
  • 한계
    • 배열에만 구현할 수 있다.
    • 정렬되어 있어야만 구현할 수 있다.

• 이진 탐색 알고리즘 사용하는 곳

  • 사전 검색 : 사전에서 단어를 찾을 때 사용
  • 도서관 도서 검색 : 도서관에서 도서코드로 검색시 사용
  • 대규모 시스템에 대한 리소스 사항 파악 : 시스템 부하 테스트에서 예측된 부하를 처리하는데 필요한 CPU 양에 대해서 파악할 때 사용

◎ 선형 탐색(Linear Search)

• 선형 탐색 알고리즘(Linear Search Algorithm) : 일렬로 된 자료를 왼쪽부터 오른쪽으로 차례대로 탐색하는 것
• 장점 : 탐색 알고리즘의 가장 기초가 되는 알고리즘으로 구현하기 매우 쉬움
• 단점 : 배열의 크기가 커질수록 찾는 시간이 오래 걸림 , $O(N)$

◎ 추가 관련 알고리즘

• Hash Search Algorithm : 출처 및 관련 자료
  • 데이터의 '내용' 과 저장한 곳의 'index' 를 미리 연결해 줌으로써 짧은 시간에 탐색할 수 있도록 고안된 알고리즘
  • 탐색 방법: 경우에 따라 여러 방법으로 설정 가능
  • 데이터를 보관하는 알고리즘과 데이터를 찾는 알고리즘을 구현해야 함
• Divide-and-conquer algorithm : 관련 자료1, 관련 자료2
  • 일렬로 나열되어 있는 자료를 계속 반씩 나누어 진행
  • 특정 조건이 되면, 상위 요소에서 값을 줌
  • 그냥 앞에서부터 진행하는 것과 비교하여 더 좋을수도 나쁠수도 있기 때문에, 상황을 고려하여 사용하는 것이 필요