리스트, 딕셔너리¶

리스트¶

리스트 : 입력순서가 유지되며, 내부적으로 동적 배열로 구현되어 있는 순서대로 저장하는 시퀀스이자 변경가능한 목록

파이썬 : list()
C++ : std::vector
자바 : ArrayList

• len(a) : O(1)
• a[i] : O(1)
• a[i:j]: O(k)
• elem in a : : O(n)
• a.count(elem) : O(n)
• a.index(elem) : O(n)
• a.append(elem): O(1)
• a.pop() : O(1)
• a.pop(0) : O(n) -> deque 권장
• del a[i] : O(n)
• a.sort() : O(nlogn) -> Timsort
• min(a), max(a) : O(n)
• a.reverse() : : O(n)

딕셔너리¶

파이썬 3.7+ 에서는 입력 순서가 유지되며 내부적으로는 해시 테이블로 구현되어 있다.

파이썬 : dict()
C++ : std::unordered_map
자바 : HashMap

• len(a) : O(1)
• a[key] : O(1)
• a[key] = value : O(1)
• key in a : O(1)

파이썬 3.7+: 딕셔너리 입력 순서 유지 파이썬 3.6+: 딕셔너리 메모리 사용량 20% 감소

3.6이하에서는 입력 순서가 유지되는 collection.OrderDict()을 사용한다.

요소의 값을 키로 하고 개수를 값 형태로 만들어 카운팅하는 collections.Counter() 등이 있다.

defaultdict¶

존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해준다.

Counter¶

아이템에 대한 개수를 계산해 딕셔너리로 리턴하며, 다음과 같이 사용한다.

OrderedDict¶

3.6 이하에서 사용하는 순서가 유지되는 딕셔너리