[Algorithm] 해시

김윤섭·2024년 7월 24일

알고리즘 코딩테스트 해시

해시 함수

임의의 크기의 데이터를 고정된 크기의 값으로 변환하는 함수

일관성: 같은 입력에 대해 항상 같은 출력을 생성
효율성: 빠르게 계산할 수 있어야 함
균일 분포: 출력값이 고르게 분포되어야 함
예: MD5, SHA-256 등

해시 테이블(Hash Table)

키(key)를 값(value)에 매핑할 수 있는 구조인 연관 배열을 구현하는 자료구조
해시 함수를 사용하여 키를 해시 값으로 변환하고, 이 값을 인덱스로 사용하여 데이터를 저장하거나 검색함.

버킷(Bucket) 또는 슬롯(Slot)이라 불리는 배열로 구성됌
각 버킷에는 키-값 쌍을 저장
충돌이 일어나지 않는다는 가정하에, 평균적으로 O(1)의 시간 복잡도

충돌

서로 다른 두 개 이상의 입력 데이터가 같은 해시 값을 가지는 현상
해시 함수의 출력 범위가 입력 데이터의 범위보다 작기 때문에 발생

해시충돌 해결법

체이닝

충돌 해결 방법 중 하나로, 같은 해시 값을 가진 항목들을 연결 리스트로 연결하는 방식

각 버킷(해시 테이블의 각 슬롯)에 연결 리스트를 사용
충돌이 발생하면 해당 버킷의 리스트에 새 항목을 추가
장점: 구현이 간단하고, 해시 테이블이 꽉 차도 계속 항목을 추가할 수 있음
단점: 최악의 경우 검색 시간이 O(n)이 될 수 있음 (모든 항목이 같은 버킷에 있는 경우)

개방주소법 (Open Addressing)

충돌 발생 시 다른 빈 버킷을 찾아 데이터를 저장하는 방식

선형 조사법 (Linear Probing): 충돌 발생 시 순차적으로 다음 버킷을 검사
이차 조사법 (Quadratic Probing): 충돌 발생 시 제곱수만큼 떨어진 버킷을 검사
이중 해싱 (Double Hashing): 두 번째 해시 함수를 사용하여 다음 위치를 결정
장점: 추가적인 메모리를 사용하지 않음
단점: 클러스터링(군집화) 현상이 발생할 수 있음, 테이블이 거의 꽉 찼을 때 성능 저하

관련 문제

오픈채팅방

def solution(record):
    # 문제분석
    # 기존 채팅방에 있던 내용도 바뀐 닉네임으로 변경되는걸 알아야함
    #중복 닉네임 허용
    # 유저아이디로 구분함
    # 입력값이 백만이라서 이중 포문은 생각해볼것

    # 알고리즘
    # 해시를 이용하면 키 : 값으로 받기 때문에 좋을듯. 유저 아이디 : 닉네임

    #엣지 케이스
    #없음
    hash = {}
    actions = []

    for r1 in record:
        r = r1.split()
        cmd, uid = r[0], r[1]

        if cmd in ['Enter','Change']:
            nickname = r[2]
            hash[uid] = nickname

        if cmd != 'Change':
            actions.append((cmd,uid))

        answer = []
    for cmd, uid in actions:
        if cmd == 'Enter':
            answer.append(f'{hash[uid]}님이 들어왔습니다.')
        elif cmd == 'Leave':
            answer.append(f'{hash[uid]}님이 나갔습니다.')

    return answer

메뉴 리뉴얼

from itertools import combinations
from collections import Counter

def solution(orders, course):
    #문제분석
    #코스요리 == 2가지 이상 단품메뉴
    #최소 2명 이상의 손님에게 주문된 단품요리
    #코스요리 개수가 나오면 메뉴구성이 문자열로 리스트에 담김
    #2*10*10*10=2000 시간복잡도는 고려 x
    #오름차순정렬
    #알고리즘

    #엣지케이스
    #단품요리가 주문된 횟수가 같을경우->모두 배열에 담기
    answer = []

    for course_length in course:
        tmp = []

        #횟수를 하나씩 세는 카운터가 있으면 좋을듯
        for order in orders:
            sorted_order = sorted(order)

            if len(sorted_order) >= course_length:

                combs = list(combinations(sorted_order,course_length))

                for comb in combs:
                    tmp.append(''.join(comb))
                    
        comb_counts = Counter(tmp)

        if comb_counts:
            max_count = max(comb_counts.values())

            if max_count > 1:
                for combo, count in comb_counts.items():
                    if count == max_count:
                        answer.append(combo)



    return sorted(answer)