[9일차] TIL (Hash Table)
부트캠프

[9일차] TIL (Hash Table)

반응형

Hash Table

hash

해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말합니다.

 

해시테이블의 핵심은 해시 함수입니다.

 

성능 좋은 해시 함수들의 특징

  • 해시 함수 값 충돌의 최소화
  • 쉽고 빠른 연산
  • 해시 테이블 전체에 해시 값이 균일하게 분포
  • 사용할 키의 모든 정보를 이용하여 해싱
  • 해시 테이블 사용 효율이 높을 것

생일 문제

import random

TRIALS = 100000     # 10만 번 실험
same_birthdays = 0 # 생일이 같은 실험의 수

# 10만 번 실험 진행
for _ in range(TRIALS):
    birthdays = []
    # 23명이 모였을 때, 생일이 같을 경우 same_birthdays += 1
    for i in range(23):
        birthday = random.randint(1, 365)
        if birthday in birthdays:
            same_birthdays += 1
            break
        birthdays.append(birthday)

# 전체 10만 번 실험 중 생일이 같은 실험의 확률
print(f'{same_birthdays / TRIALS * 100}%')

위 결과 생일이 같으 사람이 있을 확률은 약 50% 입니다.

 

비둘기집 원리

비둘기집 원리란, n개 아이템을 m개 컨테이너에 넣을 때, n > m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리를 말합니다.

 

로드 팩터

로드 팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나누 것입니다.

 

load facotr = n / k

 

개별 체이닝

충돌이 일어난 경우 기존의 값에 다음에 들어온 값을 연결한 연결 리스트 형태의 구조입니다.

원리는 다음과 같습니다.

  1. 키의 해시 값을 계산한다.
  2. 해시 값을 이용해 배열의 인덱스를 구한다.
  3. 같은 인덱스가 있다면 연결 리스트로 연결한다.

 

오픈 어드레싱

충돌이 일어나면 테이블 공간내 탐사(probing)를 통해 빈 공간을 찾아 들어갑니다.

따라서 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없습니다.

구현 방법이 간단하면서도 성능이 좋은 편이지만 데이터들이 고르게 분포하지 않는 경향이 있습니다.

 

언어별 해시 테이블 구현 방식

파이썬의 경우 딕셔너리가 해시테이블로 구성되어 있습니다. 파이썬의 해시테이블은 충돌시 오픈 어드레싱 방식을 이용해 구현되어 있습니다. 

 

위 그림처럼 로드팩터가 증가하면 성능 저하가 일어나기에 루비나 파이썬 같은 모던 언어들은 로드팩터를 낮게 잡아 성능 저하 문제를 해결하고 있습니다.

 

해시맵 디자인

해시맵을 직접 구현해보자

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

from collections import defaultdict

class MyHashTable:
    def __init__(self):
        self.size = 1000
        self.table = defaultdict(ListNode)

    def put(self, key: int, value: int):
        index = key % self.size
        if self.table[index].value is None:
            self.table[index] = ListNode(key, value)
            return

        p = self.table[index]
        while p:
            if p.key == key:
                p.value = value
                return
            if p.next is None:
                break
            p = p.next
        p.next = ListNode(key, value)

    def get(self, key: int):
        index = key % self.size
        # 노드가 존재하지 않는 경우
        if self.table[index].value is None:
            return -1

        # 노드가 존재하는 경우
        p = self.table[index]
        while p:
            if p.key == key:
                return p.value
            p = p.next
        return -1

    def remove(self, key: int):
        index = key % self.size
        if self.table[index].value is None:
            return

        # 인덱스가 첫 번째 노드일 때 삭제 처리
        p = self.table[index]
        if p.key == key:
            self.table[index] = ListNode() if p.next is None else p.next
            return

        # 연결 리스트 노드 삭제
        prev = p
        while p:
            if p.key == key:
                prev.next = p.next
                return
            prev = p
            p = p.next

 

 

1. 보석과 돌

https://leetcode.com/problems/jewels-and-stones/

 

  • 해시테이블을 이용한 풀이
dict = {}

for stone in stones:
    if stone not in dict:
        dict[stone] = 1
    else:
        dict[stone] += 1

count = 0
for jewel in jewels:
    if jewel in dict:
        count += dict[jewel]

return count

 

  • defaultdict를 이용한 풀이

defaultdice 안에 있는 인자는 딕셔너리 value값의 형식을 의미합니다.

from collections import defaultdict

dict = defaultdict(int)

count = 0
for stone in stones:
    dict[stone] += 1

for jewel in jewels:
    count += dict[jewel]

return count

 

  • Counter를 이용한 풀이
from collections import Counter

dict = Counter(stones)
count = 0

# 비교 없이 보석(jewels) 빈도 수 합산
for jewel in jewels:
    count += dict[jewel]

return count

 

  • 파이썬다운 풀이
return sum(stone in jewels for stone in stones)

 

 

2. 중복 문자 없는 가장 긴 부분 문자열

https://leetcode.com/problems/longest-substring-without-repeating-characters/

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0
        for index , char in enumerate(s):
            # 이미 등장했던 문자라면 'start' 위치 갱신
            if char in used and start <= used[char]:
                start = used[char] + 1
            else: # 최대 부분 문자열 길이 갱신
                max_length = max(max_length, index - start + 1)

            # 현재 문자의 위치 삽입
            used[char] = index

        return max_length

 

3. 상위 K 빈도 요소

https://leetcode.com/problems/top-k-frequent-elements/

 

처음 이 문제를 잘못 이해했습니다. 문제에서는 가장 많이 반복 등장하는 원소 종류 중 k개의 원소 종류를 반환하라는 문제였습니다.

import heapq

freqs = collections.Counter(nums)
freqs_heap = []
# Counter({1: 3, 2: 2, 3: 1})

for f in freqs:
    heapq.heappush(freqs_heap, (-freqs[f], f))

topk = list()

for _ in range(k):
    topk.append(heapq.heappop(freqs_heap)[1])

return topk

4. 수 찾기

https://www.acmicpc.net/problem/1920

 

  • 내 풀이(시간 초과)
import sys

input = sys.stdin.readline

n = int(input())
arr1 = list(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

for num in arr2:
    if num in arr1:
        print(1)
    else:
        print(0)

 

 

  • 이진 탐색 풀이
n = int(input())
arr1 = list(map(int, input().split()))
arr1.sort()

m = int(input())
arr2 = list(map(int, input().split()))

def binary_search(target):
    start = 0
    end = len(arr1) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr1[mid] == target:
            return True
        elif target < arr1[mid]:
            # start = 0
            end = mid - 1
        elif target > arr1[mid]:
            start = mid + 1
            # end = len(arr1) - 1
    return False


for num in arr2:
    if binary_search(num):
        print(1)
    else:
        print(0)

 

 

 

5. 비밀번호 찾기

https://www.acmicpc.net/problem/17219

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

data = {}

for _ in range(n):
    site, pw = input().split()
    data[site] = pw

for _ in range(m):
    input_site = input().rstrip()
    print(data[input_site])

그냥 input값을 쓸 경우 시간 초과가 납니다.

기본적으로 readline()은 개행문자(줄 바꿈 문자)를 포함하고 있습니다.
그래서 문자열 마지막에 개행문자가 포함되어 출력되는데 이러한 공백 없이 출력할 수 있게 하는 함수가 있습니다.

반응형

'부트캠프' 카테고리의 다른 글

[11일차] TIL (DFS)  (0) 2022.03.18
[10일차] TIL - Week1 Test  (0) 2022.03.17
[5일차] TIL (문자열 다루기)  (0) 2022.03.13
[3일차] TIL  (0) 2022.03.10
[항해99] 3조 미니 프로젝트  (0) 2022.03.07

    티스토리툴바