[자료구조/알고리즘] 맵과 집합 map, set - 파이썬

 맵 

• key와 value로 이루어진 자료구조이다.
• "": ""의 형태로 JSON 구조와 비슷하다. 
• 값은 중복 가능하나 키는 중복일 수 없다. 키로 검색해서 값을 찾는 구조이기 때문에. 

 

시간복잡도 

 C++의 삽입/삭제 시간복잡도는 log(N)이다. 맵에 값을 한번 넣을때 혹은 삭제할 때 마다 시간복잡도가 log(N)인 것. log(1)보다 엄청 느린 것은 또 아니다. 파이썬은 

 어떤 키 값이 주어졌을 때 해시 함수 y = f(x) 에 키 값을 x에 대입하면 y가 나오는데 y는 해시 테이블에서 이 키에 해당하는 value를 어디에 담을지 주소값에 해당한다. 따라서 키를 넣으면 해시테이블의 위치를 바로 알 수 있다. 이 함수 자체의 시간복잡도가 O(1)이다. 물론 충돌이 나는 경우 등 1이 아닌경우도 있지만, 따라서 파이썬 맵의 삽입 삭제 시간복잡도는 O(1)이다. 

 

집합 

• 중복을 허용하지 않는다.
• add()로 값을 넣을 수 있다. 

s = set() 
s.add(10)
s.add(10)
s.add(10)
s.add(10)
s.add(50)
s.add(70)
s.pop()
print(s)

>>>{50, 70}

pop()

 10이 빠졌다. 왜 10이빠졌지?? 이게 랜덤으로 임의의 값이 하나 빠지는 거여서 어떤 값이 빠질지 알 수 없다고 한다. 알고리즘 문제를 풀 때는 잘 쓸 일이 없겠다.

 

remove()

특정 값을 뺄 수 있다. 

 

clear()

 모든 값을 뺀다. 

 

len()

 집합 요소의 개수를 알 수 있다. 

 

시간복잡도 

맵과 마찬가지로 C++ 은 log(N) , 파이썬에서는 O(1)이다. 

 

맵과 집합 

 맵과 집합은 서로 연관이 있어 필요할 때 섞어가며 사용하곤 한다.