해시, 그리디

데이터 엔지니어링 데브코스 Day 4

- 자료구조 및 알고리즘 풀기 4

 

🚀 해시 (Hash)

해시

• 해시 함수(hash function)로도 불리며, 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수
  • 아무리 큰 숫자를 넣어도 고정된 크기의 숫자가 나옴
  • 단방향 함수이기에 출력된 값을 통해 입력값을 알 수 없음
• 키(key)를 해시 함수로 돌려 나온 해시 값에 따라 해시 테이블(hash table)에 저장
• 입력된 값이 조금만 변해도 결과가 크게 달라지는 특성 (눈사태 효과, Avalanche Effect)
• 서로 다른 입력값에도 동일한 값이 출력되는 경우가 있음 (해시 충돌, Hash Collision)
  • 입력에 비해 출력의 범위가 작기 때문
  • 이 경우, Separate Chaining 또는 Open Addressing 등의 방법을 사용하여 방지

https://ssdragon.tistory.com/132 에서 조금 더 자세히 알 수 있습니다.

 

✏️ 파이썬의 대표적인 해시 자료구조인 딕셔너리(Dictionary)

• 딕셔너리는 해시 테이블을 기반으로 구현된 자료구조
• 딕셔너리는 키(key)와 값(value)의 쌍으로 이루어져 있으며, 각 키는 고유함
• 딕셔너리는 해시 함수를 사용하여 각 키를 해시 값으로 변환하고, 해시 값으로 딕셔너리 내부의 해시 테이블에서 해당 키와 연관된 위치를 결정하는 데 사용함
• 빠른 검색 및 삽입 보장

 

✏️ 해시의 대표 문제 : 완주하지 못한 선수

def solution(participant, completion):
    d = {}
    for x in participant:
        d[x] = d.get(x, 0) + 1
    for x in completion:
        d[x] -= 1
    dnf = [k for k, v in d.items() if v > 0]
    return dnf[0]

 

 

 

 

🚀 그리디 (Greedy)

• 탐욕 알고리즘 or 욕심쟁이 알고리즘으로 불림
• 말 그대로 욕심쟁이라서 선택의 순간마다 최적의 선택을 하여 전체적으로 최적이길 바라는 방법
• 선택의 순간마다 최적의 선택을 했다하여 그것이 최적의 해답이라는 보장 X

 

🤔 탐욕 알고리즘을 적용하기 위한 2가지 조건

1. 탐욕스러운 선택 조건 (Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음
2. 최적 부분 구조 조건 (Optimal Substructure) : 문제에 대한 최적해가 부분 문제에 대해서도 최적해라는 것

https://ssdragon.tistory.com/114 에서 조금 더 자세히 알 수 있습니다.

 

✏️ 그리디의 대표적인 문제 : 체육복

def solution(n, lost, reserve):
    s = set(lost) & set(reserve)
    l = set(lost) - s # 체육복 빌려야하는 집합
    r = set(reserve) - s # 체육복 빌려줄 수 있는 집합
    
    for x in sorted(r):
        if x - 1 in l:
            l.remove(x-1)
        elif x + 1 in l:
            l.remove(x+1)
    
    return n - len(l)