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

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

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

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021 입력의 종류에 따라서 리스트의 각 항목들을 단순히 카운트(count)하는 방법으로 정렬할 수 있는데 이러한 정렬 기법을 카운팅 정렬(Counting sort)이라고 한다. < 카운팅 정렬 기본 전략 > 리스트를 한 번 스캔하면서 각 항목이 리스트에 몇 번 나타났는지 빈...

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021 지금까지 다루었던 정렬 방법들은 모두 배열의 요소들을 서로 비교하여 정렬하였다. 그런데 이러한 비교 연산을 사용하지 않고도 데이터를 정렬할 수 있는 독특한 정렬 기법들이 있다. <비교 기반의 정렬(Comparsion based sorting)> 요소들 끼리 ...