[Python] List & Dictionary

리스트 (List)

"순서대로 저장하는 시퀀스이자 변경 가능한 동적 배열"

리스트 주요 연산

연산	시간복잡도	설명
len(a)	O(1)	전체 요소의 개수 리턴
a[i]	O(1)	인덱스 i의 요소
a[i:j]	O(k)	i부터 j까지 k개의 요소
elem in a	O(n)	elem 요소가 존재하는지 확인
a.count(elem)	O(n)	elem 요소의 개수 리턴
a.index(elem)	O(n)	elem 요소의 인덱스 리턴
a.append(elem)	O(1)	리스트 마지막에 elem 요소 추가
a.pop()	O(1)	리스트 마지막 요소 추출 (스택 연산)
a.pop(0)	O(n)	리스트 첫번째 요소 추출 (큐 연산)
del a[i]	O(n)	i에 따라 다른데 최악의 경우 O(n)
a.sort()	O(nlog n)	Timsort 사용
min(a), max(a)	O(n)	전체 선형 탐색 필요
a.reverse()	O(n)	뒤집기

리스트 활용 방법

# 리스트 선언
a = list()
a = []

# IndexError 예외 처리
try:
    print(a[9])
except IndexError:
    print('존재하지 않는 인덱스')

# 리스트 요소 추가
a.insert(3, 5)    # 인덱스 지정
a.append(4)       # 리스트 마지막에 추가

# 리스트 요소 가져오기
a[3]              # 인덱스 지정
a[1:3]            # slicing
a[1:4:2]          # step

# 리스트 요소 삭제
del a[2]          # 인덱스로 삭제
a.remove(3)       # 값으로 삭제
a.pop(3)          # 삭제될 값을 리턴하고 삭제 수행

딕셔너리 (Dictionary)

"Key : Value 구조로 이뤄진 해시 테이블"

딕셔너리 주요 연산
- collections.OrderedDict() : 항상 입력 순서 유지
- collections.defaultdict() : 항상 디폴트 값 생성 (키 오류 방지)
- collections.Counter() : 요소의 값을 키로 하고 개수 카운팅

연산	시간 복잡도	설명
len(a)	O(1)	요소 개수 리턴
a[key]	O(1)	키를 조회하여 값 리턴
a[key] = value	O(1)	키/값 삽입
key in a	O(1)	키가 존재하는지 확인

딕셔너리 활용 방법

# 딕셔너리 선언 및 초기화
a = dict()
a = {}
a = {'key1': 'value1', 'key2': 'value2'}

# KeyError 예외 처리
try:
    print(a['key4'])
except KeyError:
    print('존재하지 않는 키')

# 딕셔너리 키/값 조회
for k, v in a.items():
    print(k, v)

# 딕셔너리 키 삭제
del a['key']

참고 : 「파이썬 알고리즘 인터뷰」

Python