🖇️알고리즘 스터디 2주차(2)

03.검색 알고리즘

검색?
어떤 조건을 만족하는 데이터를 찾아내는 것.

키?
주목하는 항목. 주로 데이터의 일부.

검색의 종류?
배열 검색/ 연결 리스트 검색/ 이진 검색 트리 검색

배열 검색의 알고리즘

1) 선형 검색: 무작위로 늘어놓은 데이터 집합에서 검색을 수행
2) 이진 검색: 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행
3) 해시법: 추가, 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행
- 체인법: 같은 해시값 데이터를 연결 리스트로 연결하는 방법
- 오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법

1-1) 선형 검색 seq_search()

원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘
종료조건 1. i==len(a) 2.a[i]=key
아래는 임의의 자료형인 시퀀스에서 검색할 수 있음.

from typing import Any, Sequence

def seq_search(a: Sequence, key: Any) -> int:
	i=0
    
    while True:
    	if i==len(a):
        	return -1	#검색에 실패하여 -1 반환
        if a[i]==key:
        	return i	#검색에 성공하여 현재 검사한 배열의 인덱스 반환
        i+=1
    ###############or#################
    for i in range(len(a)):
    	if a[i]==key:
        	return i
    return -1

if __name__='__main__':
	num=int(input('원소 수 입력: '))
    x=[None]*num
    
    for i in range(num):
    	x[i]=int(input*f'x[{i}]: '))
        
    ky=int(input('검색할 값 입력: '))		#검색할 키 ky를 입력받음
    
    idx=seq_search(x, ky)				#ky와 값이 같은 원소를 x에서 검색
    
    if idx==-1:
    	print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
    	print(f'검색값은 x[{idx}]에 있습니다.')

1-2) 보초법

맨끝에 검색할 키값을 보초로 추가
-> 종료조건 1번을 판단할 필요가 없음
-> 반복을 종료하는 판단횟수를 절반으로 줄임

from typing import Any, Sequence
import copy

def seq_search(seq: Sequence, key: Any) -> int:
	a=copy.deecopy(seq)		#seq 배열 복사
    a.append(key)			#보초 key 추가
    
    i=0
    while True:
    	if a[i]==key:
        	break
        i+=1
    return -1 if i==len(seq) else i
(생략)

2-1) 이진검색 bin_search()

원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘
종료조건 1.a[pc]와 key가 일치하는 경우 2.검색 범위가 더 이상 없는 경우(=pl이 pr보다 커짐)

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int:
	pl=0			#검색 범위 맨 앞 원소의 인덱스
    pr=len(a)-1		#검색 범위 맨 끝 원소의 인덱스

	while True:
    	pc=(pl+pr)//2	#중앙 원소의 인덱스
        if a[pc]==key:
        	return pc	#검색 성공
        elif a[pc]<key:
        	pl=pc+1		#검색 범위를 뒤쪽 절반으로 좁힘
        else:
        	pr=pc-1		#검색 범위를 앞쪽 절반으로 좁힘
		if pl>pr:
        	break
    return -1			#검색 실패
    
if __name__='__main__':
	num=int(input('원소 수를 입력하세요: '))
    x=[None]*num		#원소 수가 num인 배열 생성
    
    print('배열 데이터를 오름차순으로 입력하세요.')
    
    x[0]=int(input('x[0]: '))
    
    for i in range(1, num):
    	while True:
        	x[i]=int(input(f'x[{i}]: '))
            if x[i] >= x[i-1]:		#바로 직전에 입력한 원솟값보다 큰 값 입력
            	break
                
    ky=int(input('검색할 값을 입력하세요.: '))	#검색할 키값 ky 입력
    
    idx=bin_search(x, ky)
    
    if idx==-1:
    	print('검색값을 갖는 원소가 존재하지 않음')
    else:
    	print(f'검색값은 x[{idx}]에 있음')

2-2) 복잡도

1. 시간 복잡도
   데이터 수 n과 무관하게 1번 실행되는 복잡도 ex.return : O(1)
   n에 비례하는 횟수만큼 실행되는 복잡도: O(n) (실행횟수는 평균)

O(f(n))+O(g(n))==O(max(f(n),g(n)))
->2개 혹은 그 이상의 계산으로 구성된 알고리즘의 전체 복잡도는 차원이 가장 높은 복잡도를 선택함.

선형검색 알고리즘의 복잡도: O(1)+O(n)+O(1)+O(n)+O(1)=O(max(1,n,n,1,n,1))=O(n)
이진검색 알고리즘의 복잡도: O(1)+O(1)+O(log n)+O(1)+O(log n)+...+O(1)=O(log n)

3-1) 해시법

'데이터를 저장할 위치=인덱스'를 간단한 연산으로 구하는 것.
해시값: 배열의 키(=원소의 값)를 원소 개수로 나눈 나머지. 데이터에 접근할 때 기준
해시 테이블: 해시값을 인덱스로 한 배열에 키를 저장
버킷: 해시 테이블에서 만들어진 원소

해시 충돌: 키와 해시값의 대응관계는 일반적으로 n:1. 저장할 버킷이 중복되는 현상.

sol1. 체인법 (=오픈 해시법)

해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법.
Node 클래스:
필드-key, value, next
개별 버킷을 나타냄, 키와 값이 짝을 이루는 구조, 키에 해시함수를 적용하여 해시값을 구함.

from __future__ import annotations
from typing import Any, Type
import hashlib

class Node:
	def __init__(self, key: Any, value: Any, next: Node)->None:
    	self.key=key
        self.value=value
        self.next=next

ChainnedHash 클래스:
필드-capacity(해시테이블의 크기), table(해시테이블을 저장하는 list형 배열)
key가 int형인 경우 / int형이 아닌 경우

1) search()
1. 해시 함수를 이용하여 키를 해시값으로 변환
2. 해시값을 인덱스로 하는 버킷에 주목
3. 버킷이 참조하는 연결리스트를 맨 앞부터 차례로 스캔. 키와 같은 값이 발견되면 검색에 성공, 원소의 맨 끝까지 스캔해서 발견되지 않으면 검색에 실패.

2) add()
1,2. (동일)
3. 버킷이 참조하는 연결 리스트 맨 앞부터 차례로 선형 검색, 키와 같은 값 발견 시 키가 이미 등록된 경우이므로 추가 실패. 원소 맨끝까지 발견되지 않으면 해시값인 리스트의 맨 앞에 노드 추가

3) remove()
1,2. (동일)
3. 버킷이 참조하는 연결 리스트 맨 앞부터 차례로 선형 검색, 키와 같은 값 발견 시 그 노드를 리스트에서 삭제, 그렇지 않으면 삭제에 실패.

4) dump() : 해시테이블의 내용을 한꺼번에 통째로 출력

sol2. 오픈 주소법

충돌이 발생했을 때 재해시를 수행하여 빈 버킷을 찾는 방법(닫힌 해시법)
원소 추가- 선형 탐사법
원소 삭제- 해시값이 다른 값의 검색 혼돈을 막기 위해 삭제 완료된 위치 버킷에 속성 ★을 저장
- 비어있는 버킷이 '-'
원소 검색- ★을 만날 시 재해시 반복하여 검색 성공