[CS-005][기초] 해시맵과 집합으로 빠르게 찾고 중복 없애기 > IT 기술 공유

• 목록

[이번 수업]
목록에서 매번 처음부터 찾는 대신 해시맵과 집합으로 검색용 색인을 만듭니다. Python의 딕셔너리(dict)로 사용자 ID에 맞는 이름을 찾고, 집합(set)으로 중복 요청을 제거하며 등록·미등록 ID를 나눕니다.

[선수지식]
CS-001~004의 자료구조·복잡도 기초와 Python의 리스트·반복문을 알면 됩니다.

[학습목표]
1. 해시맵의 키와 값 구조를 설명한다.
2. 딕셔너리 조회와 집합 멤버십 검사를 사용한다.
3. 합집합·교집합·차집합 중 필요한 연산을 고른다.
4. 평균 시간과 최악 시간, 메모리 비용을 함께 고려한다.

[핵심개념]
해시맵(hash map)은 키를 해시 함수로 숫자처럼 바꾸어 저장 위치 후보를 찾는 구조입니다. Python에서는 dict가 대표적인 해시맵입니다. `by_id['u002']`처럼 키로 값을 찾고, 없는 키를 안전하게 처리하려면 `by_id.get('u004', '미등록')`을 사용합니다. 대괄호 조회는 키가 없으면 KeyError를 냅니다.

집합은 중복 없는 해시 가능한 원소 모음입니다. ‘등록됐는가?’를 자주 묻거나 중복을 없앨 때 적합합니다. `a & b`는 두 집합에 모두 있는 교집합, `a - b`는 a에만 있는 차집합입니다. 집합은 순서를 보장하는 목록이 아니므로 사람이 읽을 출력은 `sorted()`로 정렬합니다. 빈 집합은 `{}`가 아니라 `set()`으로 만듭니다. `{}`는 빈 딕셔너리입니다.

해시는 버킷 후보를 찾고, 충돌하면 추가 비교합니다. CPython의 dict·set 멤버십은 평균 O(1), 최악 O(n)이며 리스트의 `x in list`는 O(n)입니다. 색인 생성에는 O(n) 시간과 추가 메모리가 들어 작은 데이터의 일회성 검색은 리스트도 충분합니다.

딕셔너리 키와 집합 원소는 해시 가능해야 합니다. 문자열·숫자·불변 튜플은 가능하지만, 내용이 바뀌는 list·dict·set은 사용할 수 없습니다. 저장 중 키가 바뀌면 원래 버킷을 다시 찾을 수 없기 때문입니다. 변경 불가능한 집합이 필요하면 frozenset을 사용합니다.

[따라하기]
아래 내용을 hash_demo.py로 저장하세요.

```python
records = [
    ("u001", "민수"),
    ("u002", "지수"),
    ("u003", "하늘"),
]

by_id = {user_id: name for user_id, name in records}
registered = set(by_id)
requests = ["u002", "u004", "u002", "u003"]

for user_id in requests:
    print(user_id, by_id.get(user_id, "미등록"))

requested = set(requests)
print("unique:", sorted(requested))
print("known:", sorted(requested & registered))
print("unknown:", sorted(requested - registered))
```

Windows PowerShell에서는 `py hash_demo.py`, macOS·Linux에서는 `python3 hash_demo.py`를 실행합니다. 예상 결과는 다음과 같습니다.

```text
u002 지수
u004 미등록
u002 지수
u003 하늘
unique: ['u002', 'u003', 'u004']
known: ['u002', 'u003']
unknown: ['u004']
```

`set(by_id)`는 딕셔너리의 키들로 집합을 만듭니다. 원래 requests에는 u002가 두 번 있지만 requested에는 한 번만 남습니다. 차집합 `requested - registered`는 등록 집합에 없는 u004만 돌려줍니다.

[흔한 실수]
`if key in by_id.values()`는 키 검색이 아니라 값 전체를 검사합니다. ID 존재 여부는 `key in by_id`로 확인하세요. 집합 출력 순서에 의존하거나 `set[0]`처럼 인덱싱하면 안 됩니다. 같은 키에 새 값을 넣으면 이전 값이 교체됩니다. 집합으로 바꾸면 순서와 중복 횟수를 잃습니다.

[보안 주의]
Python의 `hash()`는 자료구조용이며 비밀번호 저장·파일 무결성·전자서명에 쓰는 암호학적 해시가 아닙니다. 문자열 해시값은 실행마다 달라질 수 있으므로 파일이나 DB에 영구 ID로 저장하지 마세요. 외부 입력으로 거대한 dict·set을 만들면 메모리와 CPU를 소모할 수 있어 항목 수와 키 길이를 제한해야 합니다. 실제 개인정보 대신 예제용 ID를 사용하고, 권한 확인은 단순한 집합 멤버십만으로 끝내지 말고 신뢰할 수 있는 서버 정책에서 수행하세요.

[직접 해볼 과제]
1. records에 u004를 추가해 known과 unknown 결과가 어떻게 바뀌는지 확인하세요.
2. 두 팀의 ID 집합을 만들어 합집합 `|`, 교집합 `&`, 차집합 `-`을 출력하세요.
3. 중복 요청 횟수도 필요할 때 set 대신 어떤 구조를 쓸지 설계하세요.

[확인문제]
1. dict와 set은 각각 무엇을 저장할 때 알맞나요?
2. 집합을 출력하기 전에 sorted를 사용한 이유는 무엇인가요?
3. 변경 가능한 list를 딕셔너리 키로 사용할 수 없는 이유는 무엇인가요?

[다음 학습]
CS-006에서는 재귀와 분할 정복으로 큰 문제를 작은 문제로 나누는 방법을 배웁니다.

[공식 참고 자료]
Python 자료구조 튜토리얼: https://docs.python.org/3/tutorial/datastructures.html
Python dict·set 형식: https://docs.python.org/3/library/stdtypes.html
Python 해시 데이터 모델: https://docs.python.org/3/reference/datamodel.html#object.__hash__
CPython 시간 복잡도 참고: https://wiki.python.org/moin/TimeComplexity