배열 기반의 연속 방식(2) - 컬렉션 자료구조(set, 딕셔너리)

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 자료구조 내용입니다.

<컬렉션 자료구조 - set, 딕셔너리>

컬렉션 자료구조는 데이터를 서로 연관시키지 않고 모아두는 컨테이너이다.

set

set의 시작복잡도

삽입 O(1)

합집합 O(m+n)

교집합 O(n) m>n

set 메서드

A.update(B) 또는 합집합 A \| =B		A를 B에 추가
A.union(B) 또는 합집합 A \| B		A를 B에 추가, 결과를 복사본으로 반환
A.intersection(B) 또는 교집합 A & B		A와 B의 교집합, 결과를 복사본으로 변환
A.difference(B) 또는 차집합 A - B		A와 B의 차집합, 결과를 복사본으로 변환
A.add(x)		A에 x가 없는 경우 추가
A.discard(x)		A의 항목 x제거
A.remove(x)		A의 항목 x제거, x가 A에 없을 경우 KeyError반환
A.pop()		A에서 random으로 한 항목 제거, 반환

딕셔너리

딕셔너리의 시간복잡도

항목 접근 O(1)

복사, 반복 O(n)

딕셔너리 메서드

setdefault()	키 존재 여부 모른채 접근, 키 없으면 오류 발생
A.setdefault(key,value)	A에 key가 존재할 경우는 value값 반환, 존재하지 않을 경우에는 새key와 default값 저장
A.update(B)	A의 (키, 값)을 B의 (키, 값)으로 갱신, B의 키가 A의 키 중에 없다면 추가
A.get(key)	A의 key값 반환
items(), keys(), values() 딕셔너리 뷰	딕셔너리 항목 조회(읽기만 가능)
A.pop(key)	A의 key항목 제거, 반환
A.popitem()	A의 key와 value 제거, 반환

딕셔너리 순회(for문)

for문을 통해 딕셔너리를 for문을 돌리면 key값이 할당된다.
순서는 임의적이다.같은 순서를 보장할 수 없다.
value값으로 for문을 반복하기 위해서는 values() 를 사용하고, key와 value를 한꺼번에 for문을 반복하려면 items() 를 사용한다.
정렬된 상태에서 순회하려면 딕셔너리를 sorted()를 사용해 정렬해 for문에 사용한다.

collection 모듈 딕셔너리

collections.defaultdict - 기본 딕셔너리 : 딕셔너리(dictionary)와 거의 비슷하지만 key값이 없을 경우 미리 지정해 놓은 초기(default)값을 반환하는 dictionary이다.
collections.OrderDict - 정렬된 딕셔너리 : 기본 딕셔너리(dictionary)와 거의 비슷하지만, 입력된 아이템들(items)의 순서를 기억하는 Dictionary 클래스이기 때문에 sorted()함수를 사용하여 정렬된 딕셔너리(sorted dictionary)를 만들때 사용할 수 있다.
collections.Counter - 카운터 딕셔너리 : 컨테이너에 동일한 값의 자료가 몇개인지를 파악하는데 사용하는 객체이다.

collection 모듈 딕셔너리의 자세한 내용은 docs.python.org에서 확인할 수 있다.