해시 Hash

1. 해시(Hash)란?

값을 바로 찾기 위한 구조

• 키를 넣으면
• 해시 함수가 주소를 계산해서
• 그 자리에 있는 값을 저장하거나 조회

👉 찾는 데 걸리는 시간이 거의 O(1)

2. 코딩테스트에서 해시를 쓰는 순간

• 중복 여부
• 존재하는지 확인
• 횟수 세기
• 쌍 찾기
• 한 번만 등장한 것

👉 해시로 한 번만 순회

3. 기본패턴 1) 존재 여부 확인

if x in arr: # O(n)

s = set(arr)
if x in s: # O(1)

👉 중복 제거 + 빠른 탐색 = set

4. 기본패턴 2) 개수 세기(빈도수)

# 직접 구현

cnt = {}
for x in arr:
	if x in cnt:
    	cnt[x] += 1
	else:
    	cnt[x] = 1

# 파이썬스러운 방식
from collections import Counter
cnt = Counter(arr)

5. 대표 코테 문제 유형

1) 두 수의 합

• 합이 target이 되는 두 수 찾기

nums = [2,7,11,15]
target = 9

seen = {}
for i, num in enumerate(nums):
    if target - num in seen:
        return [seen[target - num], i]
    seen[num] = i

👉 현재 값 기준으로 과거를 해시에서 찾는다

2) 중복 원소 찾기

seen = set()
for x in nums:
    if x in seen:
        return True
    seen.add(x)
return False

3) 완주하지 못한 선수

from collections import Counter

p = Counter(participant)
c = Counter(completion)

answer = p - c
print(list(answer.keys())[0])

📌 Counter는 뺄셈 가능

6. 시간복잡도

⚠️ 해시는 최악의 경우 O(n) 이지만
👉 코테에서는 평균 O(1) 로 생각하면 됨