이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.
5장 리스트, 딕셔너리
- 리스트와 딕셔너리는 코딩 테스트에서 무조건 사용
- 문제 풀이에 자유자재로 활용할 수 있도록 숙지
1) 리스트
- 리스트란?
- 순서대로 저장하는 시퀀스
- 입력 순서가 유지됨 - 값을 변경할 수 있는 Mutable
- 동적 배열로 구현됨
- C++의 Vector, Java의 ArrayList - 매우 다양한 기능을 제공
- 스택/큐로써의 기능도 모두 제공
- 이는 다른 언어에 비해 매우 유리한 조건 - 큐로써 사용할 시 주의
- pop(0)는 O(n)을 소요
- 가장 앞의 요소를 제외한 나머지 요소들을 copy해야하기 때문
- Deque를 대산 사용 (추후 다룰 예정) - min/max도 O(n)
- 순차탐색을 하는듯
- 리스트가 정렬되지 않은 경우도 고려함에 따라 O(n)이 소요되는 기능이 많은듯
- 순서대로 저장하는 시퀀스
- 리스트의 활용 방법
- 선언
- a = list()
- a = [] - 삽입
- 초기값 : a = [1, 2, 3]
- append : a.append(4) -> [1, 2, 3, 4]
- insert : a.insert(3, 5) -> [1, 2, 3, 5, 4]
- 타입에 상관없이 삽입 가능 - 읽기
- 인덱스 : a[3] -> 5
- 존재하지 않는 인덱스를 조회 : IndexError - 슬라이싱(간결함, 강력함)
- 특정 인덱스 구간(마지막 이전까지) : a[1:3] -> [2, 3]
- 시작 인덱스 생략 : a[:3] -> [1, 2, 3]
- 종료 인덱스 생략 : a[4:] -> [5, 4]
- 특정 인덱스 주기(1부터 2칸씩) : a[1:4:2] -> [2, 5] - 삭제
- 인덱스로 삭제 : del a[1]
- 값으로 삭제 : a.remove(3)
- pop(삭제하고 값을 반환) : a.pop(3)
- 선언
- 리스트의 특징
- 연속된 공간을 사용하는 배열과 다양한 타입을 연결하는 연결 리스트의 장점을 모두 가짐
- cpython/Include/cpython/listobject.h
- PyObject **ob_item; 이 리스트의 값
- Python Object의 주소를 연속된 공간(배열)에 저장
- 따라서, 다양한 타입을 동시에 리스트에 삽입 가능 - 속도 면에서 불리
- 포인터의 위치를 찾아가서 타입 코드를 확인하는 등 추가 작업 필요
- 연속된 공간을 사용하는 배열과 다양한 타입을 연결하는 연결 리스트의 장점을 모두 가짐
2) 딕셔너리
- 딕셔너리란?
- 키/값 구조로 이루어진 자료구조
- 내부적으로 Hash Table로 구현
- C++에서는 unordered_map, Java에서는 HashMap
- 숫자, 문자, 집합 등을 key로 지정
- (참고) 2021.07.12 - [개발/개발지식] - Python의 Hashable (Dictionary의 key가 되는 기준은 무엇일까?)
- Hash Table이므로, 최악의 경우 O(n)
- 그러나 Amortized Analysis에 따라 O(1)의 시간 복잡도를 가짐
(혹시 동적 배열에서 증명한 방법과 차이가 있을지?) - 딕셔너리에 대한 많은 개선이 진행됨
- Python 3.7+ : 딕셔너리 입력 순서 유지
- Python 3.6+ : 딕셔너리 메모리 사용량 20% 감소 - 딕셔너리를 효율적으로 생성하기 위한 추가모듈 지원
- collections.OrderedDict() : 항상 입력 순서가 유지
- collections.defaultdict() : 항상 디폴트 값을 생성하여 키 오류 방지
- collections.Counter() : 요소 값이 key, 개수가 value
- 딕셔너리의 활용 방법
- 선언
- a = dict()
- a = {}
- a = {1}로 선언할 경우, set으로 처리됨 (key 유무에 따라 나뉨) - 삽입
- 초기화 : a = {"a":1, "b":2}
- 별도 선언 : a["c"] = 3 - 읽기
- 인덱스 조회 : a["a"] -> 1
- 반복문 : for k, v in a.items() - 삭제
- del a["b"] - 예외
- 읽기/삭제시 없는 key일 경우 : KeyError
- try except로 사용할 시 유용함
- 선언
- 딕셔너리 모듈
- defaultdict
- 존재하지 않는 key를 조회할 경우, default 값으로 아이템 생성
>> a = collections.defaultdict(int)
>> a['A'] = 5
>> a['B'] = 4
# a -> {'A' : 5, 'B' : 4}
>> a['C'] += 1
# a -> {'A' : 5, 'B' : 4, 'C' : 1}
- 존재하지 않는 key를 조회할 경우, default 값으로 아이템 생성
- Counter
- 아이템에 대한 개수를 딕셔너리로 리턴
>> a = [1, 2, 3, 4, 5, 5, 5, 6, 6]
>> b = collections.Counter(a)
>> b
# Counter({5: 3, 6: 2, 1: 1, 2: 1, 3: 1, 4: 1}) - key=아이템 값, value=개수
- 가장 빈도수가 높은 요소 추출
>> b.most_common(2)
# [(5, 3), (6, 2)] - most_common에서 크기가 같으면 입력 순서대로 출력
- 아이템에 대한 개수를 딕셔너리로 리턴
- OrderedDict
- Python 3.7부터 딕셔너리 내부적으로 입력 순서가 유지됨
- 사실상 하위 호환성을 위해 남겨짐
- 코딩 테스트시 하위 버전의 인터프리터를 사용할 경우 필요할 수도 있음
- defaultdict
'책읽기' 카테고리의 다른 글
[파이썬 알고리즘 인터뷰][문자열] 유효한 팰린드롬 (0) | 2021.07.16 |
---|---|
[데이터 분석을 위한 SQL 레시피][1장] 빅데이터 시대에 요구되는 분석력이란? (0) | 2021.07.15 |
[파이썬 알고리즘 인터뷰] 2부 - 파이썬 (~ 4장 - 빅오, 자료형) (0) | 2021.07.09 |
[파이썬 알고리즘 인터뷰] 2부 - 파이썬 (~ 3장 - 파이썬) (0) | 2021.06.29 |
[파이썬 알고리즘 인터뷰] 1부 - 코딩 인터뷰 (0) | 2021.06.23 |