내일배움캠프 32일차 - 자료구조 & 알고리즘 5주차 : Map, Set
Map - 이름표로 데이터에 접근
map은 key-value 쌍을 저장하는 자료구조
key는 이름표(찾는 기준), value는 실제 데이터.
시간복잡도: 검색 / 삽입 /삭제 모두 O(log n)
- 내부적으로 이진 탐색 트리(BST) 라는 구조를 사용하기 때문.
- ex) 1만개 데이터 → 약 14번이면 찾는다.
※ 이진 탐색 트리(BST)란?
데이터를 크기 순서대로 정리해서 빠르게 찾는 구조.
"왼쪽은 작은 값, 오른쪽은 큰 값" - 이 규칙 하나로 검색 범위를 절반씩 줄여나간다.
map의 핵심 규칙
규칙1: key는 중복 불가. 같은 키로 다시 넣으면 기존 값이 사라진다.
규칙2: 순회하면 key 기준 정렬. 넣은 순서가 아니라 key의 오름차순으로 나온다.
map 주요 연산 정리
| 연산 | 설명 | 시간 복잡도 |
| m["key"] = value | 삽입 또는 수정 | O(log n) |
| m.insert({"key",value}) | 삽입 (수정x) | O(log n) |
| m["key"] | 값 읽기 ( [ ] 자동생성 주의! ) | O(log n) |
| m.count("key") | 존재 여부 반환 (0 또는 1) | O(log n) |
| m.erase("key") | 삭제 | O(log n) |
| for(auto& p : m) | 순회 (p.first / p.second) | O(n) |
※ map.insert() 사용 시에 값이 이미 있으면 덮어 씌우지 않는다
[ ] 자동생성의 함정
없는 키를 []로 읽기만 해도 기본값(int는 0)으로 자동 생성된다.
의도치 않게 map 크기가 늘어나는 버그의 원인이 된다.
: 검색 목적이라면 []를 직접 쓰지 않고 count()로 먼저 확인하고 있을 때만 []로 접근하기
Map의 사용 예시 - 카운팅 패턴 : 자동생성이 오히려 편리해지는 방법
동작 원리:
1. n이 처음 등장: countMap[n]은 없는 키 → 0으로 자동 생성 → ++ → 1
2. n이 이미 있음: countMap[n]은 기존 값 → ++ → 값 증가
"함정"이라고 했던 자동생성이, 카운팅에서는 오히려 편리한 기능이 된다.
map.find() vs map.count()
map.find()는 key의 위치를 iterator로 반환하고(없으면 end()값 반환),
map.count()는 key의 유무만을 반환한다는 특징이 있다.
Set - 값만 있는 맵
"이 값이 존재하는가?" 만 관심이 있을 때 쓴다.
(map = 사전, set = 출석부 에 비유된다)
중복 제거 + 자동 정렬
insert순서: 30,10,20,10,30 → {10,20,30}
그 외에도 insert(), count(), erase(), 순회 모두 map과 거의 동일한 인터페이스를 가진다.
unordered_map - 정렬을 포기하면 더 빨라진다
 |
| map | unordered_map | |
| 내부 구조 | 이진 탐색 트리 | 해시 테이블 |
| 검색 속도 | O(log n) | O(1) 평균 |
| 순회 순서 | key 정렬 순 | 보장 없음 |
| 추천 용도 | 정렬 | 빠른 검색 |
정렬이 필요하면 map / 빠른 검색이 필요하면 unordered_map을 사용한다.
둘의 사용법은 insert(), count(), erase(), [] 모두 동일하다.
해시(Hash) - O(1)검색의 비밀
v[3]하면 메모리에서 바로 3번 칸을 찾아간다. 숫자 인덱스로 바로 접근하므로 O(1)이다.
그렇다면 "김철수"같은 문자열도 숫자로 바꿀 수 있다면, 배열처럼 바로 접근할 수 있지 않을까?
→ 이것이 해시 함수(Hash function)의 아이디어. 어떤 데이터든 고정 크기의 숫자(해시값) 출력
해시 테이블의 원리
 |
| 해시검색: "김철수" → hash() → 2 → 배열[2] → 바로 찾음! O(1) |
해시충돌 - 같은 칸에 두명이?
해시함수가 "김철수" → 2, "정하나" → 2 를 반환한다면? 해시 충돌(Hash Collision)이 발생한다.
 |
| 해시충돌(Hash Collision) 예시 |
해시 충돌 해결 방법: 같은 해시끼리는 리스트로 연결한다.
→ 같은 해시 내에서 리스트 검색이 발생함
 |
| 이것이 unordered_map이 "평균 O(1)" 이라고 하는 이유이다. |
map, set의 실제 사용사례
게임 개발
map은 게임에서 데이터 관리의 핵심이다.
 |
| 게임에서의 map사용 예시 |
웹/서버
웹에서는 key-value 구조는 사실상 모든 곳에 있다.
{"name": "철수", "score": 78}
이것이 바로 JSON - 웹의 표준 데이터 형식이자 key-value 구조이다.
서버 캐시(Redis)도 거대한 해시 테이블이고,
URL 쿼리(?key=value), HTTP 헤더, 쿠키도 전부 key-value를 사용한다.
CS 전반
해시 테이블은 컴퓨터 과학에서 가장 중요한 자료구조 중 하나다.
- 데이터베이스의 인덱스
- 파일 무결성 검증(체크섬)
- 암호학 (암호화 해시)
- 블록체인
"데이터를 숫자로 바꾸는" 해시의 아이디어는 CS 전반에 걸쳐있다.
(Python의 dict, JavaScript의 Object/Map도 같은 원리를 사용한다)
오늘의 핵심
- map은 key-value 쌍을 저장: vector는 숫자 인덱스, map은 의미있는 키로 접근
- [] 자동 생성 주의: 없는 키를 []로 읽기만 해도 기본값으로 자동 생성, 검색은 count() 먼저
- 카운팅 패턴 countMap[n]++: 없으면 0 자동생성 → +1, 있으면 기존 값 +1
자동 생성이 오히려 편리해지는 역전의 패턴.
- set은 "값만 있는 map": 중복 불가 + 자동 정렬을 가진 STL. "있는가?"만 확인할 때 사용.
- 시간복잡도 차이: map은 O(log n), unordered_map은 평균 O(1) 의 연산속도을 가진다.
댓글
댓글 쓰기