[python3.10 기본] 17. 고급 데이터 구조

17.1 deque와 기타 컬렉션 (collections 모듈)

deque는 양쪽 끝에서 빠르게 추가 및 제거가 가능한 양방향 큐입니다. 이 외에도 defaultdict, namedtuple, Counter, OrderedDict 등을 제공합니다.

 

deque 사용법

from collections import deque

# deque 생성
d = deque([1, 2, 3])

# 요소 추가
d.append(4)
d.appendleft(0)
print(d)  # deque([0, 1, 2, 3, 4])

# 요소 제거
d.pop()
d.popleft()
print(d)  # deque([1, 2, 3])

defaultdict 사용법

from collections import defaultdict

# 기본값이 int인 defaultdict 생성
dd = defaultdict(int)
dd['a'] += 1
print(dd)  # defaultdict(<class 'int'>, {'a': 1})

namedtuple 사용법

from collections import namedtuple

# namedtuple 정의
Point = namedtuple('Point', ['x', 'y'])

# 인스턴스 생성
p = Point(1, 2)
print(p)  # Point(x=1, y=2)
print(p.x, p.y)  # 1 2

Counter 사용법

from collections import Counter

# Counter 생성
count = Counter('abracadabra')
print(count)  # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

OrderedDict 사용법

from collections import OrderedDict

# OrderedDict 생성
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3
print(od)  # OrderedDict([('a', 1), ('b', 2), ('c', 3)])

17.2 heapq 모듈을 사용한 힙 큐

heapq 모듈은 최소 힙 자료 구조를 제공합니다. 힙은 우선순위 큐를 구현하는 데 유용합니다.

 

힙 생성 및 요소 추가

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 2)
print(heap)  # [1, 2, 4, 3]

최소값 제거

min_element = heapq.heappop(heap)
print(min_element)  # 1
print(heap)  # [2, 3, 4]

리스트를 힙으로 변환

data = [3, 1, 4, 1, 5, 9]
heapq.heapify(data)
print(data)  # [1, 1, 4, 3, 5, 9]

17.3 bisect 모듈을 사용한 이진 검색

bisect 모듈은 정렬된 리스트를 다루는 기능을 제공합니다. 이진 검색을 통해 리스트에 요소를 효율적으로 삽입할 수 있습니다.

 

요소 삽입

import bisect

data = [1, 2, 4, 5]
bisect.insort(data, 3)
print(data)  # [1, 2, 3, 4, 5]

위치 검색

index = bisect.bisect(data, 3)
print(index)  # 3

범위 내의 요소 검색

left = bisect.bisect_left(data, 3)
right = bisect.bisect_right(data, 3)
print(left, right)  # 2 3