해시에 대해 알아보자! 📚

해시(Hash)란? 🤔

해시는 키(key)를 사용해 값을 저장하고 검색할 수 있는 자료구조입니다. 해시 테이블(Hash Table)은 데이터를 저장할 위치를 계산하는 해시 함수를 사용해 빠르게 데이터를 검색할 수 있습니다. 대표적으로 딕셔너리(Dictionary)가 있습니다.

해시의 기본 개념 🌟

해시 함수(Hash Function): 키를 입력받아 해시 테이블의 인덱스로 변환하는 함수입니다. 해시 테이블(Hash Table): 해시 함수를 이용해 데이터를 저장하는 배열 기반의 자료구조입니다. 충돌(Collision): 서로 다른 두 키가 동일한 해시 값을 가질 때 발생합니다.

해시의 장단점 🎢

장점 빠른 검색 속도: 평균적으로 O(1) 시간 복잡도로 빠르게 데이터를 검색할 수 있습니다. 유연한 키 타입: 문자열, 숫자 등 다양한 타입의 키를 사용할 수 있습니다. 단점 충돌 처리 필요: 충돌을 해결하기 위한 추가적인 방법이 필요합니다. 메모리 사용: 해시 테이블은 메모리를 많이 사용할 수 있습니다. 파이썬에서 해시 구현 💻 파이썬에서는 딕셔너리를 사용해 해시 테이블을 쉽게 구현할 수 있습니다.

1# 딕셔너리 예제
2hash_table = {}
3hash_table["apple"] = "a fruit"
4hash_table["banana"] = "a yellow fruit"
5print(hash_table["apple"])  # 출력: a fruit
6print(hash_table.get("banana"))  # 출력: a yellow fruit

프로그래머스 해시 문제 🚀

문제: 전화번호 목록 📞 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두어입니다. 구조대: 119 박준영: 97 674 223 지영석: 119 552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않으면 true를 반환하는 함수를 작성해보세요.

입력 예시 phone_book = ["119", "97674223", "1195524421"]

출력 예시 false

코드 작성하기 💻

1def solution(phone_book):
2    phone_book.sort()
3    for i in range(len(phone_book) - 1):
4        if phone_book[i + 1].startswith(phone_book[i]):
5            return False
6    return True
7
8# 테스트
9phone_book = ["119", "97674223", "1195524421"]
10print(solution(phone_book))  # 출력: False

설명 📋

전화번호 목록을 정렬합니다. 정렬된 전화번호 목록에서 앞 번호가 뒷 번호의 접두어인지 확인합니다. 접두어인 경우 False를 반환하고, 끝까지 확인 후 접두어가 없는 경우 True를 반환합니다.

팁 🌟

정렬을 활용하자: 정렬 후 인접한 항목만 비교하면 효율적으로 문제를 해결할 수 있습니다. 문자열 메서드 활용: startswith() 같은 문자열 메서드를 잘 활용하면 코드가 간결해집니다. 해시의 충돌 처리: 해시 테이블을 사용할 때는 충돌 처리를 위한 방법(예: 체이닝, 개방 주소법)을 이해하고 있어야 합니다.