검색 알고리즘 (선형/이진/해시)

검색 알고리즘이란?

: 하나 또는 여러개의 키를 조건으로 데이터 집합에서 원하는 값을 찾아내는 것

• 선형 검색 : 무작위 데이터 집합에서 검색
• 이진검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서의 빠른 검색
• 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서의 빠른 검색

---

1. 선형 검색

• 정의 : 직선(선형)으로 늘어선 무작위 데이터 집합 (ex 배열) 에서 검색

• 방식 : 원하는 키값의 원소를 찾을 때까지 맨 앞에서부터 스캔

• str 형 문자열도 검색 가능

  • 선형 검색 종료 조건 : 1) 검색 실패 , 2) 검색 성공
    • 배열 원소 개수가 n개라면, 조건 판단 횟수는 평균 n/2 번

1-1. 보초법

: 선형 탐색에서 종료조건을 검사하는 cost을 반으로 줄이는 방법

• 방법 : 검색하고 싶은 키값을 배열 마지막에 저장 (저장값 = 보초 sentinel)
• 절차 예시
  1) 기존 배열을 복사해 검색값을 배열 끝에 넣고 반복문을 돌린다.
  2) 검색에 성공했다면 반복문을 종료한다.
  3) 복사 배열의 len 와 찾은 배열 원소의idex가 동일하다면 검색에 실패했음을 알 수 있다.

def seq_search(seq: Sequence, key: Any) -> int:
  copy_lst = copy.deepcopy(a_lst)
  a_lst.append( key )
  i = 0
  while true:
     if a[i] == key: break
     i += 1
  return -1 if i == len(copy_lst) else i

idx = seq_search(a_lst, key)

if idx == -1 : print("검색값을 갖는 원소가 없다")
else: print(f'검색값은 a_lst[{idx}]에 있다')

---

2. 이진 검색

• 장점 : 배열의 정렬를 전제로 이루어지며, 선형검색보다 빠르게 검색 가능
  • 오름차/내림차순으로 정렬되었을 때 더 효율적으로 검색 가능

• 검색 범위 : 맨 앞, 맨 끝, 중앙 인덱스 = 0, n-1, (n-1)//2

• 배열의 중앙 원소의 값과 일치/대소 비교 조건으로 탐색 범위를 좁혀감

  • 이진 검색 종료 조건 : 1) array[mid]와 key 가 일치하는 경우 2) 검색 범위가 더 이상 없는 경우
    • 필요 비교 횟수는 평균 log n
    • 검색 성공 log n-1 / 검색 실패 [log(n+1)]

---

3. 복잡도

• 알고리즘의 성능평가의 객관적 기준

1. 시간 복잡도 : 실행에 필요한 시간을 평가
2. 공간 복잡도 : 메모리와 파일 공간이 얼마나 필요한지 평가

3-1. 선형 검색의 시간 복잡도

• 실행 횟수가 1번 -> 복잡도 O(1)

  • O(1)의 필요계산 시간은 변하지 않음

• 실행 횟수가 n/2번 -> 복잡도 O(n)

  -> n에 비례 하는 횟수만큼 실행되는 경우, 복잡도는 O(n)

  • n 이 점점 커지면 O(n)에 필요한 시간도 길어짐

• 2가지 계산으로 구성된 알고리즘의 복잡도는 높은 쪽의 복잡도를 우선시 함

  • O(1) + O(1) + O(n) + O(1) = O(max(1, 1, n, 1) = O(n)

  📌 Plus : 리스트 또는 튜플 에서의 검색

  • obj.index(x, i , j) -> 함수의 호출 인수 중 j 또는 i, j를 생략 가능

    • x과 같은 원소가 있다면 가장 작은 인덱스를 반환
    • 찾는 원소가 없다면 예외 처리 -> ValueError

  📌 Plus : 복잡도 표기법 : O(n) = 오더n, 오더

3-2. 이진 검색의 시간 복잡도

• 실행 횟수가 log n 번 -> 복잡도 O(log n)
  • 1 < (log n) < n

---

4. 해시법

: 데이터 저장 위치 = 인덱스 를 간단한 연산으로 구하는 것

• 특징 : 데이터의 검색 / 추가 / 삭제를 효율적으로 수행

• 해시(값): key를 해시함수라는 함수에 Input으로 넣어서 Ouput으로 나오는 것

  • ex) 배열의 key(원소값)를 원소 개수로 나눈 나머지 a[i]//len(a)

• 해시 테이블 : 해시값을 인덱스로 원소를 새로 저장한 배열

  • ex) 길이가 13인a 배열에 35을 추가해도 a[5] 이후의 원소들을 이동시킬 필요 없음

• 해시 함수 : key를 고정된 길이의 해시로 변환 ( 해당 과정을 Hashing 이라고 함)

  • ex) 나머지 연산 (+응용) 할때 주로 사용

• 버킷 : 해시 테이블에서 만들어진 원소 / 데이터가 저장되는 곳

• 해시 충돌
  : 해시 함수로 해시 테이블에 A라는 값을 추가했을 때 이미 해당 버킷에 B라는 값이 들어가 있을 때

  • 키와 해시의 대응관계는 n:1 이다.

    • 충돌 대처 방법 :
      1) 체인법 : 해시값이 같은 원소를 연결 리스트로 관리
      2) 오픈 주소법 : 빈 버킷 찾을 때까지 해시 반복

4-1. 체인법 (오픈 해시법)

: 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법

• 인덱스를 해시값으로 하는 같은 해시값을 갖고 있으므로 연결 리스트의 앞쪽 노드를 참조해 버킷에 저장
  ex) hashTb[4] --참조--> 64 --참조--> New Value

• Node 클래스 : 개별 버킷

  • 구성 필드 : Key, Value, Next

  (내용 추가 예정 23.08.14)

...
<기존 원소 추가 예시>

• 예시 : 오름차순으로 정렬된 a배열에 35 를 추가할 때
• a[5] 와 a[6] 사이에 값 추가를 위해 이진 검색법으로 검사
• a[6] 부터 모든 원소를 한칸씩 뒤로 이동
• a[6] 에 35 대입
  -> 원소 이동 (=삭제) 에 필요 복잡도 = O(n)

출처 : do it! 자료구조와 알고리즘 입문 (파이썬 편)
https://go-coding.tistory.com/30