[코딩테스트 이론] 해시

※ 코딩테스트 합격자 되기 - 파이썬 편 (골든 래빗) 교재 참조

해시

: 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조

• 해시의 특징
  1) 해시는 단방향으로 동작 : 키를 통해 값을 찾을 수 있지만, 값을 통해 키를 찾을 수는 없다
  2) 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다
  3) 값을 인덱스로 활용하려면 적절한 변환과정을 거쳐야 한다
  이 특징은 외부에 정보를 안전하게 전달할 수 있기 때문에 네트워크 보안에서 많이 활용된다.

• 해시 용어
  • 해시테이블 : 키와 대응한 값이 저장되어 있는 공간
  • 버킷 : 해시 테이블의 각 데이터

• 해시 활용 분야
  1) 비밀번호 관리 : 단방향적 특징
  2) 데이터 베이스 인덱싱 : 데이터 효율적으로 검색
  3) 블록체인 : 각 블록은 이전 블록의 해시값을 포함하고 있으며 이를 통해 데이터 무결성 확인 가능

해시함수

• 해시 함수 구현시 고려할 내용
  1) 해시함수가 변환된 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안됨

    - 충돌 : 서로 다른 두 키에 대해 해싱함수를 적용한 결과가 동일한 것

  2) 해시함수가 변환한 값의 충돌은 최대한 적게 발생해야 함

• 자주 사용하는 해시 함수 알아보기
  1) 나눗셈법 : 키를 소수로 나눈 나머지 활용 %(모듈러 연산)2) 곱셈법 : 소수로 나누지 않고 모듈러 연산만 취함3) 문자열 해싱 : 키의 자료형이 문자열일 때

  -   문자-> 숫자 -> 다항식의 값 (너무 클 경우 오버플로우 발생, 모듈러 연산 활용하면 좋음!)
  -   큰 소수를 구하기 쉽지 않기 때문에 곱셈법을 활용함. h(x) = (((x*A) mod 1)* m) A는 황금비
  -   소수로 나누는 이유 : 다른 수를 사용할 때보다 충돌이 적기 때문 h(x) = x mod m

충돌처리

• 충돌처리법
  1) 체이닝 : 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터 연결
• - 단점 1) 해시 테이블 공간 활용성이 떨어짐 충돌이 많아지면 링크드리스트의 길이가 길어지고, 다른 공간은 덜 사용하기 때문 2) 검색 성능이 떨어짐 링크드리스트 자체의 한계

2) 개방 주소법 : 체이닝에서 링크드리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값 삽입  
(메모리 효율적)


    - 선형 탐사 방식 : 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동
        단, 테이블 빈 곳에 해시 충돌이 발생한 값끼리 모이는 영역이 생겨 (클러스터 형성) 해시값이 겹칠확률이 높아질 수 있음
    - 이중 해싱 방식 : 해시 함수 2개를 활영해 첫 번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치 정할지 결정하는 역할을 두 번째 해시 함수가 함

---

문제1 

[메뉴 리뉴얼]

https://school.programmers.co.kr/learn/courses/30/lessons/72411

프로그래머스

**내 풀이

1. 모든 주문에 가능한 조합 만들기

  - 이 때, XY와 YX는 같으므로 정렬을 해서 같은 값으로 만들어 주어야 한다

2. 주문한 수가 2이상이고, course에 해당하는 조합의 길이인 값을 정렬한다.

3. 각 course별로 가장 빈도가 높은 값만 넣는다

  - 단, 빈도가 같다면 빈도가 같은 모든 값을 넣는 다 -> stack으로 구현

 

어려웠던 점

> 문제를 이해하기가 어려웠다... 또한 특수 경우가 몇가지 있어서 이를 고려하기 어려웠다.

   문제를 제대로 이해한 것이 맞는지 test를 몇 개 해본 후 구현에 들어갈 것! + 세부적인 내용도 잊지 않기

from itertools import combinations
def solution(orders, course):
    answer = []
    dic = dict()

    #모든 주문에 가능한 조합
    for order in orders:
        for c in course:
            for comb in combinations(sorted(order), c): #정렬주의!!
                comb_str = ''.join(comb)
                if comb_str in dic:
                    dic[comb_str] += 1
                else:
                    dic[comb_str] = 1

    #가장 높은 빈도수
    for c in course:
        tmp = []
        for k, v in dic.items():
            if len(k) == c and v >= 2:
                tmp.append((k,v))
        tmp = sorted(tmp, key=lambda x:-x[1])
        if tmp: #가장 높은 빈도수의 값이 여러개 일 때에는 모두 넣어주기
            top = tmp[0][1]
            while tmp:
                a = tmp.pop(0)
                if top == a[1]:
                    answer.append(a[0])

    return sorted(answer)