알고리즘 2

[자료구조/Python] 해시(Hash), 해시테이블(Hash Table)

해당 포스팅은 [Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편]과 [파이썬 알고리즘 인터뷰]을 통해 공부한 내용이 정리되어 있습니다. 해시/해쉬(Hash)란? 흔히 자료구조에서의 해시는 해시 테이블(Hash Table)을 뜻하며, Key와 Value로 어떠한 대응 관계를 나타내는 자료구조임 언어에 따라 해시, 맵, 사전 등으로 불리지만 파이썬에서는 딕셔너리 자료형을 통해 구현(충돌 시 오픈 어드레싱 방식을 사용)되어 있음 해시법(Hashing) 해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구현하는 것을 뜻함 다시 말해 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것! 원소의 검색, 추가·삭제를 모두 효율적으로 수행할 수 있음: O(1) 우리는 해시 테이블의 인덱스..

알고리즘 2024.01.10

[자료형/Python] 딕셔너리(Dictionary)

해당 포스팅은 점프 투 파이썬, 혼자 공부하는 파이썬 책을 보고 1차 정리 후, 추가 공부를 통해 보강하였습니다. 딕셔너리 자료형은 말 그대로 '사전'이라는 의미를 지니며, Key와 Value를 한 쌍으로 갖는 자료형임 Key:Value → baseball:야구, basketball:농구 ... 리스트나 튜플처럼 순차적으로(sequential) 해당 요솟값을 구하지 않고 Key를 통해 Value를 얻음 → 딕셔너리의 가장 큰 특징! 딕셔너리 자료형은 내부적으로 해시 테이블을 이용하므로 데이터의 검색 및 수정에 있어 O(1)의 시간 복잡도를 가짐 자료형 의미 가리키는 위치 선언 형식 리스트 인덱스를 기반으로 값을 저장 인덱스 변수 = [] 딕셔너리 키를 기반으로 값을 저장 키 변수 = {} 딕셔너리의 생성..

알고리즘 2024.01.05
728x90