3. 컬렉션 (Collection): 파이썬 자료구조와 알고리즘

https://github.com/beomseok-kang/DSA-examples 에서 예제에 대한 내가 쓴 답을 볼 수 있다.

 

 

컬렉션 (collection) 자료구조는 시퀀스 자료구조와 달리, 데이터를 서로 연관시키지 않고 (relating) 모아두는 컨테이너이다. 컬렉션 자료구조는 시퀀스 자료구조가 갖던 속성 중 아래 세 가지 속성을 지닌다.

• 멤버십 연산자: in
• 크기 함수: len(seq)
• 반복성: 반복문의 데이터를 순회

파이썬의 내장 컬렉션 (collection) 데이터 타입은 셋 (set) 과 딕셔너리 (dictionary) 가 있다.

셋 (Set)

파이썬의 셋 (set) 은 반복 가능하고, 가변적 (mutable) 이며, 중복 요소가 없고 정렬되지 않은 컬렉션 데이터 타입이다. 셋은 멤버십 테스트 및 중복 항목 제거에 사용된다. 셋의 시간복잡도는 O(1)이고, 합집합의 시간복잡도는 O(m+n)이다. 교집합의 경우, 두 셋 중 더 작은 셋에 대해서만 계산하면 되므로 시간복잡도는 O(n)이다.

셋 메서드

add( )

a.add(x) 는 셋 a 에 x가 없는 경우 x를 추가한다.

>>> a = {1, 2, 3, 4}
>>> a.add(5)
>>> a
{1, 2, 3, 4, 5}
>>> a.add(4)
>>> a
{1, 2, 3, 4, 5}

update( ) 와 |= 연산자

a.update(b) 혹은 a|=b 는 b라는 셋을 a라는 셋에 추가한다 (합집합, union).

>>> a = {1, 2, 3,}
>>> a.update({4, 5})
>>> a
{1, 2, 3, 4, 5}
>>> a|={6, 7}
>>> a
{1, 2, 3, 4, 5, 6, 7}

union( ) 과 | 연산자

a.union(b) 혹은 a|b 는 위 update() 와 같은 일을 하지만 원본에 적용하는 대신 복사본을 반환한다.

>>> a = {1, 2, 3}
>>> a.union({4, 5})
{1, 2, 3, 4, 5}

intersection( ) 과 & 연산자

a.intersection(b) 와 a&b는 a 와 b 의 교집합의 복사본을 반환한다.

>>> a = {1, 2, 3, 4, 5}
>>> b = {4, 5, 6, 7}
>>> a.intersection(b)
{4, 5}

difference( ) 와 - 연산자

a.difference(b) 와 a-b는 a에서 b를 뺀 차집합의 복사본을 반환한다.

>>> a = {1, 2, 3, 4, 5}
>>> b = {4, 5, 6, 7}
>>> a.difference(b)
{1, 2, 3}

clear( )

a.clear() 는 a 의 모든 항목을 제거한다.

>>> a = {1, 2, 3, 4}
>>> a.clear()
>>> a
set()

discard( ), remove( ), pop( )

a.discard(x) 는 a의 항목 x를 제거하며, 반환값은 없다. a.remove(x) 는 discard와 같지만 x 항목이 없을 경우 KeyError 에러를 발생시킨다. a.pop() 은 a 에서 무작위 한 항목을 제거하고 그 항목을 반환하며, 만약 a가 빈 셋이라면, KeyError 에러를 발생시킨다.

>>> a = {1, 2, 3, 4}
>>> a.discard(1)
>>> a
{2, 3, 4}
>>> a.remove(2)
>>> a
{3, 4}
>>> a.remove(5)
Traceback (most recent call last):
  File "<pyshell#26>", line 1, in <module>
    a.remove(5)
KeyError: 5
>>> a.pop()
3
>>> a.pop()
4
>>> a.pop()
Traceback (most recent call last):
  File "<pyshell#29>", line 1, in <module>
    a.pop()
KeyError: 'pop from an empty set'

셋과 리스트

리스트 타입은 셋 타입으로 변환할 수 있다 (casting).

>>> a = [1, 2, 3, 4]
>>> set(a)
{1, 2, 3, 4}
>>> b = [3, 4, 5, 6]
>>> set(a).intersection(set(b))
{3, 4}

딕셔너리에서도 셋 속성을 사용할 수 있다.

딕셔너리

파이썬 딕셔너리 (dictionary) 는 해시 테이블 (hash table) 로 구현되어 있다. 해시 함수는 특정 객체에 해당하는 임의의 정수 값을 상수 시간 내에 계산한다. 이 정수는 연관 배열의 인덱스로 사용된다.

>>> hash(33)
33
>>> hash('hello world!')
-1261253343

컬렉션 매핑 타입 (mapping type) 인 딕셔너리는 반복 가능하다. 그리고 멤버십 연산자 in 과 길이를 구하는 len() 함수도 지원한다. 매핑은 키 - 값 항목의 컬렉션이고, 각 항목에 대한 메서드를 제공한다. 딕셔너리를 순회할 때, 정렬되지 않은 매핑 타입은 임의의 순서대로 항목을 순회한다.

딕셔너리의 항목은 고유하다. 따라서 항목에 접근하는 시간복잡도는 O(1)이다. 딕셔너리는 변경 가능하며, 항목의 추가와 제거가 가능하다. 딕셔너리는 항목의 삽입 순서를 기억하지 않으며, 인덱스 위치 또한 사용할 수 없다. 따라서 슬라이스도 사용할 수가 없다. (단, 파이썬 3.7부터는 표준 딕셔너리도 항목의 삽입 순서를 보존한다.)

>>> a = dict({"one": 1, "two": 2})
>>> a
{'one': 1, 'two': 2}
>>> a['three'] = 3
>>> a
{'one': 1, 'two': 2, 'three': 3}

딕셔너리 메서드

setdefault( )

setdefault() 메서드는 딕셔너리의 키 (key) 의 존재 여부를 모른 채, 접근할 때 사용된다 (딕셔너리의 존재하지 않는 키에 접근하면 에러가 난다). a.setdefault(key, default) 를 사용하면, 딕셔너리 a에 key가 존재할 경우 키에 해당하는 값을 얻을 수 있고, key가 존재하지 않는다면, 새 키와 기본값 default가 딕셔너리에 저장된다.

>>> a = dict({ 'one': 1, 'two': 2 })
>>> a.setdefault('one', 3)
1
>>> a
{'one': 1, 'two': 2}
>>> a.setdefault('three', 3)
3
>>> a
{'one': 1, 'two': 2, 'three': 3}

update( )

a.update(b) 는 딕셔너리 a 에 딕셔너리 b 의 키가 존재한다면, 기존 a의 해당 키의 값을 b의 해당 키의 값으로 갱신한다. 만약 해당 키가 a 에 존재하지 않는다면, 해당 키와 값을 a에 추가한다.

>>> a = dict({'one': 1, 'two': 2})
>>> a.update({'three': 3})
>>> a
{'one': 1, 'two': 2, 'three': 3}
>>> a.update({'one': '일'})
>>> a
{'one': '일', 'two': 2, 'three': 3}

get( )

a.get(key) 는 a 의 key의 값을 반환한다. key가 존재하지 않으면 아무것도 반환하지 않는다.

>>> a = dict({'one': 1, 'two': 2})
>>> a.get('one')
1
>>> a.get('three')
>>> a.get('two')
2

items( ), values( ), keys( )

a.items() 와 a.values(), a.keys() 모두 딕셔너리 뷰 (view) 이다. 각각 a의 항목, 값, 키들을 조회하는 읽기 전용의 반복 가능한 객체다.

>>> a = dict({'one': 1, 'two': 2, 'three': 3})
>>> a.items()
dict_items([('one', 1), ('two', 2), ('three', 3)])
>>> a.values()
dict_values([1, 2, 3])
>>> a.keys()
dict_keys(['one', 'two', 'three'])

pop( ), popitem( )

a.pop(key) 는 딕셔너리 a 의 key 키를 가진 항목을 제거한 후, 그 항목을 반환한다. a.popitem() 은 딕셔너리 a 에서 무작위 항목을 제거한 후, 그 키와 항목을 반환한다.

>>> a = dict({'one': 1, 'two': 2, 'three': 3})
>>> a.pop('one')
1
>>> a
{'two': 2, 'three': 3}
>>> a.popitem()
('three', 3)
>>> a
{'two': 2}

clear( )

a.clear() 는 딕셔너리 a의 모든 항목을 제거한다.

>>> a = dict({'one': 1, 'two': 2, 'three': 3})
>>> a.clear()
>>> a
{}

딕셔너리 순회

반복문에서 딕셔너리를 순회할 때는 기본적으로 키를 사용한다. 딕셔너리의 키는 임의의 순서대로 나타나지만 (3.7부터는 삽입된 순서), sorted()함수를 사용해 정렬된 상태로 순회할 수 있다. sorted() 함수는 딕셔너리의 keys(), values(), items()에 사용할 수 있다.

>>> a = dict({'one': 1, 'two': 2, 'three': 3})
>>> for key in a.keys():
    print(key)

one
two
three

딕셔너리 분기

딕셔너리를 이용해서 효율적인 분기를 할 수 있다.

>>> def hello():
    print('hello')

>>> def world():
    print('world')

>>> functions = dict(h=hello, w=world)
>>> functions['h']()
hello
>>> functions['w']()
world

파이썬 컬렉션 데이터 타입

파이썬의 collections 모듈은 다양한 딕셔너리 타입을 제공한다. 내장 기능보다 더 강력한 성능을 보인다.

기본 딕셔너리

기본 딕셔너리 (default dictionary) 는 collections.defaultdict 모듈에서 제공하는 추가 딕셔너리 타입이다. defaultdict 는 내장 딕셔너리의 모든 연산자와 메서드를 사용할 수 있고, 추가로 안에 들어갈 타입을 지정해 줄 수 있다.

정렬된 딕셔너리

정렬된 딕셔너리 (ordered dictionary) 는 collections.OrderedDict 모듈에서 제공한다. OrderedDict 역시 모든 메서드와 속성을 가지며 추가로 삽입 순서대로 항목을 저장한다.

카운터 딕셔너리

카운터 (counter) 타입은 해시 가능한 (hashable) 객체를 카운팅하는 특화된 서브클래스이다. collectionsCouter 모듈에서 제공한다.

>>> from collections import Counter
>>> a = [1, 1, 1, 2, 2, 3, 3, 3, 3, 3]
>>> counts = Counter(a)
>>> counts
Counter({3: 5, 1: 3, 2: 2})

연습문제

1. 단어 횟수 세기
2. 애너그램 확인 (한 단어가 다른 단어의 글자 순서만 바꾼 단어인지 확인)
3. 주사위 합계 경로 (주사위를 두 번 던져 합계가 특정 수가 나오는 경우의 수와 경로를 구하기)
4. 단어의 중복문자 제거 (중복되는 문자를 모두 찾아서 제거)

출처

파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인