해당 시리즈는 [ 파이썬 알고리즘 인터뷰 ] 를 통해 학습한 내용을 정리한 글입니다.
리스트
리스트는 말 그대로 순서대로 저장하는 시퀀스이자 변경 가능한 목록이다.
입력 순서가 유지되고, 내부적으로는 동적 배열로 구현되어 있다.
파이썬에서 리스트를 사용하면 사실상 스택을 사용할지, 큐를 사용할지를 고민하지 않아도 된다.
- 스택과 큐에서 사용 가능한 모든 연산을 제공하기 때문이다. 🙂👍🏻
리스트의 주요 연산 시간 복잡도
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| len(a) | O(1) | 전체 요소의 개수를 리턴함 |
| a[i] | O(1) | 인덱스 i의 요소를 가져옴 |
| a[i:j] | O(k) | i부터 j-1까지 슬라이스의 길이만큼 k개의 요소를 가져옴 |
| elem in a | O(n) | elem 요소가 존재하는지 확인함. 처음부터 순차 탐색 = O(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(n log n) | 정렬함, 최선의 경우 O(n) |
| min(a), max(a) | O(n) | 최소, 최대값을 계산하기 위해 선형 탐색 |
| a.reverse() | O(n) | 뒤집음 |
리스트의 경우 탐색 시 값의 존재 유무를 확인하려면 정렬된 경우 이진탐색이 효율적이다.
그렇지만 매번 정렬이 필요하고, 대개는 정렬이 안되어있다.
리스트의 경우 순차적으로 조회를 하는데 최악의 경우 항상 O(n)이 소요된다.
리스트의 특징
리스트는 연속된 공간에 요소를 배치하는 배열의 장점과 다양한 타입을 연결해 배치하는 연결리스트의 장점을 모두 취했다.
때문에 파이썬은 원시 타입 자료형은 제공하지도 않는다. (ex. char, int ... )
파이썬은 모든 것이 객체이며, 파이썬의 리스트는 객체에 대한 포인터 목록을 관리하는 형태이다.
다른 자료형을 단일 리스트에 모두 통합해서 저장할 수 있지만, 각 자료형의 크기는 저마다 다르기 때문에 이들을 연속된 메모리 공간에 할당하는 것은 불가능하다.
따라서 각각 객체에 대한 참조로 구현할 수 밖에 없다.
인덱스를 조회함에도 모든 포인트의 위치에 찾아가서 타입 코드를 확인하고, 값을 일일히 확인해봐야 하는 등 추가적인 작업이 필요하기 때문에, 속도 면에서도 훨씬 더 불리하다.
🔥 파이썬은 기능을 위해 '리스트+객체' 에 대한 참조를 택했고, 이로 인해 부득이하게 속도를 희생한 측면이 있다.
딕셔너리
딕셔너리는 키-값으로 이뤄진 구조를 말한다.
파이썬 3.7+ 에서는 입력 순서가 유지되며, 내부적으로는 해시 태이블로 구현되어 있다.
-
리스트는 인덱스를 숫자로만 지정할 수 있지만, 딕셔너리는 다양한 타입을 키로 사용할 수 있다.
-
해시할 수만 있다면 모든 불변 객체를 모두 키로 사용할 수 있는데 이 과정을 해싱이라고 한다.
-
해시 테이블을 이용해 자료를 저장한다.
-
딕셔너리의 키를 지정하면 값을 조회할 수 있다.
-
만약 존재하지 않는 키를 조회할 경우에는 에러가 발생한다.
딕셔너리의 주요 연산 시간 복잡도
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| len(a) | O(1) | 요소의 개수를 리턴함 |
| a[key] | O(1) | 키를 조회해 값을 리턴 |
| a[key]=value | O(1) | 키/값을 삽입함 |
| key in a | O(1) | 딕셔너리에 키가 존재하는지 확인함 |
무엇보다 해시 테이블은 입력과 조회 모두 O(1)이다.
최악의 경우 O(n)이 될 수 있지만 대부분의 경우 더 빨리 실행되며, 분할 상환 분석에 따른 시간 복잡도는 O(1)이다.
파이썬 3.6 이하에 있는 딕셔너리 관련 모듈
- 항상 입력 순서가 유지되는 collections.OrderedDict()
- 조회 시 항상 디폴트 값을 생성해 키 오류를 방지하는 collections.defaultdict()
- 요소의 값을 키로 하고, 개수를 값 형태로 만들어 카운팅하는 collections.Counter()
딕셔너리 모듈
defaultdict 객체
defaultdict 객체는 존재하지 않는 키를 조회할 경우, 에러 메세지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해준다.
>>> a = collections.defaultdict(int)
>>> a['A'] = 5
>>> a['B'] = 4
>>> a
defaultdict(<class 'int'>, {'A':5, 'B':4})
>>> a['C'] += 1
>>> a
defaultdict(<class 'int'>, {'A':5, 'B':4, 'C':1})- 디폴트가 0인 경우 자동으로 생성 후 1을 더해 최종적으로 1이 만들어진다.
Counter 객체
Counter 객체는 아이템에 대한 개수를 계산해 딕셔너리로 리턴해준다.
>>> a = [1,2,2,3,3,3]
>>> b= collections.Counter(a)
>>> b
Counter({1:1, 2:2, 3:3})-
Counter 객체는 이처럼 키에는 아이템 값이, 값에는 해당 아이템의 수가 들어간 딕셔너리를 생성한다.
-
가장 빈도수가 높은 요소는 most_common()을 사용한다.
>>> b.most_common()
[(3,3)]
>>> b.most_common(2)
[(3,3),(2,2)]OrderedDict 객체
대부분의 언어에서 해시테이블을 이용한 자료형은 입력 순서가 유지되지 않는다.
파이썬 3.6 이하에서도 마찬가지였고 입력 순서가 유지되는 OrderedDict라는 별도의 객체를 제공했다.
>>> collections.OrderedDict({'banana':3, 'apple':4, 'orange':2})
#출력 : OrderedDict([('banana',3), ('apple',4), ('orange',2)])파이썬 3.7부터는 딕셔너리는 내부적으로 인덱스를 이용하면서 입력순서가 유지되도록 개선되었다.
그렇지만 코테에서 3.7 이상의 버전을 쓴다는 기대를 하면 안된다.
따라서 orderedDict 모듈의 존재를 알아두어야 한다!
타입 선언
>>> type([])
<class 'list'>
>>> type(())
<class 'tuple'>
>>> type({})
<class 'dict'>
>>> type({1})
<class 'set'>각각 리스트, 튜플, 딕셔너리, 집합을 기호로 선언한 경우다.
자료형 기호 리스트 [ ] 튜플 ( ) 딕셔너리 { } 집합 { }
- 딕셔너리와 집합은 같은 중괄호
{}를 사용하지만 키의 존재 유무로 서로 다른 자료형으로 선언된다.
