[모각코] 2회차(12.30) 결과

01 검색 알고리즘

- 배열 검색을 다룸

01-1 선형 검색 (linear search) -> O(n)

: 무작위로 늘어놓은(선형) 데이터 집합에서 검색을 수행(가장 기본적인 배열 검색 알고리즘)

 

▶ 선형 검색의 종료조건

    - 검색 실패 # n+1

    - 검색 성공 # n

i = 0
"""sequence a에서 key와 값이 같은 원소를 선형 검색"""
while True:
    if i == len(a):
	# 검색 실패
    if a[i] == key:
    	# 검색 성공
    i += 1 # index 증가

- 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법

 

01-1 추가) 보초법(sentinel method)

: 종료 조건 검사 비용(cost)를 반으로 줄이는 방법

- 종료 조건1이 while문에서 삭제될 수 있음!

 

01-2 이진 검색 (bineary search) -> O(log n)

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

- 정렬된 데이터!

pl

pc

pr

pl: 맨 앞 원소 인덱스

pc: 중앙 원소 인덱스

pr: 맨 끝 원소 인덱스

 

▶이진 검색의 종료 조건

    - a[pc]와 key가 일치하는 경우

    - 검색 범위가 더 이상 없는 경우

def bin_search(a: Sequence, key: Any) -> int:
	"""시퀀스 a에서 key와 일치하는 원소를 이진 검색"""

	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 # 검색 실패  

필요한 평균 비교 횟수 = 평균 log n

 

복잡도(complexity)

- 시간 복잡도: 실행하는 데 필요한 시간

- 공간 복잡도: 메모리(기억 공간)와 파일 공간이 얼마나 필요한 지

 

01-3 해시법 (hashing)

: 추가 or 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행

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

+검색, 추가, 삭제 효율적 수행

 

- 원소 값(key)

- 해시값(hash value): 원소값 % 13

- hash table: 해시값을 인덱스로 하여 원소를 새로 저장

- hash function: 키를 해시값으로 변환하는 과정

 

해시 충돌

일반적으로 키와 해시값은 다 대 1(n : 1)이다.

저장할 버킷이 중복되는 현상 -> 충돌(collision)

+ 버킷(bucket): 해시 테이블에서 만들어진 원소

 

해시값이 같은 데이터 저장하기(해시 충돌 해결법)

1) 체인법 (chaining)  = 오픈 해시법(open hasing)

: 같은 해시값 데이터를 연결 리스트로 연결

 

 

2) 오픈 주소법

: 데이터를 위한 해시값이 충돌할 때 재해시(rehash)