탐색 알고리즘

Search Algorithm ?

• 주어진 데이터에서 원하는 특정 값을 찾는 것.

• Mechanism

  • Linear (선형)
  • Binary (이진)
  • Hashing (해싱)

1. 순차 탐색 - Sequential Search

• Data의 처음부터 끝까지 모든 요소를 비교하며 데이터를 찾아가는 방식 = Linear

• 정렬되지 않은 데이터에서 탐색할 수 있는 유일한 방법

• O(n) 의 시간복잡도를 가진다.

• Pros : 구현이 쉽다.

• Cons : 배열의 크기가 커질수록 시간소요가 길다.

2. 이진 탐색 - Binary Search

• 정렬된 데이터에서 사용

• O(logN) 의 시간복잡도를 가진다.

• Step

  1. 정렬된 Array의 가운데 index 지정
  2. 값과 일치 비교
  3. 찾으려는 값이 크다면, 왼쪽 부분 데이터(작은 부분) 제거, 아니면 반대
  4. 반복

• Pros : Linear Search 보다 명확히 빠른 속도

• Cons : 탐색하려는 배열이 정렬이 되어있어야 한다.

3. Hashing

• Hash Table
  : Data의 해시 값 → Table 내의 주소

• 평균적으로 삽입 / 삭제 / 탐색 작업을 O(1) 의 시간복잡도로 해결 가능

• 최악의 경우 O(n)
  : 모든 Key가 같은 인덱스로 매핑되는 경우처럼

• Python에서는 Dictionary를 통해 해시 테이블을 구현하고 사용할 수 있다.

  • 값 가져오기 : dict.get("value", default)
  • 값 업데이트 : dict['value'] = setValue
  • 값 삭제하기 : del dict['value'], dict.pop('value', else)