[Python Algorithm Interview] 03. 리스트, 딕셔너리

리스트, 딕셔너리

리스트

• C++에서는 std::vector, JAVA에서는 ArrayList에 해당합니다.
• 파이썬에서 리스트의 마지막 요소의 .append(), pop()에 대해서는 O(1)의 시간 복잡도를 갖습니다.
• 반면, 첫 번째 요소를 추출하는 pop(0)은 O(1)의 시간 복잡도라고 생각할 수 있으나, O(n)의 시간 복잡도를 갖습니다.
  • 이 경우, Deque와 같은 자료형을 사용하여 성능을 높일 수 있습니다.

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

연산	시간 복잡도	비고
len(a)	O(1)
a[i]	O(1)
a[i:j]	O(k)	i부터 j까지 슬라이싱한 길이인 k만큼
element in a	O(n)	순차 탐색이라 n만큼 시간 소요
a.count(element)	O(n)
a.index(element)	O(n)
a.append(element)	O(1)
a.pop()	O(1)
a.pop(0)	O(n)	큐의 연산이며, 전체 복사로 O(n)
del a[i]	O(n)	i에 따라 다르며, 최악의 경우 O(n)
a.sort()	O(n log n)	Timsort를 사용하며, 최선의 경우 O(n)
min(a), max(a)	O(n)	전체를 선형 탐색
a.reverse()	O(n)	리스트는 입력 순서가 유지되어 뒤집게 되면 입력 순서가 반대로 됨

python 리스트 활용법

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

# 추가
'''리스트의 가장 뒤에 value 추가'''
a.append(value)

'''리스트의 index 위치에 value 추가'''
a.insert(index, value)

# 슬라이싱
'''리스트의 index i부터 j까지의 값들을 리스트로 반환'''
a[i:j]

'''리스트의 처음부터 index i까지 값들을 리스트로 반환'''
a[:i]

'''리스트의 index i부터 마지막까지의 값들을 리스트로 반환'''
a[i:]

'''리스트의 index i부터 j까지의 값들 중 k만큼 건너뛴 값들을 리스트로 반환'''
a[i:j:k]

# 삭제
'''리스트의 index i에 해당하는 값 삭제'''
del a[i]

a.pop(i) # i를 입력하지 않았을 경우, 리스트에서 가장 뒤에 있는 값을 삭제

'''리스트의 value에 해당하는 값 삭제'''
a.remove(value)

리스트의 특징

• 파이썬은 모든 것이 객체이기 때문에, 리스트는 객체에 대한 포인터 목록을 관리하는 형태로 구현되어 있음
  • 사실상 연결 리스트에 대한 포인터 목록을 배열 형태로 관리하고 있음
  • 배열과 연결 리스트를 합친 듯한 강력한 기능 제공
• 리스트 안에 여러 자료형을 담을 수 있음
• 그러나, 속도가 느리다는 단점을 지님

딕셔너리

• Key-Value 구조
• 해시 테이블로 구현됨
• C++에서는 std::unordered_map, JAVA에서는 HashMap에 해당
• 해시 테이블은 다양한 타입을 키로 지원하면서 I/O에 대한 시간복잡도가 O(1)
  • 최악의 경우 O(n)이지만, 분할 상환 분석에 따라 시반 복잡도는 O(1)
• 파이썬 3.6버전부터 딕셔너리 메모리 사용량이 20% 감소되었고, 3.7버전부터 딕셔너리 입력 순서를 유지함

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

연산	시간 복잡도	비고
len(dict)	O(1)
dict[key]	O(1)
dict[key] = value	O(1)
key in a	O(1)	딕셔너리에 키가 존재하는지 확인

딕셔너리의 활용 방법

# 선언
dic1 = dict()

dic2 = {}

# 추가
dic = {'key1': 'value1', 'key2': 'value2'}

dic['key3'] = 'value3'

# 삭제
del a['key3']

# 존재하지 않는 키에 대한 예외 처리
'''try-catch'''
try:
    print(dic['key1'])
except:
    print('존재하지 않는 키 입니다')

'''if문'''
if 'key4' in dic:
    print(True)
else:
    print(False)

# 반복문
for key, value in dic.items():
    print(key, value)

딕셔너리 모듈

• defaultdict 객체
  • 존재하지 않는 키를 조회했을 때, 에러 메시지 대신 디폴트 값을 기준으로 키에 대한 아이템을 생성
  • collections.defaultdict(value) 클래스를 갖음

dic = collections.defaultdict(int) # 기본값으로 정수형 0을 갖음
dic['k1'] = 10
dic['k2'] = 5
dic['k3'] += 10 # defaultdict를 사용하지 않았다면 에러 메시지를 출력하지만, dic['k3']에 0 + 10 값이 저장

• Counter 객체
  • 객체의 아이템의 값이 키, 아이템의 개수는 값으로 반환
    • 예를들어, 리스트의 값들의 개수를 딕셔너리로 {value1:count of value1}형태로 반환
  • collections.Counter(dictionary) 클래스를 갖음
• OrderedDict 객체
  • 파이썬 3.6버전 이하에서는 해시 테이블의 값의 입력 순서가 유지되지 않아 제공했던 객체
  • 파이썬 3.7버전부터는 내부적으로 index를 이용하여 입력 순서가 유지되어 더 이상 사용할 필요가 없어짐
  • collections.OrderedDict(dictionary) 클래스를 갖음