자료구조 #1 (딕셔너리)

※포스트의 모든 내용은 박상길 저자의 "파이썬 알고리즘 인터뷰" 에서 참고한 내용이다.

• 딕셔너리

딕셔너리는 파이썬에서 제공하는 키/값의 형태 데이터 모음의 자료구조이다. 파이썬 3.7+에서는 입력 순서가 유지되지마 파이썬 3.6 이전에서는 유지되지 않는다. 또 내부는 해시 테이블로 구현되어 있고, 다른 언어에서 해시 테이블로 구현된 자료형은 C++에서 std::unordered_map, 자바에서는 HashMap이 있다. 리스트는 인덱스를 숫자로만 지정할 수 있었지만 딕셔너리에서는 다양한 타입의 키를 이용하여 그에 해당하는 값을 찾을 수 있다. "해싱"이라는 과정으로 통해 숫자 뿐 아니라 문자, 집합, 불변 객체를 모두 키로 사용할 수 있다. 해시 테이블의 장점은 입력과 조회 모두 O(1)에 가능하다는 점이 있다. 딕셔너리의 주요 연산 시간 복잡도와 설명을 보자.

• 주요 연산

• d[key]
시간복잡도: O(1)
키(key)를 조회하여 값은 반환한다.

• d[key] = value
시간복잡도: O(1)
키에 해당하는 값(value)을 삽입한다.

• key in d
시간복잡도: O(1)
딕셔너리(d)에 키(key)가 존재하는지 확인한다.

• len(d)
시간복잡도: O(1)
딕셔너리(d)의 요소 개수를 반환한다.

주요 연산이 모두 O(1)인 이러한 자료형은 코딩 테스트 시에도 매우 유용하게 활용된다. 앞에서 말했 듯이 원래 딕셔너리는 입력 순서를 유지하지 않았다. 파이선 3.7부터 내부적으로 입력 순서 유지 기능을 제공했다. 하지만 코딩 테스트 시, 인터프리터 의 버전을 확인하기도 어렵고 하여 딕셔너리가 당연히 입력 순서를 유지할 것이라고 가정하고 문제를 푸는 것은 위험하다. 따라서 이럴 때 쓰이는 방법이 있는데 collection 모듈에서 제공하는 OrderedDict()를 사용하는 것이다. 이외에도 이 모듈에는 키 오류를 방지하기 위해 디폴트 값을 생성하는 defaultdict()와 요소의 값을 키로 하고 그의 개수를 값으로 하는 Counter() 등 다양한 기능을 제공한다.

• 활용

- 선언

먼저 딕셔너리는 다음과 같이 선언할 수 있다.

>>> d1 = dict() # dict()를 이용하여 생성
>>> d2 = {} # 중괄호를 이용하여 생성
>>> d3 = {'key1':'value1', 'key2':'value2', 'key3':'value3'} # 리스트 생성과 동시에 초기화

- 추가

선언된 딕셔너리에 키/값을 삽입하기 위해서는 다음과 같이 할 수 있다.

>>> d = {'key1':'value1', 'key2':'value2', 'key3':'value3'}
>>> d
{'key1':'value1', 'key2':'value2', 'key3':'value3'}
>>> d['key4'] = 'value4'
>>> d
{'key1':'value1', 'key2':'value2', 'key3':'value3', 'key4':'value4'}

위와 같이 딕셔너리이름[키] = 값의 형태로 키/값을 삽입할 수 있다.

- 접근 및 조회

조회는 딕셔너리의 키를 지정하면 그에 해당하는 값을 조회할 수 있다.

>>> d = {'key1':'value1', 'key2':'value2', 'key3':'value3'}
>>> d
{'key1':'value1', 'key2':'value2', 'key3':'value3'}
>>> d['key4']
'value4'

하지만 존재하지 않은 키를 지정하여 조회하려고 한다면 KeyError 오류가 발생한다. 이는 다음과 같이 try를 이용하여 예외처리할 수 있다.

try:
	print("d[key8]")
except KeyError:
	print("The key does not exist.")

다음과 같이 for 반복문을 통해서 각각 조회 및 추출도 가능하다.

>>> for k,v in d.items():
...		print(k,v)
...
key1 value1
key2 value2
key3 value3
key4 value4

또 다음과 같이 키가 그 딕셔너리에 존재하는 지 알 수 있다.

>>> 'key8' in d
False

- 삭제

딕셔너리 내의 특정 요소를 삭제하기 위해서는 키로 접근하여 삭제할 수 있다.

>>> d = {'key1':'value1', 'key2':'value2', 'key3':'value3'}
>>> del d['key1']
>>> d
{'key2':'value2', 'key3':'value3'}

이 또한 다음과 같이 try를 이용하여 예외처리 할 수 있다.

try:
	print("d[key8]")
except KeyError:
	d['key8'] = 'value8'

• 딕셔녀리 모듈

- defaultdict 객체

defaultdict 객체는 존재하지 않는 키를 조회할 경우, 에러 메세지 대신 디폴트 값을 기준으로 해당하는 키에 대한 딕셔너리 아이템을 생성한다. 이는 collections.defaultdict 클래스를 가진다.

>>> d = collections.defaultdict(int)
>>> d['one'] = 1
>>> d['two'] = 2
>>> d
defaultdict(<class 'int'>, {'one': 1, 'two': 2})
>>> d['three'] += 3
>>> d
defaultdict(<class 'int'>, {'one': 1, 'two': 2, 'three': 3})

위와 같이 존재하지 않는 키인 'three'에 접근했는데 에러 메세지가 뜨지 않고 디폴트인 0을 기준으로 자동 생성 및 계산되었다.

- Counter 객체

Counter 객체는 요소에 대해 개수를 계산하여 딕셔너리로 반환한다. 요소의 값을 키로, 해당 요소의 개수를 값으로 하는 딕셔너리를 만들고 이를 한 번 더 래핑하여 collection.Counter 클래스를 갖는다. 또 most_common() 같은 함수도 있어 유용하게 이용 가능하다.

>>> l = [1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 6]
>>> c = collections.Counter(l)
>>> c
Counter({4: 4, 2: 2, 3: 2, 6: 2, 1: 1, 5: 1})
>>> type(c)
<class 'collections.Counter'>
>>> c.most_common(4)
[(4, 4), (2, 2), (3, 2), (6, 2)]

- OrderedDict 객체

파이썬의 딕셔너리는 다른 언어의 해시 테이블을 이용한 자료형들과 마찬가지로 원래는 입력 순서가 유지되지 않았다. 물론 파이썬 3.7 이후 부터는 입력 순서가 유지되도록 개선되었지만, 실제 코딩테스트를 볼 때 인터프리터의 버전이 어떤 것일지 모르므로 무작정 딕셔너리를 사용하며 입력 순서가 유지될 것이라고 생각하는 것은 위험하다. 따라서 collections.OrderedDict를 통해 입력 순서가 유지되는 딕셔너리를 다음과 같이 이용할 수 있다.

>>> od = collections.OrderedDict({'1': 1, '2': 2, '3': 3})
>>> od
OrderedDict([('1', 1), ('2', 2), ('3', 3)])
>>> od['4'] = 4
>>> od
OrderedDict([('1', 1), ('2', 2), ('3', 3), ('4', 4)])