요즘 코딩 테스트 언어를 파이썬으로 정하고 조금씩 문제를 풀어보는 중이다. 친구에게 <파이썬 알고리즘 인터뷰> 라는 책을 추천받고 이 책에 나오는 문제들로 공부를 해보는 중에 리스트와 딕셔너리의 주요 연산 시간 복잡도에 대한 설명을 봤다. 평소에 시간복잡도에 대해서 잘 생각하지 않고 코딩을 했는데, 이 기회에 리스트와 딕셔너리에 대해 공부하고 기록하려고 한다.

리스트

파이썬의 리스트는 말 그대로 순서대로 저장하는 시퀀스이자 변경 가능한 목록을 말한다. 입력 순서가 유지되며, 내부적으로는 동적 배열로 구현되어 있다.

리스트의 주요 연산 시간 복잡도

연산	시간 복잡도	설명
len(a)	$O(1)$	전체 요소의 개수를 리턴한다.
a[i]	$O(1)$	인덱스 $i$의 요소를 가져온다.
a[i:j]	$O(k)$	$i$부터 $j$까지 슬라이스의 길이만큼 $k$개의 요소를 가져온다. 이 경우 객체 $k$개에 대한 조회가 필요하므로 $O(k)$이다.
elem in a	$O(n)$	elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 $n$만큼 시간이 소요된다.
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)$	리스트 첫번째 요소를 추출한다. 큐의 연산이다. 이 경우 전체 복사가 필요하므로 $O(n)$이다.
del a[i]	$O(n)$	i에 따라 다르다. 최악의 경우 $O(n)$이다.
a.sort()	$O(nlogn)$	정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 $O(n)$에도 실행될 수 있다.
min(a), max(a)	$O(n)$	최솟값/최댓값을 계산하기 위해서는 전체를 선형탐색해야 한다.
a.reverse()	$O(n)$	뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다.

리스트의 활용 방법

• 리스트 선언

a = list()
# 또는
a = []

• 리스트에 요소 추가1(append)

a = [1, 2, 3]
a.append(4)
# a
[1, 2, 3, 4]

• 리스트에 요소 삽입(insert)

a.insert(3, 5)
# a
[1, 2, 3, 5, 4]

• 리스트에 요소 추가2(append)
  파이썬의 리스트는 다양한 자료형을 단일 리스트에서 관리할 수 있다.

a.append('안녕')
a.append(True)
# a
[1, 2, 3, 5, 4, '안녕', True]

• 리스트 슬라이싱(slicing)
  특정 범위 내의 값을 편리하게 가져오는 기능

slice1 = a[1:3]
# slice1
[2, 3]

slice2 = a[:3]
# slice2
[1, 2, 3]

slice3 = a[4:]
# slice3
[4, '안녕', True]

# 인덱스 1, 3의 값
slice4 = a[1:4:2]
# slice4
[2, 5]

• 리스트의 요소 삭제

# a
[1, 2, 3, 5, 4, '안녕', True]
a.remove(3)
# a
[1, 2, 3, 4, '안녕', True]

• 리스트의 요소 추출

# a
[1, 2, 3, 4, '안녕', True]
pop_value = a.pop(4)
# pop_value
'안녕'
# a
[1, 2, 3, 4, True]

딕셔너리

파이썬의 딕셔너리는 키/값 구조로 이뤄진 딕셔너리를 말한다. 파이썬 3.7+에서는 입력 순서가 유지되며, 내부적으로는 해시 테이블로 구현되어 있다.

딕셔너리의 주요 연산 시간 복잡도

연산	시간 복잡도	설명
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'}
a['key3'] = 'value3'
# a
{'key1':'value1', 'key2':'value2', 'key3':'value3'}

• 딕셔너리의 값 조회1

value = a['key1']
# value
'value1'

• 딕셔너리의 값 조회2(for 반복문)

for k, v in a.items():
	print(k, v)
    
# 결과
key1 value1
key2 value2
key3 value3

출처: 파이썬 알고리즘 인터뷰