Map

Map이란?

자료구조의 일종으로, Key-Value 쌍의 집합으로 데이터를 저장하는 구조다.

이처럼 Key에 접근하면 Value가 나오는 형식이다.

• 각각의 키는 유일해야 하며, 키에 대한 값은 유일하지 않아도 된다.
• JSON과 비슷한 방식

Map의 기본연산

• 삽입
• Value 조회
• 삭제
• 특정 Key 조회
• 모든 키, 값, 키-값 조회
• Map의 크기

시간 복잡도 (Time complexity)

Operation	Average	Worst
Access	O(1)	O(N)
Search	O(1)	O(N)
Insert	O(1)	O(N)
Delete	O(1)	O(N)

Python에서의 Map

파이썬에서는 Map을 표현하기 위해 내장 클래스인 딕셔너리(Dictionart)가 존재한다. hash로 이루어져 있다.

자주 사용하는 딕셔너리는 구현도 단순하다.

m = {"Yoondy": 40, "Sky": 100}  # 생성
m["Jone"] = 20
print(len(m))
print(m.keys())
print(m.values())
print("Jone" in m)
print(m)

이외에도 많은 연산을 사용할 수 있다.

• 추가 map[key] = value
• 특정 키로 값 조회 value = map[key]
• 특정 키로 값 삭제 del map[key]
• 특정 키 존재 확인 key in map
• 모든 키 가져오기 keys = map.keys()
• 모든 값 가져오기 values = map.values()
• 모든 키-값 쌍 가져오기 items = map.items()
• Map 크기 len(map)

---

Set

Set이란?

자료구조의 일종으로, 중복되지 않는 원소들의 집합으로 데이터를 저장하는 구조다.

과거 수학시간에 배운 집합과 같이 원소들의 순서가 없고 유일하다.

Set의 기본연산

• 삽입
• 삭제
• 원소 포함 여부(조회)
• 교집합(intersection)
• 합집합(union)
• 차집합(difference)
• Set의 크기

시간 복잡도 (Time complexity)

Operation	Average	Worst
Access	N/A	N/A
Search	O(1)	O(N)
Insert	O(1)	O(N)
Delete	O(1)	O(N)

원소 조회가 있는데 Access가 N/A인 이유는 Set은 인덱스 개념이 없기 때문에 특정 위치에 접근하는 Access 연산은 지원하지 않는다.

위에서 나타내는 조회는 Access와 비슷한 의미로 쓰일 수 있지만 단순히 원소가 Set에 존재하는지 확인하는 의미이다.

Python에서의 Set

파이썬에서는 Map과 같이 Set을 표현하기 위해 내장 클래스인 Set이 존재한다.

s = set()
s.add(123) # add로 값 넣기 가능
s.add(123) # 중복은 삽입 X
s.add(789)
s.add(456)
print(s)
print(len(s))
print(s.pop()) # 랜덤
s.remove(789)
print(s)
s.clear()
print(s)

위 처럼 사용한다.
이외에도 많은 연산을 지원하지만 원하는 값을 빼는 것에 문제가 있어 알고리즘 공부에 있어서 사용할 일이 적은 자료구조이다.