Study Blog

https://vibeee.tistory.com/284 검색 알고리즘 - 해시법해시법해시법을 이용하면 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있다.해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 원소 갯수가 13vibeee.tistory.com 지난 포스팅에서 소개했던 것처럼 해시 충돌이 발생할 때 해결하는 방법으로 체인법 외 오픈주소법이 있다.오픈 주소법오픈 주소법은 충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(closed hashing)이라고도 한다. 원소 추가하기아래 그림은 18을 추가하는 과정에서 충돌이 발생하는 상태를 보여준다. 이럴 때 재해시를 수행할 수 있다. 재해시를 위한 해시 함수..

해시법해시법을 이용하면 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있다.해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 원소 갯수가 13인 경우 키를 원소 갯수에 나누면 아래와 같이 해시값을 구할 수 있다. 위 표에서 해시값 부분에서 새로 원소를 구해 저장한 배열을 해시 테이블이라고 하며, 해시 테이블은 아래와 같이 구해지게 된다. 이와 같이 키를 해시값으로 변환하는 과정을 해시 함수라고 하며, 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다.해시 테이블에서 만들어진 원소를 버킷(Bucket)이라고 한다.(위 그림에서 0~12의 인덱스를 가진 배열) 해시 충돌위 해시 테이블에 18이라는 값을 추가하려고 할 때, 18을..

이진 검색 알고리즘을 사용하기 위한 조건→ 배열의 데이터가 정렬되어 있어야 한다.이 조건을 만족한다면 이진 검색은 선형 검색보다 빠르게 검색할 수 있다. 따라서 이진 검색은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다. 이진 검색 알고리즘의 작동 원리검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl, pr, pc라고 칭하고,검색을 시작할 때 pl은 0, pr은 n - 1, pc는 (n - 1) // 2로 초기화한다.(pl은 배열의 맨 앞, pr은 배열의 맨 끝, pc는 배열의 중간의 인덱스를 잡아줘야 하기 때문) 1. a[pc] a[pl]~a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외한다.검색 범위는 중앙 원소 a[pc]보다 뒤쪽..

선형 검색의 종료 조건1) 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 -> 검색 실패2) 검색할 값과 같은 원소를 찾는 경우 -> 검색 성공! 배열 a가 있을 때 검색하는 프로그램은 다음과 같이 나타낼 수 있다.i = 0while True: if i == len(a): # 검색 실패 if a[i] == key: # 검색 성공(찾은 원소의 인덱스는 i) i += 1 선형 검색 알고리즘 코드 1 (while)# while 문으로 작성한 선형 검색 알고리즘from typing import Any, Sequencedef seq_search(a: Sequence, key: Any) -> int: # 시퀀스 a가 있고 key는 아무 자료형, 결과는 int로 반환한다. ..