키를 주소로 바꿔 빠르게 찾는 딕셔너리와 집합의 원리
목록에서 매번 처음부터 찾는 비용을 없애고 싶을 때 씁니다. 키로 값을 찾거나, 이미 본 값인지 확인하거나, 빈도를 셀 때 코드와 시간 복잡도를 동시에 줄여 줍니다.
코드를 생각하지 말고, 아래 상황이 어떤 순서로 움직이는지만 따라가 보세요.
신발 모양을 기억해 모든 칸을 열어보지 않고, 받은 열쇠 번호로 내 신발장을 바로 엽니다.
전화번호를 찾을 때 모든 사람을 확인하지 않고 이름을 검색해 번호를 바로 꺼냅니다.
코딩 테스트의 장난감 예제를 넘어, 실제 시스템에서 같은 원리가 어디에 숨어 있는지 연결해 보세요.
URL이나 사용자 ID를 키로 삼아 계산·조회 결과를 즉시 재사용합니다.
로그의 상태 코드, 상품 카테고리, 단어별 등장 횟수를 셉니다.
처리한 이벤트 ID를 set에 기록해 같은 요청의 재처리를 막습니다.
세션 토큰을 키로 사용자 정보와 만료 시각을 바로 찾습니다.
상품 코드를 키로 현재 수량과 보관 위치를 즉시 조회합니다.
해시 함수가 키를 정수로 바꾸고 그 값으로 저장 위치를 결정합니다. 서로 다른 키가 같은 위치를 가리키는 충돌은 내부 규칙으로 해결합니다. 좋은 분산과 충분한 공간이 유지되면 조회·삽입·삭제가 평균 O(1)입니다.
| 연산 | Python 표현 | 시간 |
|---|---|---|
| 조회 | mapping[key] | 평균 O(1) |
| 삽입/수정 | mapping[key] = value | 평균 O(1) |
| 포함 확인 | key in seen | 평균 O(1) |
| 전체 순회 | for key in mapping | O(n) |
counts = {}counts = {'a': 1}counts = {'a': 1, 'b': 1}counts = {'a': 2, 'b': 1}설명을 닫고 먼저 풀어본 뒤, 막히는 지점에서 어떤 연산이 필요한지 다시 떠올려 보세요.
Easy 연습 1 / 7
Python으로 풀기Easy 연습 2 / 7
Python으로 풀기Easy 연습 3 / 7
Python으로 풀기Easy 연습 4 / 7
Python으로 풀기Easy 연습 5 / 7
Python으로 풀기Easy 연습 6 / 7
Python으로 풀기Easy 연습 7 / 7
Python으로 풀기Medium 연습 1 / 3
Python으로 풀기Medium 연습 2 / 3
Python으로 풀기Medium 연습 3 / 3
Python으로 풀기