파이썬 알고리즘 인터뷰 5장을 정리한 내용입니다.
List
- 순서대로 저장하는 시퀸스이자 변경 가능한 목록이다.
- 입력 순서가 유지되며 내부적으로는 동적 배열로 구현되어 있다
- 다양한 기능을 제공한다
- 스택과 큐 중 어떤걸 사용할지 고민하지 않아도 된다
리스트 주요 시간 복잡도
O(1)
- len()
- a[i]
O(k)
- a[i:j] : i부터 j까지 슬라이스의 길이만큼 k개의 요소를 가져온다. 이 경우 객체 k개에 대한 조회가 필요하므로 O(k)다
O(n)
- elem in a
- a.coutnt(elem)
- a.index(elem)
- a.pop()
- del a[i]
- min(a)
- max(a)
- a.reverse()
O(n log n)
- a.sort()
리스트 활용
1
2
a = list()
a = []
딕셔너리
- 키/값 구조로 이뤄진 것이다
- 내부적으로는 해시 테이블로 되어 있다
딕셔너리 시간 복잡도
O(1)
- len(a)
- a[key]
- a[key] = value
- key in a
딕셔너리 활용 방법
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a = dict()
b = {}
n = {'key1': 'value1', 'key2': 'value2'}
print(n)
print(n['key1'])
# {'key1': 'value1', 'key2': 'value2'}
# value1
del n['key1']
print(n)
# {'key2': 'value2'}
print('key3' in n)
# False
딕셔너리 모듈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import collections
a = collections.defaultdict(int)
a['A'] = 6
a['B'] = 4
print(a)
# defaultdict(<class 'int'>, {'A': 6, 'B': 4})
a['C'] += 1
print(a)
# defaultdict(<class 'int'>, {'A': 6, 'B': 4, 'C': 1})
q = [1, 2, 5, 4, 5, 7, 7, 7, 9]
b = collections.Counter(q)
print(b)
print(b.most_common(2))
# Counter({7: 3, 5: 2, 1: 1, 2: 1, 4: 1, 9: 1})
# [(7, 3), (5, 2)]
order_dict = collections.OrderedDict({'ba': 3, 'app': 5, 'dfdf': 0})
print(order_dict)
# OrderedDict([('ba', 3), ('app', 5), ('dfdf', 0)])
defaultdict 객체
- 존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해 준다
- 실제로
collections.defaultdict라는 클래스를 가진다
Counter 객체
Counter객체는 아이템에 대한 개수를 계산해 딕셔너리로 리턴한다- 키에는 아이템 값이, 값에는 해당 아이템의 개수가 들어간다
- 빈도수가 가장 높은 요소를 찾기위해서는
most_common()을 사용하면 된다
OrderedDict 객체
- 대부분의 언어에서 해시 테이블을 이용한 자료형은 입력 순서가 유지되지 않는다
OrderedDict객체는 순서가 유지되는 딕셔너리를 제공한다- 파이썬 3.7 부터 딕셔너리는 내부적으로 인덱스를 사용하여 입력 순서가 유지되도록 개선되었다
- 코딩 테스트 환경의 파이썬 버전에 유의해야한다.