📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

🗓️TIL (this week I learned)
월 개념정리
화 해시 함수, 충돌, 버킷, 체이닝
수 😴
목 깃허브 문제 풀기 2
금 난이도⭐ 풀기, 문제 세팅
토 🤒

🔷 8. 해시⭐⭐⭐

8-1 개념

1. 해시 함수를 사용

• 변환한 값을 인덱스 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료 구조
• 키와 데이터는 일대일 대응
• 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수

2. 해시의 특징

• 단방향: 키를 통해 값을 찾을 수 있다.(반대x). 네트워크 보안에서 많이 활용됨.
• $O(1)$: 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾을 수 있어 탐색 효율이 좋다.
• hash table: 키와 대응한 값이 저장되어 있는 공간
• bucket: 해시 테이블의 각 데이터

3. 활용

• 비밀번호 관리
• 데이터베이스 인덱싱
• 블록체인: 각 블록은 이전 블록의 해시값을 포함. 이를 통해 데이터 무결성을 확인
  - data integrity: 데이터의 정확성, 일관성, 유효성이 유지되는 것. 정보에 결점이 없도록 유지하는 성질.
  

➕ 참조:
https://en.wikipedia.org/wiki/Hash_table
https://en.wikipedia.org/wiki/Hash_function
https://ko.wikipedia.org/wiki/생일_문제
https://en.wikipedia.org/wiki/Birthday_problem
https://en.wikipedia.org/wiki/Four_color_theorem

문제

1. 완주하지 못한 선수

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

def solution(participant, completion):
    table = {}
    for i in participant:
        if i not in table:
            table[i] = 1
        else:
            table[i] += 1
            
    for j in completion:
        table[j] -= 1
    
    # 꺼내는 게 문제..
    for key in table.keys():
        if table[key] > 0:
            return key

참고) https://velog.io/@erdosnumber0/leetcode-771.Jewels-and-Stoneseasy

# counter 활용하기
import collections


def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

개인적으로 왜 [0]이 있는걸까 의아했는데,
[0]이 없다면, ['미완주자'] 가 되었을 것이다.
list가 없었다면 dict_keys['미완주자']였을 것이고.

⌛시간 복잡도: 참가자 이름(N개)을 해시 테이블에 추가 $O(N)$,
완주 참가자 이름(N-1개:문제 안에 1명을 제외하고 모두 완주한다는 얘기가 있으므로) 해시테이블에서 제외하는 $O(N-1)$

고로, $O(N+N-1)$ → $O(N)$이지 않을까??? ❓❓❓❓

• 아, 책 오타 $O(N+N-1)$의 괄호 표기가 오타인 듯 하다.
  괄호 없이 $O(2*N-1)$

2. 할인행사

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

3. 오픈채팅방

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

4. 베스트앨범

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

5. 메뉴리뉴얼

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

추천 문제1

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

추천 문제2

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