참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021 동적 계획법(Dynamic programming)은 1950년대 미국 수학자 벨맨(Richard Bellman)이 만든 용어로, 다단계 의사 결정 프로세스를 최적화하는 일반적인 방법으로 처음 소개되었다. 큰 문제를 작은 문제로 나누고, 그 결과를 저장해 두었다가 재사용하는 문제 해결 ...

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

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

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

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