[자료구조] 딕셔너리(Dictionary), 맵(Map), 집합(Set)

딕셔너리, 맵

 

한줄요약 : JSON이라고 생각하면 된다

Key, Value 형태로 제공되는 자료구조이다

C++에서는 맵, 파이썬에서는 딕셔너리라는 이름으로 제공된다

삽입/삭제시 Python의 딕셔너리에서는 O(1), C++의 맵에서는 O(logN)의 시간 복잡도를 가진다

이때 Key는 Unique하여 중복을 허용하지 않는다

두 언어의 시간복잡도가 다른 이유는, 내부적으로 다르게 구현되어 있기 때문이다

파이썬은 Hash 구조로 구현되어있어, 상수의 시간복잡도가 나온다

hash

본 것과 같이 Hash는 하나의 Unique한 key 하나당 각각의 hash가 연결되어 있다

그래서 시간복잡도가 O(1)이 나온다...!

Red-black tree

레드블랙 트리.. 알고리즘 시간에 꽤나 골칫거리였던 친구... 여기서 또 보는구나...

C++의 Map은 내부적으로 이 Red-black Tree로 구현되어 있다

교수님이 수업시간에 설명해준 링크로 자세한 설명을 대체한다

http://www.btechsmartclass.com/data_structures/red-black-trees.html

Data Structures Tutorials - Red - Black Tree with an example

 

코드는 다음과 같다

// C++
map<string, int> m;
m["iamjooon2"] = 40;
m["jminjong"] = 100;
m["bvnm0121"] = 50;
printf("size: %d\n", m.size());
for(auto p: m){
	printf("%d, %d\n", p.first, p.second);
}
// 내부적으로 red-black tree로 구현되어있음

# Python
d = {}
d["iamjooon2"] = 40
d["jminjong"] = 100
d["hjhjdev"] = 50
print("size: ", len(d))
for k in d:
	print(k, d[k])
    
# 내부적으로 Hash로 구현되어 있음

파이썬의 딕셔너리는 삽입/삭제시 시간복잡도가 O(1)이 된다

 

집합

중고등학교 수업시간에 배웠던 바로 그 집합이다

가장 큰 특징으로, 중복을 허용하지 않는다

삽입/삭제시 Python의 Dictionary에서는 O(1), C++의 Dictionary에서는 O(logN)의 시간 복잡도를 가진다

// C++
set<int> s;
s.insert(456);
s.insert(12);
s.insert(456);
s.insert(7890);
s.insert(7890);
s.insert(456);
printf("size: %d", s.size()); // size: 3
for (auto i : s){
	printf("%d\n", i);
}

# Python
s = set()
s.add(456)
s.add(12)
s.add(456)
s.add(7890)
s.add(7890)
s.add(456)
print("size: ", len(s)) # size: 3
print(s) # {456, 12, 7890}
s.remove(12)
print(s) # {456, 7890}

 

집합은 중복을 허용하지 않으며, 삽입/삭제시 시간복잡도가 O(1)이 걸린다

 

위 두 특징을 잘 활용하여 알고리즘 문제 해결시 사용해보자...!