표준 라이브러리

다히·2023년 1월 11일
Dequebisectcollectionscounterheapqitertoolsmathpython
0

Python

목록 보기
1/3

: itertools, heapq, bisect, collections, math

💡 파이썬 공식 문서

라이브러리설명
내장 함수기본 입출력 기능부터 정렬 기능(sorted())을 포함하고 있는 기본 내장 라이브러리
itertools반복되는 형태의 데이터 처리하는 기능을 제공하는 라이브러리
순열과 조합 라이브러리 제공
heapq우선순위 큐 구현에 사용
bisect이진 탐색 기능 제공
collectionsdeque, Counter 등의 자료구조 포함하는 라이브러리
math필수적인 수학적 기능 제공

내장 함수 Built-in functions

  • import 명령어 없이 사용 가능
  • input(), print(), sum(), min(), max(), eval(), sorted(), sort() 등

eval()

  • 문자열 형식의 수식을 인자로 받아, 수식을 계산한 결과를 반환
    result = eval("(3 + 5) * 7)
print(result)

sorted()

  • key 속성을 이용해서 정렬 가능 & reverse 속성 부여 가능
  • 리스트와 같은 iterable 객체는 sort() 메서드가 내장되어 있어서 sorted 사용할 필요 없음
    result = sorted(iterable 객체, key=lambda x: x[2], reverse = True)

itertools

  • 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리
  • from itertools import ___

permutations

  • iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산

  • permutations는 클래스이기 때문에, 객체 초기화 이후에는 리스트로 변환해서 사용

    from itertools import permutations
array =  ['a', 'b', 'c']
result = list(permutations(array, r))
# [('a', 'b'), ('a', 'c'), ('b', 'a'), (’b’, ‘c’), (’c’, ‘a’), (’c’, ‘b’)]

combinations

  • iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우를 계산

    from itertools import combinations
array =  ['a', 'b', 'c']
result = list(combinations(array, r))
# [('a', 'b'), ('a', 'c'), ('b', 'c')]

product

  • permutations 복원추출 ver.

    from itertools import product
array = ['a', 'b', 'c']
result = list(product(array, repeat = 2)) 
# 생략 ( 3^2 개 생성 )

  • repeat 속성: 중복 허용

  • repeat을 써주지 않으면 TypeError: 'int' object is not iterable 발생

combinations_with_replacement

  • combinations 복원 추출 ver.

    from itertools import combinations_with_replacement
array = ['a', 'b', 'c']
result = list(combinations_with_replacement(array, 2))
# [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]

heapq

  • 힙 기능을 위한 표준 라이브러리

  • 다익스트라 최단 경로 알고리즘 등 우선 순위 큐 기능을 구현할 때 사용

  • 코딩테스트 환경에서는 heapq가 PriorityQueue 라이브러리보다 빠르게 작동

    import heapq
heap = []  # 빈 리스트를 사용
heapq.heappush(heap, value)  # 원소 삽입
heapq.heappop(heap)  # 원소 삭제

힙 정렬(heap sort)

  • max heap이나 min heap 트리를 이용한 정렬 방식
  • 내림차순 정렬: max heap, 오름차순 정렬: min heap
  • 힙의 길이: len(heap)

오름차순 정렬 : 최소 힙(Min heap)

  • 파이썬에는 최소 힙(Min Heap)이 구현되어 있기 때문에 원소를 힙에 전부 삽입했다가 제거함으로써 오름차순으로 정렬 가능 ⇒ O(NlogN)
  • 최소 힙 사용해서 저장 → 저장 값 중 최솟값이 0번 인덱스, 즉 이진트리 루트에 위치
  1. 모든 원소를 차례대로 heap에 삽입 heapq.heappush(heap, value)
  2. 힙에 삽입된 모든 원소를 차례대로 result에 담음
    heapq.heappop(heap) 하면 힙의 루트 원소, 즉 최솟값이 pop됨
def heapsort(iterable):
    heap = []
    result = []
    for value in iterable:
        heapq.heappush(heap, value)  # 모든 원소 힙에 넣고
    for i in range(len(heap)):
        result.append(heapq.heappop(heap))  # 차례로 꺼내서 결과 저장
    return result

내림차순 정렬 : 최대 힙(Max heap)

  • 파이썬에는 최대 힙(Max Heap)이 구현되어 있지 않기 때문에 내림차순 정렬을 위해서는 부호를 바꾼 뒤 최소 힙을 이용하여 정렬하고 다시 부호를 바꿔주어야 함
def heapsort(iterable):
    heap = []
    result = []
    for value in iterable:
        heapq.heappush(heap, **-value**)
    for i in range(len(heap)):
        result.append(**-heapq.heappop(heap)**)
    return result
  • 입력 가속 tip: N = int(sys.stdin.readline()) * -1

주의사항

  • 최솟값을 삭제하기 않고 접근하는 방법은 heap[0]
  • 그러나 heap[1] 이나 heap[2] 그 다음으로 작은 수가 있다고 보장할 수 없음
  • 힙은 heappop() 함수로 원소 삭제할 때마다 이진 트리 재배치 → 새로운 최솟값을 인덱스 0에 위치시키는 것!
  • 두 번째로 작은 원소를 얻으려면 heappop()으로heap[0]을 제거한 뒤에 다시 heap[0]에 접근해야 함

기존 리스트를 힙으로 반환

  • heapq 모듈의 heapify() 함수 사용
  • heapify()로 리스트 넘기면, 리스트 내부 원소들이 힙 구조에 맞게 재배치 → 최솟값이 0번째 인덱스에 위치됨
  • 즉, 빈 리스트 생성 후 heappush()로 원소 하나씩 추가한 효과
    ⇒ O(N)의 시간 복잡도
  • 주의: 새 리스트를 반환하는 것이 아니라 인자로 넘긴 리스트에 직접 변경
    ⇒ 원본 리스트 보존 위해서는, 반드시 해당 리스트를 복제하 후에 인자로 넘기기
    import heapq
heap = [4, 5, 1, 2]  
heapq.heapify(heap)
# [1, 2, 4, 5]

우선순위 큐

  • 데이터를 정렬된 상태로 저장하기 위해서 사용
  • 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 자료구조
  • 내부적으로 데이터 정렬된 상태로 보관하는 메커니즘이 heapq 모듈로 구현되어 있음
  • put, get 함수 ⇒ O(logN)
    from queue import PriorityQueue
queue = PriorityQueue()  # default size는 무한대, maxsize 인자로 사이즈 지정 가능
queue.put(value)  # 원소 삽입
queue.get()  # 원소 제거
# [1, 2, 4, 5]
  • 다른 기준으로 원소 정렬 원할 때는 (우선순위, 값)의 튜플 형태로 데이터 추가 및 제거
    queue.put((3, 'A'))
queue.put((1, 'B'))
queue.put((2, 'C'))
print(queue.get()[1])  # B
print(queue.get()[1])  # C
print(queue.get()[1])  # A

bisect

이진 탐색(Binary Search) 기능을 제공하는 표준 라이브러리

  • 정렬된 배열에서 특정한 원소 찾아야 할 때

bisect_left(a, x) : 정렬된 순서를 유지하면서, 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스 찾기
bisect_right(a, x): 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스 찾기
⇒ 시간 복잡도 O(logN)

예제1 : 값이 특정 범위에 속하는 원소의 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
	right_idx = bisect_right(a, right_value)
	left_idx = bisect_left(a, left_value)
	return right_idx - left_idx 

a = [1, 2, 3, 3, 3, 5, 5, 7]
print(count_by_range(a, 3, 3))  # 3의 개수 -> 3

collections

deque, Counter 등 유용한 자료구조를 제공하는 표준 라이브러리

deque

  • 파이썬에서 큐를 구현할 때 이용
  • 스택의 기능도 有 → 스택 대용도 가능, 시간 초과 안 나려면 deque 쓰셈
  • 리스트와 다르게, 인덱싱과 슬라이싱이 불가능
  • 시작 또는 끝 부분에 데이터를 삽입 및 삭제할 때 효과적
from collections import deque
a = deque([1, 2, 3, .. ])

deque 메서드

  • pop() : 마지막 원소를 제거한 뒤 반환
  • popleft() : 첫 번째 원소를 제거한 뒤 반환
  • append(x) : deque 오른쪽에 x 삽입
  • appendleft(x) : deque 왼쪽에 x 삽입
  • clear() : deque의 모든 원소를 제거
  • copy() : deque의 shallow copy를 생성
  • count(x) : x와 같은 deque element의 수 계산
  • rotate(r) : r만큼 회전, r이 음수이면 좌측으로 회전
  • len(deq) : 덱의 길이
  • max(deq) : 덱의 최댓값

추가: deque.rotate()

deq = deque([1, 2, 3, 4, 5])

deq.rotate(1)  # deque([5, 1, 2, 3, 4])
deq.rotate(-1)  # deque([1, 2, 3, 4, 5])
deq.rotate(-1)  # deque([2, 3, 4])

추가: 덱끼리의 연결

  • deque을 연결하는 방법 비교: append vs extend vs +
d1 = deque([5, 6, 7, 8])
d2 = deque([1, 2, 3, 4])
d1.appendleft(d2)
# deque([deque([1, 2, 3, 4]), 5, 6, 7, 8])

d1.extend(d2)
# deque([5, 6, 7, 8, 1, 2, 3, 4])

d1.extendleft(d2)
# deque([4, 3, 2, 1, 5, 6, 7, 8])

d2 = deque([1, 2, 3, 4])
# deque([1, 2, 3, 4, 5, 6, 7, 8])

  • deque에다가 deque을 append() 하면 deque() object 자체가 들어감

  • 연결하고 싶을 때는 extend() 또는 + 를 쓸 수 있는데,

  • extend()를 쓰면 d1.extendleft(d2)에서 d2의 첫 원소부터 차례로 d1의 왼쪽에 들어가게 되므로 d2의 순서가 뒤바뀐 채 들어감

  • 두 deque을 단순 연결하고 싶으면, 앞에 올 deque + 뒤에 올 deque 을 사용하면 됨


Counter

  • 리스트 등 iterable 객체가 주어졌을 때 해당 객체 내부의 원소가 몇 번 등장했는지
  • 최빈값 : Counter(arr).most_common()
    ⇒ 리스트 안에 (원소, 빈도수) 튜플이 빈도수 내림차순으로 저장됨
from collections import Counter

counter = Counter(['a', 'b', 'a', 'c', 'b', 'b', 'a', 'b'])
print(counter)  # Counter({'b': 4, 'a': 3, 'c': 1})
print(dict(counter)  # {'b': 4, 'a': 3, 'c': 1}

math

자주 사용되는 수학적인 기능을 포함하고 있는 표준 라이브러리

  • math.factorial(x) : x! 반환
  • math.sqrt(x) : 제곱근 반환
  • math.gcd(a, b) : 최대 공약수 반환






Source

profile
다히
다음 포스트

입출력

0개의 댓글