[DAY 4] Python: Lecture 9. Advanced Data Structure

[Lecture 9] Advanced Data Structure

우선순위 큐, 스택, 큐, linked list, 기본 값이 있는 dictionary 등 좀 더 강력한 자료구조를 사용하고 싶을 때

Stack

• FILO 구조
• 기존 list를 활용한다.
• 동적 배열이기 때문에 push와 pop이 O(1)
• append: push 연산 / pop: pop 연산

 

Queue

• FIFO 구조
• list로 구현할 수는 있지만 처음 위치에 삽입/삭제하는 경우 O(N)이 걸림
• linked list 구조를 활용해야함
  • tail에서 데이터 추가, head에서 데이터 삭제
• double linked list는 양방향으로 접근 가능한 데이터 구조 - Deque
  • 중간 random access가 어렵다.
  • head, tail에서 원하는 위치로 이동해야하므로 시간복잡도가 최악에는 O(N)이 나온다.
• Queue에서는 linked list가 유리함
  • 양쪽 끝에서 자유롭게 입출력
  • 중간 참조는 오래걸리지만 큐 구조에서는 상관X
• from collections import deque
• appendleft(): 왼쪽 삽입, O(1)
• pop(): 오른쪽 삭제, O(1)
• append(): 오른쪽 삽입, O(1)
• popleft(): 왼쪽 삭제, O(1)
• reversed(): 뒤집기, O(N)

 

Priority Queue

• min/max 함수는 O(N)이 소요된다.
• 최소/최대값을 빠르게 구하기 위해서는 이진 탐색 O(logN)을 사용할 수 있음
  • 이진 탐색은 내부를 정렬해야 함
• 내부가 항상 정렬된 자료구조?
  • 입력할 때마다 sorted O(NlogN)
  • 리스트 정렬 후 값을 중간에 삽입 삭제하면 O(N)
• 따라서 Priority Queue가 효율적이다.
  • 내부적으로는 리스트로 구현
  • 파이썬의 heap은 기본적으로 minheap
  • heap[k] ≤ heap[2k+1], heap[2k+2]
• import heapq
• heapq.heapity(queue) : 힙을 초기화 O(NlogN)
• heap[0] : heap top, 가장 작은 값 참조, min heap O(1)
• heapq.heappush(queue, value): 삽입, O(logN)
• heapq.heappop(queue): 삭제, O(logN)
• heapq.heappushpop(queue, value): push하고 pop하는 것보다 빠름
• O(N^2)일 것 같은 문제는 heapq나 분할정복을 사용하면 O(NlogN)으로 풀 수 있다.

 

Defaultdict

• 파이썬 기본 딕셔너리는 키가 없으면 에러가 발생
  • d.get(key, default) key가 없어도 에러없이 default가 나옴
• Dictionary의 기본 값을 지정 가능

from collections import defaultdict

characters = defaultdict(int) # 기본값 int() = 0
for char in text:
    characters[char] += 1 # 값이 없으면 0으로 대체 됨

Counter

• 글자, 객체의 개수를 세는 데 최적화된 데이터 구조

from collections import counter

characters = Counter(char for char in test)
# Counter(list), Counter(string)

• 딕셔너리 처럼 생성 및 관리 가능
• 일반적인 dictionary처럼 .keys(), .values() 사용 가능
• .elements()로 모든 요소 변환
• kwargs로 생성 가능

c = Counter(Korean=2, English=3)
c #({'English': 3, 'Korean': 2})

집합 연산 지원

• + : 횟수 더하기
• & : 교집합
• | : 합집합
• - : 차집합

Named Tuple

• 데이터만을 담기 위한 클래스 사용
  • 클래스 선언 및 getter 작성 필요
  • 숫자로 indexing이 불가능
  • getitem 작성 필요
  • → 귀찮다는 단점이 있음

• 튜플로 쉽게 자료구조를 만들 수는 있지만 각 인덱스가 무엇을 의미하는지 관리하기 어렵고 attribute명으로 접근이 불가능하다.
• 그래서 사용되는게 Named Tuple이다!
  • 각 튜플 원소에 이름 붙이는 것이 가능
  • 클래스가 아니라 튜플이므로 unpacking이 가능함

from collections import namedtuple

# 새로운 타입 생성
c3d = namedtuple("c3d",['x','y','z']) # 일종의 하나의 클래스처럼 사용 가능

point = c3d(10, 20, z=30)
print(point.x) # 10, attribute 이름으로 참조가능
print(point[1]) # index로도 참조 가능
print(*point) # tuple unpacking도 가능하다.

point[1] += 1# 불변타입이므로 수정은 불가능 하다.

Dataclass

• pythonic한 데이터 클래스를 위해서는 dataclasses의 dataclass 데코레이터를 활용하면 된다.

# 데이터 클래스 명시, 문법도 살짝 다름
@dataclass
class c3d:
    x: float
  y: float
  z: float = 0

    def norm(self) -> float:
        return (self.x ** 2 + self.y ** 2 **+** self.z ** 2**) ** .5**

point = c3d(10, 20, z=30)
print(point)
print(point.norm)