[Algorithm] Python - dictionary 활용과 시간 복잡도 (Big-O)

Python - dictionary 활용과 시간 복잡도 (Big-O)

알고리즘 문제를 풀다 보면 딕셔너리를 사용하는 경우가 있다.

 

딕셔너리는 다른 다른 자료형에 비해 동작시간에서 유리한 측면이 있다.

 

 

Dictionary 자료형

---

딕셔너리는 사전이라는 의미로 key-value 쌍을 가지는 자료형이다.

 

1) 딕셔너리 생성

dictionary0 = dict()
dictionary1 = {}

 

 

2) 딕셔너리 값 추가 및 삭제

dictionary["과일"] = "apple"

del dictionary["과일"]

 

 

3) 딕셔너리 내장함수

dictionary.keys()    # 딕셔너리의 key를 가져온다. 
dictionary.values()  # 딕셔너리의 value를 가져온다.
dictionary.get()     # 해당 딕셔너리 key의 value값을 가져온다. 값이 없으면 none 반환
dictionary.items()   # 딕셔너리의 key와 value을 가져온다.

 

반응형

Dictionary 활용

---

값을 입력받는 로직이다.

 

value값을 list형으로 입력받고 싶을 때 사용하는 로직이다.

graph = dict()
for _ in range(N):
    key, value = map(int, input().rstrip().split())
    if value not in graph:
        graph[key] = list()
    graph[key].append(value)

 

 

모듈을 사용하여 해당 키가 존재하는지 확인하는 과정을 생략할 수 있다.

from collections import defaultdict

dic = defaultdict(list)
dic["과일"].append("apple")
dic["과일"].append("orange")
dic["숫자"].append(0)
dic["숫자"].append(1)

 

728x90

시간 복잡도 (Big-O)

---

Operation	Example	Class
Store	d[k] = v	O(1)
Length	len(d)	O(1)
Delete	del d[k]	O(1)
Get	d.get(k)	O(1)
Pop	d.pop(k)	O(1)
Clear	d.clear()	O(1)
View	d.keys()	O(1)
Iteration	for k in d	O(N)

 

List 자료형에 비해 빠른 동작 속도를 가지고 있는 것을 알 수 있다.

 

Dictionary는 Hash Table을 사용한다.

 

key 값을 알고 있으면 바로 접근할 수 있다.

 

때문에 순차적으로 값을 탐색하는 List 보다 시간복잡도면에서 유리하다.