악곱 == 악성곱슬

! 파이썬의 일부 라이브러리는 잘못 사용하면 수행시간이 비효율적으로 증가한다 !

표준 라이브러리

---

표준 라이브러리란 자주 사용되는 표준 소스코드를 미리 구현해놓은 라이브러리를 말한다.

• print(), input(), sorted()등 내장 라이브러리
• itertools: 반복되는 형태를 처리하는 기능을 제공. 순열과 조합 라이브러리를 제공
• heapq: 힙 기능을 제공하는 라이브러리. 우선순위 큐를 구현하기 위해 사용
• bisect: 이진 탐색 기능을 제공
• collections: 덱(deque), 카운터(counter)등의 유용한 자료구조를 포함
• math: 팩토리얼, 제곱근, 최대공약수, 삼각함수, 파이 등

내장함수

---

li = [1, 2, 3, 4, 5]

# sum()
print(sum(li))
>>> 15

# max, min
print(max(li), min(li))
>>> 5 1

# eval
print(eval("(3 + 5) * 7"))
>>> 56

# sorted
print(sorted(li, reverse=True))  # 내림차순 정렬
>>> [5, 4, 3, 2, 1]
# key=lambda사용가능
li2 = [[0, 1], [3, 5], [2, 3]]
print(sorted(li2, key=lambda x: x[0])) # 앞 쪽 원소를 기준으로 정렬
>>> [[0, 1], [2, 3], [3, 5]]

# sort: 리스트와 같은 iterable 객체는 기본으로 sort() 메서드 내장
li.sort(reverse=True)

itertools

---

반복되는 데이터를 처리하는 기능 포함

순열(permutations)과 조합(combinations)에서 유용하게 사용

from itertools import permutations, combinations, product

data = ['A', 'B', 'C']
per = list(permutations(data, 2))  # 리스트, 개수
print(per)
>>> [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
com = list(combinations(data, 2))  # 리스트, 개수
print(com)
>>> [('A', 'B'), ('A', 'C'), ('B', 'C')]
pdt = list(product(data, repeat=2))
print(pdt)
>>> [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

복원 추출하는 경우

from itertools import combinations_with_replacement

data = ['A', 'B', 'C']
result = list(combinations_with_replacement(data, 2))
print(result)

>>> [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

heapq

---

힙 기능을 위한 라이브러리

다익스트라(Dijkstra) 최단 경로 알고리즘을 포함해서 우선순위 큐(priority queue)를 구현하고자 사용된다.

PriorityQueue라이브러리도 있지만 코테 환경에선 heapq가 더 빠르게 동작한다고 한다

파이썬의 heap은 min heap으로 구성되어 있다

원소 입출력 시간복잡도는 O(NlogN), 오름차순 정렬

import heapq

def heapsort(li):
    h = []
    result = []
    for v in li:
        # heappush 할 때 이미 min-heap 트리로 삽입하는 것
        heapq.heappush(h, v)
    for i in range(len(h)):
        # heappop 에서 top 노드를 추출(가장 작은 원소)
        result.append(heapq.heappop(h))
    return result

answer = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 10])
print(answer)
>>> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

min heap대신 max heap을 사용하고 싶다면 부호를 반대로 삽입, 반대로 추출

import heapq

def heapsort(li):
    h = []
    result = []
    for v in li:
        # heappush 할 때 부호를 반대로
        heapq.heappush(h, -v)
    for i in range(len(h)):
        # 추출할 때 부호를 반대로 해서 원상 복구
        result.append(-heapq.heappop(h))
    return result

answer = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 10])
print(answer)
>>> [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

내림차순으로 정렬 할 수 있다.

bisect

---

이진 탐색을 쉽게 구현하기 위한 라이브러리

bisect_left(), bisect_right()가 중요하게 사용된다. 시간복잡도는 O(logN)

from bisect import bisect_left, bisect_right

a = [1, 2, 3, 3, 4]
x = 3

# [1, 2, 여기, 3, 3, 4]
print(bisect_left(a, x))
>>> 2

# [1, 2, 3, 3, 여기, 4]
print(bisect_right(a, x))
>>> 4

bisect_left의 경우 삽입할 가장 왼쪽 인덱스, bisect_right의 경우 삽입할 가장 오른쪽 인덱스를 반환한다.

이 둘을 이용하여 정렬된 리스트 에서 값이 특정 범위에 속하는 원소의 개수를 구하고자 할 때, 효과적으로 사용될 수 있다.

from bisect import bisect_left, bisect_right

def count_by_range(li, lvalue, rvalue):
    r_idx = bisect_right(li, rvalue)
    l_idx = bisect_left(li, lvalue)
    return r_idx - l_idx

# [3, 4] 범위에 있는 데이터 출력
print(count_by_range([1, 2, 3, 3, 4, 4, 8, 9], 3, 4))
>>> 4

# 3 개수 출력
print(count_by_range([1, 2, 3, 3, 4, 4, 8, 9], 3, 3))
>>> 2

collections

---

보통 파이썬에서는 deque를 이용해 큐(queue)를 구현한다.

리스트 자료형은 stack처럼 작동한다. append, pop등

큐구현을 리스트 자료형으로 구현한다면 시간측면에서 손해다.

가장 앞쪽에 원소를 추가하거나 가장 앞쪽에 있는 원소를 제거하려면 O(N)이다. deque는 해당 연산들이 O(1)로 연산이 가능하다는 장점이 있다.

deque는 인덱싱, 슬라이싱의 기능은 사용할 수 없다.

deque는 큐 뿐 아니라 스택의 대응으로도 사용할 수 있다.

from collections import deque

data = deque([2, 3, 4])
data.appendleft(1)   # 앞 쪽 삽입
data.append(5)   # 뒤 쪽 삽입
print(data)
>>> deque([1, 2, 3, 4, 5])   # deque자료형이 반환된다.
print(list(data))
>>> [1, 2, 3, 4, 5]   # 리스트 자료형으로 변환하여 반환

리스트 특정 원소의 개수를 세어주는 Counter

from collections import Counter

counter = Counter(['삼전', '하닉', '삼전', '하닉', '삼전', '카카오'])
print(counter['삼전'])
>>> 3
print(counter['하닉'])
>>> 2
print(dict(counter))
>>> {'삼전': 3, '하닉': 2, '카카오': 1}

math

---

팩토리얼, 제곱근, 최대공약수 등을 계산해주는 기능을 포함

import math

print(math.factorial(5))   # 팩토리알
>>> 120
print(math.sqrt(7))        # 루트
>>> 2.6457513110645907
print(math.gcd(21, 14))    # 최대공약수
>>> 7
print(math.pi)             # 파이
>>> 3.141592653589793
print(math.e)              # 자연상수 e
>>> 2.718281828459045