[파이썬 알고리즘 인터뷰] 2부 - 파이썬 (~ 5장 - 리스트, 딕셔너리)

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

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로 사용할 시 유용함
• 딕셔너리 모듈
  1. 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}
  2. 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에서 크기가 같으면 입력 순서대로 출력
  3. OrderedDict
     • Python 3.7부터 딕셔너리 내부적으로 입력 순서가 유지됨
     • 사실상 하위 호환성을 위해 남겨짐
     • 코딩 테스트시 하위 버전의 인터프리터를 사용할 경우 필요할 수도 있음