리스트
- 가변 자료형 + 순서 유지
- 동적 배열
- C ++ : std::vector
- 자바 : ArrayList
- 파이썬 리스트를 사용하면 stack을 사용할 지, queue를 사용할 지 고민할 필요 없다! 리스트에서 다 할 수 있다.
- 리스트에서 첫 번째 요소 꺼내는 데 O(n) (전체복사가 필요하므로)-> deque 활용하여 성능 개선 가능하다.
- 리스트에서 sort -> timsort 사용하여 O(nlogn)
- 리스트 기능
- append
- indexing
- slicing
- del (index 활용하여 제거)
- remove (value 활용하여 제거)
- pop
- ...
- 리스트 특징
- 객체를 가리키는 포인터들이 연속된 메모리 공간에 존재
- 각 객체는 불연속된 메모리 공간에 존재
- -> 배열과 연결 리스트의 장점을 취할 수 있다!
- 탐색 시, 포인터의 위치를 찾아가서 값을 비교해야 하므로 속도가 느리다는 단점이 있다.
딕셔너리
- 키, 값 구조로 이루어진 자료구조
- 입력순서가 유지 (파이썬 3.7 이상부터)
- 그 이하인 경우 collections.OrderedDict 를 사용
- collections.Counter() : 요소의 값을 key로 하고, 그 개수를 value로 만들어준다
- 내부적으로는 해쉬 테이블로 구현
- C++ : std::unordered_map
- 키 조회 성능 : O(1)
- 키 삽입 성능 : O(1)
- 키 리턴 성능 : O(1)
- 딕셔너리 기능
- key in dict
- items() -> key, value
- del dict[key]
- collections.defaultdict()
- 존재하지 않는 키를 조회할 경우, 에러를 발생하는 대신 디폴트 값을 기준으로 해당 키에 대한 아이템을 생성
- collections.Counter()
- 아이템에 대한 개수를 계산하여 딕셔너리로 리턴
- key - 아이템의 value
- value - 아이템의 개수
- most_common()을 사용하여 빈도가 높은 key를 추출할 수 있다.
- collections.OrderedDict()
- 입력순서가 유지되는 딕셔너리
- 파이썬 3.7 이상의 버전부터는 기본 딕셔너리에서도 입력 순서가 유지된다.