알고리즘 학습

3장. 더 나은 해싱을 통한 더 나은 삶

이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: [e-mail]

이 장에서는 학습 내용을 살펴봅니다:

• 기호 테이블에 (키, 값) 쌍을 저장하고 키와 연관된 값을 검색하는 방법.¹

• 배열의 크기가 저장된 쌍의 수에 비해 충분히 큰 경우 효율적인 검색을 위해 배열을 사용하여 (키, 값) 쌍을 저장하는 방법.

• 링크된 목록 배열을 사용하여 (키, 값) 쌍을 저장하여 키를 제거하는 추가 기능을 지원하는 방법.

• 효율적인 기호 테이블 크기를 조정하는 방법.

• 연속적인 호출에 따라 작업의 동작이 변경될 수 있는 경우 평균 런타임 성능을 결정하기 위한상각 분석입니다.

• 기하학적 크기 조정이 비용이 많이 드는 크기 조정 작업의 빈도를 줄이는 방법, 즉 put() 평균적으로 O(1) 성능을 상각했다는 의미입니다.

• 계산 해시 함수가 키 값을 균일하게 분배하여 심볼 테이블 구현의 효율성을 보장하는 방법.

값과 키 연결하기

값을 저장하는 대신 특정 키에 값을 연결하기 위해 (키, 값) 쌍의 컬렉션을 저장해야 할 수도 있습니다. 이를 심볼 테이블 데이터 유형이라고 하며, 키만 주어지면 연관된 값을 찾을 수 있습니다. 해싱은 (키, 값) 쌍을 찾기 위해 컬렉션을 처음부터 끝까지 수동으로 검색하는 대신 효율적인대안을 제공합니다. 앞서 설명한 검색 알고리즘보다 성능이 뛰어납니다. 심볼 테이블은 키(및 해당 값)를 제거할 수 있는 경우에도 효율적일 수 있습니다. 예를 들어 오름차순과 같이 특정 순서로 모든 키를 검색하는 기능은 포기하지만, 결과 심볼 테이블은 개별 키와 관련된 값을 검색하거나 저장하는 데 최적의 성능을 제공합니다.

월과 연도의 달력을 인쇄하는 print_month(month, year) 함수를 작성하고 싶다고 가정해 보겠습니다. 예를 들어 print_month('February', 2024) 은 다음과 같이 출력됩니다:

   February 2024
Su Mo Tu We Th Fr Sa
             1  2  3
 4  5  6  7  8  9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29

어떤 정보가 필요하나요? 해당 연도의 해당 월 첫째 날의 요일(위는 목요일)이 필요하며 2월은 28일(2024년과 같은 윤년의 경우 29일)이라는 것을 알아야 합니다. 연도의 각 월 길이를 일 단위로 기록하는 값과 함께 고정 배열인 month_length 을 사용할 수 있습니다:

month_length = [ 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

첫 번째 달인 1월의 일수는 31일이므로 month_length[0] = 31입니다. 2월은 다음 달로 일수가 28일이므로 목록의 다음 값은 28입니다. 올해의 마지막 달인 12월의 일수가 31일이므로 month_length 의 최종 값은 31입니다.

지금까지 이 책에서 설명한 내용을 고려할 때, 같은 길이의 ...