자료구조와 함께 배우는 알고리즘 입문 [파이썬] - 3장. 검색 알고리즘

3-1. 검색 알고리즘이란

선형 검색

• 무작위로 늘어놓은 데이터 집합에서 검색을 수행

이진 검색

• 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행

해시법

• 추가, 삭제가 일어나는 데이터 집합에서 아주 빠른 검색을 수행
  • 체인법: 같은 해시값 데이터를 연결 리스트로 연결하는 방법
  • 오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법

---

3-2. 선형 검색

• 배열에서 검색하는 방법 중 가장 기본적인 알고리즘

  직선 모양으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지
  맨 앞부터 스캔하여 순서대로 검색하는 알고리즘

• 반복할때마다 두가지 종료 조건을 체크
  • 배열 끝을 지났는지
  • 원소를 찾았는지

• 보초법(sentinel method)
  • 검색하려는 값을 배열 맨 끝에 추가 이때 저장하는 값을 ‘보초’
  • ‘종료조건 - 배열 끝을 지났는가’ 를 판단하지 않아도 됨

---

3-3. 이진 검색

• 배열이 정렬되어 있어야한다.
• 검색 범위를 반으로 줄여가며 탐색

검색 방법

1. 첫번째 검색범위 0 ~ n-1, 중앙 인덱스 pc = (n-1)//2
   
   
2. 중앙값보다 키 값이 크다면 왼쪽은 검색에서 제외,
   시작 범위: pc +1로 업데이트, 다시 중앙값 찾아서 반복
   
   
3. 중앙값보다 작다면 오른쪽은 검색에서 제외,
   끝 범위: pc-1로 업데이트, 중앙값 찾아서 반복
   
   
4. 검색범위가 없거나, 중앙값과 키 값이 일치하면 종료

• 평균 비교 횟수 log n, 검색 실패 경우: log(n+1), 성공할 경우: log n -1

# 바이너리 서치
# data 중에서 target 을 검색하여 index 값을 return 한다.
# 없으면 None을 return한다.

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

---

3-4. 해시법

[해시법에 대한 자세한 설명 링크]

해시법 (with Python)

• ‘데이터 저장할 위치 = 인덱스’ 를 간단한 연산으로 구하는것
  • 검색과 함께 데이터 추가 삭제도 가능

원소의 값을 원소 개수로 나눈 나머지 = ‘해시값’
해시값을 사용하여 새로운 배열을 만든다 = ‘해시 테이블’
새로 추가할 값을(ex, 35) 원소 개수(ex, 13)로 나눈 나머지(ex, 9)에
해당하는 인덱스(ex, x[9])에 저장

• 이렇게 키를 해시값으로 변환하는 과정을 ‘해시함수’
• 해시 테이블에서 만들어진 원소를 ‘버킷’ x[i]
• 버킷에 이미 값이 들어있는 경우를 ‘해시 충돌’

• 해결방안
  • 체인법(오픈 해시법)
    • 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법
  • 오픈 주소법(닫힌 해시법)
    • 충돌이 발생하면 키에 1을 더해서 빈 버킷을 찾을 때까지 해시를 반복
    • 원소를 삭제하면 해당 버킷에 삭제완료임을 나타내는 속성 저장

---

복잡도

• 시간 복잡도: 실행하는데 필요한 시간
• 공간 복잡도: 메모리와 파일공간이 얼마나 필요한지
• 가장 높은 복잡도 우선