참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021 체이닝(chaining)은 선형 조사법과 달리 하나의 버킷에 여러 개의 레코드를 저장할 수 있도록 하는데, 이때 버킷은 크기를 변경할 수 있는 리스트 구조로 구현한다. 따라서, 하나의 버킷에서 아무리 많은 충돌이 발생하더라도 문제 없이 처리할 수 있다. → 선형 조사법의 cluster...

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021 1. 선형 조사에 의한 오버플로 처리 해시 함수로 계산된 버킷에 빈 슬롯이 없으면 그 다음 버킷들을 순서적으로 조사하여 빈 슬롯이 있는지를 찾는다. 이때 비어있는 공간을 찾는 것을 조사(probing)라고 한다. 선형 조사법(linear probing)은 해시 테이블의 k번 째 위치인 ...

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021 1. 해싱(Hashing)이란? 공간을 이용해 시간 벌기 전략의 탐색 기법이다. 이상적인 경우의 시간 복잡도: $O(1)$ < 해싱의 기본 전략 > 지금까지의 탐색 방법들은 탐색키를 테이블에 저장된 각 레코드의 키값과 하나씩 비교하여 원하는 항목을 찾는 방식이었다...

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021 보이어 무어 알고리즘(Boyer-Moore algorithm)은 호스풀 알고리즘에 추가적인 휴리스틱을 더해 효율을 높이고자 한 방법이다.

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021 문자열 매칭 문제는 길이가 $n$인 텍스트 속에서 길이가 $m$인 패턴의 위치를 찾는 문제이다. 억지 기법(brute force)을 적용하면 최악의 경우 텍스트의 $n-m+1$개 위치에서 각각 $m$번의 비교를 해야 하므로 시간 복잡도는 $O(nm)$이지만, 평균적으로는 이보다 훨씬...