_10_ 자료구조 — 트리/해쉬를 이용한 맵, 셋
맵(Map)과 셋(Set)의 두 구현 방법인 트리/해쉬를 각각 살펴보고 연산을 알아봅시다.
셋(Set)
셋은 말 그대로 집합입니다. 집합이란 자료구조는 우리가 수학에서 의미하는 집합이랑은 조금 다르지만 중요한 특징이 있습니다. 바로 중복을 허용하지 않는다는 점입니다.
c++의 경우 중복을 허용하는 집합인 std::multiset라는 자료구조도 존재하지만 이건 알 필요는 없습니다.
맵(Map)
맵은 셋과 비슷한데, 키(Key)와 값(Value)를 갖습니다. 셋은 키(Key)만 가지는 자료구조라면, 맵은 키도 갖고 어떤 키에 상응하는 값도 가집니다.
맵과 셋의 구현
보통 트리를 이용하든 해쉬를 이용하든 셋과 맵의 구현은 상당한 난이도가 요구됩니다.
여기서 해시란 어떤
- 트리를 이용한다면 BBST(Balanced Binary Search Tree, 균형잡힌 이진 탐색 트리)를 구현하여야 하고 다음과 같은 구현법들이 있습니다.
- AVL Tree
- Red-Black Tree
- Splay Tree
- Treap
보통 AVL 트리나 Red-Black 트리는 컴퓨터 공학 수업을 듣는다면 한 번쯤 구현해볼 수도 있습니다. 절대 쉽지 않았을 겁니다. 하물며 알고리즘 문제를 풀어야되는데 맵이나 셋 한번 쓰겠다고 저걸 다짜고 있는다는 건 말이 안됩니다.
백준에는 Red-Black 트리 태그가 붙은 문제는 한 문제밖에 없고 무려 루비 5 난이도입니다. Splay 트리 같은 경우도 그냥 기본 문제가 다이아몬드로 갈 정도로 직접 구현하기에는 말도 안되는 난이도입니다. 당연히 코딩테스트에서 이런걸 낼리가 없겠죠
2. 해쉬를 이용한다면 적절한 해쉬알고리즘을 사용해야 하고 해쉬 테이블까지 직접 구현을 해야하므로 더 난관에 봉착할 수도 있습니다.
따라서 우리는 언어에서 지원해주는 맵, 셋 자료구조 구현체를 그냥 가져다 사용하기만 하면 됩니다.
각 언어에서의 셋과 맵
일단 맵과 셋의 지원해주는 연산들이나 트리와 해시의 차이점은 제쳐두고 각 언어에서 어떻게 사용할 수 있는지 살펴보겠습니다.
c++부터 보겠습니다.
다음은 자바입니다. 자바는 좀 더 자료구조들 이름이 직관적이라 주석이 없습니다.
다음은 대망의 파이썬입니다. 두구두구
????????
트리를 이용한 맵과 셋은 어디간걸까요?
놀랍게도 파이썬은 이걸 공식적으로 어떻게 지원하지 않는 것으로 보입니다.
물론 이와 관련되어 OrderedDict란 녀석이나 파이썬 3.7 부터는 뭐 딕셔너리에 넣는 순서대로 딕셔너리 내부의 Key가 정렬된다는 말도 있지만 c++이나 자바에서 지원해주는 연산과 조금 차이가 있어보입니다.
우린 망한걸까요? 아닙니다. 사실 코딩테스트 문제를 푸는데 트리를 이용한 맵/셋은 필요없습니다.
보통 그냥 중복을 허용하지 않는 자료구조나 특정 키와 값으로 데이터를 저장하는 자료구조가 필요한 것 뿐이지, 데이터들을 키로 정렬해서 어떤 연산들을 빠르게 수행해야 하는 스위핑같은 알고리즘은 코딩테스트에 보통 출제되지 않습니다. 어렵기도 하고요.
지원해주는 연산들
맵과 셋은 어떤 방식으로 구현되느냐에 따라 연산들의 시간복잡도와 데이터들이 관리되는 방식들이 다릅니다.
앞서 언급되었지만, 트리를 이용해서 맵과 셋이 구현되면 Key의 정렬 기준에 따라 정렬이 되어 자료들이 관리되지만 해시를 이용해서 구현된다면 그냥 지맘대로 데이터들이 들어가있습니다.
연산들을 살펴봅시다!
- Insert
자료구조에 데이터를 넣습니다.
- 트리 — O(logN)
- 해시 — O(1)
2. Erase
자료구조에 특정 데이터를 삭제합니다.
- 트리 — O(logN)
- 해시 — O(1)
3. Find
자료구조에 특정 데이터가 있는지 검색합니다.
- 트리 — O(logN)
- 해시 — O(1)
사실 모두 트리는 O(logN) 이고 해시는 O(1) 입니다.
게다가 트리를 이용해서 구현하면 O(logN)이라도 상수가 붙어 느린 편입니다.
그러면 항상 데이터들이 정렬될 필요가 없다면 해시를 이용한 자료구조를 쓰는 것이 이득일까요?
아닙니다. 트리를 이용하면 최악의 경우에도 O(logN)이 항상 보장되지만, 해시를 쓴다면 해시 알고리즘에서 데이터들이 계속 해시 충돌을 일으킨다면 O(N)까지 느려집니다. (실제로 알고리즘 대회에서는 남의 코드를 테스트 케이스를 만들어 저격할 수 있는데, 해시를 이용한 맵, 셋을 써서 저격당해서 멀쩡한 코드가 시간초과가 난다면 피눈물이 납니다.)
하지만 코딩테스트에서는 두 가지를 아무거나 혼용해서 써도 무방합니다. 데이터들이 정렬될 필요가 없다면 데이터가 저장되는 방식은 상관이 없고, 당장 저 자료구조들의 시간복잡도 차이로 어떤 코드는 맞고 어떤 코드는 틀리고하는 문제는 나오지 않습니다.
셋의 활용
셋이란 자료구조가 흔히 쓰이는 경우는 세 가지입니다.
- 데이터들의 중복을 제거할 때
- 자료구조에 데이터를 넣고, 존재하는지 확인하고, 삭제하는 연산을 O(logN) 혹은 O(1) 에 하고싶을 때
- 만약 트리를 이용한 셋이라서 자동으로 정렬이 될 경우 정렬된 데이터를 관리하고 싶을 때
보통 1, 2번만 많이 쓰이고 코딩 테스트에선 3번 활용법을 이용해야 하는 경우는 드뭅니다.
일단 1번 경우를 보죠.
1. 데이터들의 중복을 제거할 때
파이썬에서 다음과 같은 리스트들이 있습니다.
위와 같이 중복을 제거할 수 있습니다.
2번 경우는 그냥 맵과 셋에서 지원해주는 연산을 사용하면 해결 가능합니다!
