문제풀이 - STL 연관 컨테이너의 비교

Jinho Lee·2024년 1월 9일

개요

백준 25192번 문제를 풀다가, unordered_map을 사용했는데 시간초과로 틀렸다. 이를 해결하기 위해 map으로 자료구조를 바꾸어 시도해보니 바로 성공하였다.
여기서 내가 연관 컨테이너 사이의 차이를 정확히 모른다는 것을 알고, 조사해보고자 이 곳에 정리한다.

연관 컨테이너(Associate Container)란, key와 value를 관계지어 묶어서 저장하는 컨테이너이다.
key를 통해 요소에 빠른 접근은 가능하지만 자체적인 기준으로 요소를 정렬하기 때문에 삽입되는 요소의 위치를 지정하거나 알 수 없다.
- 배열 같은 순차 컨테이너에서 사용되는 int 값 Index나 반복자(Iterator)를 사용한 접근이 불가하다는 것이다.

key와 value를 쌍으로 가지는 연관 컨테이너이다.
일반적으로 Red-Black Tree로 구현된다고 한다.
요소가 key 값에 따라 오름차순으로 정렬된다.
key와 value를 대응하여 key를 인덱스처럼 사용해 value에 접근할 수 있다.
최종 데이터(leaf node)를 탐색할 때, 최악의 경우가 최선의 경우보다 2배 이상 시간이 걸리지 않도록 설계되어 있다.
- 이러한 특징으로 인해 데이터를 묶어 빠르게 검색할 때 유용하다.
key의 중복을 허용하지 않는다.

#include <map>

map<key type, value type> 맵 이름;
multimap<key type, value type> 멀티맵 이름;

key만 갖는 컨테이너이다. key가 곧 저장하는 값이다.
map과 같이 Red-Black Tree로 구현된다고 한다.
key 값에 따라 오름차순으로 정렬된 위치에 요소를 삽입하여 검색 속도가 매우 빠르다.
- 검색으로 데이터의 존재 유무를 파악하기에 유용하다.
- 다른 정렬 기준을 사용하고 싶다면 템플릿 매개변수에서 지정할 수 있다.
key의 중복을 허용하지 않는다.

#include <set>

set<타입> 셋이름(생성자 인수);
multiset<타입> 멀티셋이름(생성자 인수);

기본적인 기능은 위의 map, set과 같지만, 구현되는 구조가 다르다.
- 위의 map과 set은 트리로 구현되어 요소를 정렬하지만,
  unordered_map과 unordered_set은 key를 해시(Hash) 함수로 무작위의 인덱스로 변환해 요소를 해시 테이블에 균등 분배해 저장한다.
- 많은 양의 데이터를 저장할 경우, 이론상 검색 속도가 $O(1)$ 로 매우 빠른 검색이 가능하다.
해시 테이블의 충돌은 체이닝(Chaining)으로 해결한다.
다만 저장할 데이터가 적은 경우 단점이 많다.
- 할당된 메모리를 전부 사용하지 못해 메모리 낭비가 발생한다.
- 지역참조성이 부족해 캐시 미스가 일어나는 등, 검색 시에도 오버헤드가 발생한다.
  - 오버헤드 : 어떤 처리를 하기 위해 간접적인 처리 시간 및 메모리 등이 추가적으로 사용되는 현상
따라서 unordered_map과 unordered_set의 사용은 다음과 같은 경우에 바람직하다.
1. 많은 데이터를 저장해야 하는 반면 검색 속도는 빨라야 하는 경우
2. 빈번하게 데이터의 삽입, 삭제가 일어나지 않는 경우
key 중복을 허용하지 않는다.

조사한 바에 따르면, 결과적으로 map과 unordered_map을 비교했을 때
저장하는 데이터 양이 적을 때는 map이 유리하고 많으면 unordered_map이 유리하다는 것을 알았다.
- 이는 map은 데이터 양이 많으면 인덱스가 널뛰기 때문에 캐시 미스가 발생하기 쉽고,
  반대로 unordered_map은 데이터 양이 적으면 캐시 미스가 발생하기 쉽다는 지역참조성에 따른 결론이다.
- 추가로 unordered_map은 해시 함수의 성능이 자료 구조 자체의 성능에 크게 관여한다고 한다.
  - 해시 테이블에서의 잦은 충돌은 반복적인 체이닝 기법의 사용을 야기하고, 이는 순차적인 탐색을 요구하기에 이상적인 $O(1)$ 을 보장할 수 없게 된다.
또한 문자열(string) 키를 사용하는 경우에는 map이 탐색 성능에 있어서 우위를 점한다고 한다.
- 이는 map이 Red-Black Tree로 구현되어 있어 문자열 비교를 더 적게 필요로 하기 때문이다.
  즉,

문자열의 길이가 길고 데이터의 양이 많지 않은 경우는 map이 unordered_map보다 탐색에 유리하다.

25192번 문제의 경우에는 저장하는 최대 데이터의 수가 100,000개, $10^5$ 에 불과하고 key로 사용되는 데이터 또한 최대 20의 길이를 가지는 문자열이었기에, unordered_map에 비해 map을 사용하는 것이 훨씬 적절한 구현으로 보인다.