Python Basic/파이썬 알고리즘 인터뷰
[2부] 05장 리스트, 딕셔너리
EASYH
2021. 2. 6. 21:28
파이썬을 사용하면서 가장 빈번하게 접하게 될 자료형
- 리스트 (Mutable)
- 딕셔너리 (Mutable)
리스트 (List)
파이썬의 리스트
- 순서대로 저장하는 시쿼스
- 변경 가능한 목록 (Mutable List)
- 입력 순서 유지
- 내부적으로는 동적 배열로 구현
- 동적 배열 (Danamic array): 크기가 고정되지 않은 배열 (7장 배열에서 자세히 소개) <-> 정적 배열 (Static array)
- 정적 배열 (Static array): 크기가 고정되어 있어, 데이터를 크기 만큼만 저장할 수 있음.
파이썬 리스트는 다양한 기능을 제공함.
- 리스트를 사용하면 사실상 스택을 사용할지, 큐를 사용할지 고민하지 않아도 됨 (스택, 큐는 9장에서 다룸). 스택과 큐에서 사용 가능한 모든 연산 제공.
- 또한 리스트는 O(1)에 실행 가능한 연산들도 있음.
- 리스트 마지막에 요소를 .append() 로 추가.
- 리스트 마지막 요소를 pop() 으로 추출.
- 원하는 인덱스의 요소 조회
리스트의 주요 연산 시간 복잡도
| 연산 | 시간 복잡도 | 설명 |
| 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(n log n) | 정렬 (팀소트 사용), 최선의 경우 O(n) 에도 실행 가능 |
| min(a), max(a) | O(n) | 최솟값/최댓값 계산 |
| a.reverse() | O(n) | 뒤집음 |
리스트 활용 방법
1. 리스트 선언
- 2가지 방법
- a = list()
- a = []
2. 리스트 요소 추가
- 초깃값을 지정해 선언
- a= [1, 2, 3]
- append() 로 추가
- a.append(4)
- insert() 로 추가
- 특정 위치의 인덱스를 지정해 요소 추가.
- a.insert(3, 5)
3. 리스트 요소 추출
- 간단히 인덱스 지정
- a[3]
- 슬라이싱 (slicing)
- 특정 범위 내의 값을 가져옴
- 원래 슬라이싱은 문자열에 유용하게 활용되는 기능으로서, 리스트에도 동일한 형태도 활용할 수 잇음.
- a[1:3]
- a[:3]
- a[1:]
4. 리스트 요소 삭제
- 2가지 방법
- 인덱스로 삭제하기 (del 키워드, pop() 함수)
- del a[1]
- a.pop(3)
- 값으로 삭제하기 (remove() 함수)
- a.remove('안녕')
- 인덱스로 삭제하기 (del 키워드, pop() 함수)
리스트의 특징
리스트는 배열과 연결 리스트의 장점을 모두 취한 듯한 형태를 가짐.
- 배열의 장점: 연속된 공간에 요소를 배치함 (7장 배열)
- 연결 리스트의 장점: 다양한 타입을 연결해 배치함 (8장 연결 리스트)
- 연결 리스트: 각 노드가 데이터와 포인터를 가지고, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
CPython에서 리스트는 요소에 대한 포인터 목록(ob_item)을 갖고 있는 구조체(Struct)로 선언됨.
- 리스트에 요소를 추가하거나 조작하면, ob_item의 사이즈를 조정해 나타는 형태로 구현.
- 즉, 리스트는 객체로 되어 있는 모든 자료형을 포인터로 연결함.
- 파이썬 리스트는 객체에 대한 포인터 목록을 관리하는 형태로 구현
- 일반적으로 동적 배열에 삽입할 수 있는 자료형은 동일한 타입으로 제한되는 경우가 많음 (e.g. 정수형 배열이라고 하면, 정수가 아닌 값은 저장할 수 없음).
- 그러나 파이썬의 리스트는 연결 리스트에 대한 포인터 목록을 관리하고 있기 때문에 정수, 문자, 불리언 등 제작기 다양한 타입을 동시에 단일 리스트에서 관리할 수 있음.
- 각 자료형의 크기는 저마다 서로 다르기 때문에 이들을 연속된 메모리 공간에 할당하는 것은 불가능. 각각의 객체에 대한 참조로 구현할 수 밖에 없고, 당연히 인덱스를 조회하는 데에도 모든 포인터의 위치를 찾아가서 확인하는 등의 추가 작업이 필요함.
- 파이썬은 강력한 기능을 위해 리스트와 객체에 대한 참조를 택했으며, 이로 인해 부득이하게 속도를 희생한 측면이 있음.
딕셔너리 (Dictionary)
파이썬의 딕셔너리
- 키/값 구조로 이뤄진 딕셔너리
- 파이썬 3.7+ 에서는 입력 순서 유지
- 내부적으로는 해시 테이블 (Hash table)로 구현되어 있음.
- 해시 테이블: (Key, Value)로 데이터를 저장하는 자료구조 중 하나로, 빠르게 데이터를 검색할 수 있는 자료구조 (11장 해시 테이블에서 상세하게 소개)
- 키 값: 해시할 수만 있다면, 불면 객체(숫자, 문자, 집합 등)를 모두 키로 사용할 수 있음. -> 이 과정을 해싱이라고 함.
- 리트코드 문제를 풀면서, 딕셔너리 오류에 키 값을 해시할 수 없다는 에러 떴음. -> 다시 살펴보니까, 키 값에 리스트 (mutable) 가 들어가 있어서 해시할 수 없었나 봄.
딕셔너리의 주요 연산 시간 복잡도
| 연산 | 시간 복잡도 | 설명 |
| len(a) | O(1) | 요소의 개수 리턴 |
| a[key] | O(1) | 키를 조회하여 값 리턴 |
| a[key] = value | O(1) | 키/값 삽입 |
| key in a | O(1) | 딕셔너리에 키가 존재하는지 확인 |
- 해시 테이블은 다양한 타입을 키로 지원하면서도, 입력과 조회 모두 O(1)에 가능.
- 해시 테이블은 최악의 경우 O(n)이 될 수 있으나, 대부분의 경우 훨씬 더 빨리 실행되고, 분할 상환 분석에 따른 시간 복잡도는 O(1) 임.
- 해시 테이블에 대해 설명 잘 되어있음.
[자료구조] 해시테이블(HashTable)이란?
1. 해시테이블(HashTable)이란? [ HashTable(해시테이블)이란? ] 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른
mangkyu.tistory.com
딕셔너리 활용 방법
1. 딕셔너리 선언
- 2가지 방법
- a = dict()
- a = {}
2. 딕셔너리 값 할당
- a = {'key1':'value1', 'key2':'value2'}
- a['key3'] = 'value3'
3. 딕셔너리 값 조회
- a['key1']
4. 딕셔너리 값 삭제
- del a['key1']
딕셔너리 모듈
딕셔너리와 관련된 특수한 형태의 컨테이너 자료형
- defaultdict
- Counter
- OrderedDict
defaultdict 객체 => 6장 문제 풀이에 사용
- 존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성함.
- 실제로는 collections.defaultdict 클래스를 가짐.
Counter 객체 => 6장 문제 풀이에 사용
- 아이템에 대한 개수를 계산해 딕셔너리로 리턴
- key에는 아이템의 값이, value에는 해당 아이템의 개수가 들어간 딕셔너리를 생성함.
- 실제로는 collections.Counter 클래스를 가짐.
- Counter 객체에서 가장 빈도 수가 높은 요소 추출은 most_common() 을 사용하면 됨.
OrderedDict 객체
- 대부분 언어에서 해시 테이블을 이용한 자료형은 입력 순서가 유지되지 않음.
- 파이썬 3.6 이하에서는 마찬가지였고, 입력 순서가 유지되는 OrderedDict 라는 별도의 객체를 제공함.
- 그러나 파이썬 3.7 부터 딕셔너리는 내부적으로 인덱스를 이용하며, 입력 순서가 유지되도록 개선됨.
- 따라서, 더 이상 OrderedDict를 사용할 필요는 없으며, 기본 딕셔너리만 사용해도 입력 순서가 충분히 유지됨. 그러나 코딩 테스트 시 하위 버전의 파이썬 인터프리터를 사용하는 경우가 있고, 원래 해시 테이블은 입력 순서에 관여하지 않는 자료형인 만큼, 무턱대로 딕셔너리로 입력 순서를 기대하는 것은 권장하지 않음.
- 파이썬 3.7+: 딕셔너리 입력 순서 유지
- 파이썬 3.6+: 딕셔너리 메모리 사용량 20% 감소