ZLFN.SPACE

본 글에서는 딕셔너리와 해싱을 알아보고, 각 언어의 구현을 알아보며 배운 내용을 체크해보려 합니다.

이 내용은 포항공과대학교의 CSED 233의 내용을 기반으로 하며, 수업에서 다루지 않은 내용은 인용문으로 표기하였거나 별도 명시하였으니 참고바랍니다.

Dictionary ADT

딕셔너리는 추상 자료형_{Abstract Data Types}의 일종으로, 특정 키에 대해 특정 원소가 매핑되는 짝의 집합으로 구성되어 있습니다.

• 구현마다 다르긴 합니다만 대체로 중복키는 허용되지 않습니다.

  Map이라고도 불립...

엣코더 ABC #348의 E - Minimize Sum of Distance 에서 트리 DP, 그중에서도 전방향 트리(全方位木（ぜん ほうい き）) DP를 쓴다고 해서 찾아봤습니다.

이 알고리즘은 일본 외에서는 Rerooting 이라고 불리며, 루트가 정해지지 않은 트리에서 조건에 맞는 루트를 구할 때 유용하게 사용할 수 있는 테크닉입니다. 한국에서는 트리에서의 다이나믹 프로그래밍 분류의 일종으로 취급되지만, 외국에서는 이름을 따 붙힐 정도로 경쟁적 프로그래밍에서 은근 자주 출제되는 알고리즘인 듯 합니다.

개

!! 구 블로그 (Blogger) 에서 가져온 글입니다. 글 일부가 깨져보일 수 있습니다.

탐색이란?

탐색이란 데이터 구조 안의 저장된 정보를 찾는 것입니다.
대표적인 탐색 알고리즘에는 3가지가 있습니다.

• 순차탐색 (Sequential Search)
  혹은 선형탐색 (Linear Search)
• 이분탐색 (Binary Search)
• 해시탐색 (Hash Search)