유용한 표준 라이브러리

• 내장함수: 기본 입출력(input(), print(), sorted()), 정렬 기능 등을 제공하는 함수
• itertools: iterator를 처리하기 위한 기능을 제공한다.
  • itertools의 순열,조합 라이브러리는 코딩테스트 중 완전탐색 알고리즘에 유용하게 사용된다.
• heap: heap 자료구조를 제공한다.
  • heap정렬과 우선순위 큐 기능 구현에 사용한다. (다익스트라 최단거리 알고리즘에 활용 된다.)
• bisect: 이진 탐색 기능을 제공한다.
• collections: deque, Counter 등의 유용한 자료구조를 제공한다.
• math: 수학과 관련된 기능을 제공한다.
  • factorial, square, GCD, 삼각함수와 같은 함수와 pi와 같은 상수를 제공

 

[내장함수]

별도의 모듈을 import할 필요 없이 사용할 수 있는 함수들을 말한다. 대표적인 것들은 다음과 같다.

 

1. iterable 객체 요소의 합 -> sum()

# sum(iterable object) : 숫자형 데이터를 담고 있는 iterable 객체를 입력으로 받아 총 합계를 반환하는 함수
data = [1, 2, 3, 4, 5]
result = sum(data)
print(result)

2. iterable 객체 최소값과 최대값 -> min(), max()

data = (3,4,2,5,1)

print(min(data))
print(max(data))

data = ("banana", "graph", "orange", "apple")

print(min(data))
print(max(data))

 

3. 문자열로 제공된 수식의 계산결과 -> eval()

result = eval("(5 - 2) * 3")
print(result) # result = 9

 

4. iterable 객체를 정렬하기 -> sorted() (sorted() 사용 방법 확인하러 가기)

리스트 정렬

5. console 입출력 함수 -> input(), print() (input() 사용 방법 확인하러 가기)

console 입출력과 형변환

 

 

 

[heapq]

heap 기능을 위한 라이브러리

코딩테스트 환경에서느 우선순위 queue를 구현할 때 PriorityQueue 대신 사용하면 성능향상을 꾀할 수 있다.

min heap이므로 데이터를 넣었다 빼는 것 만으로도 O(NlogN) 복잡도의 오름차순 정렬 가능

import heapq

def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h, value)
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

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

 

max heap이 필요한 경우 heap에 원소를 삽입하기 전에 원소의 부호를 변경 후 삽입하고 원소를 꺼낸 후에는 부호를 변경하여 결과 값으로 사용한다.

import heapq


def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h, -value)
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result


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

 

 

 

[bisect]

이진탐색 기능을 제공하는 라이브러리이다.

이진탐색 특성상 정렬된 데이터에 한해 정상 동작한다.

정렬된 리스트의 특정 범위 안의 원소 개수를 확인할 때 유용하게 사용할 수 있다.

 

1. 특정 값을 삽입할 위치 확인 - 삽입할 인덱스 번호를 반환해준다.

from bisect import bisect_left, bisect_right

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

print(bisect_left(a, x))
print(bisect_right(a, x))

 

2. 특정 범위 안에 원소 수를 확인

from bisect import bisect_left, bisect_right

def count_element_by_range(data, leftValue, rightValue):
    return bisect_right(data, rightValue) - bisect_left(data, leftValue)

list_data = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

print(count_element_by_range(list_data, 4, 8))  # 4 <= n <= 8 -> 3개
print(count_element_by_range(list_data, -1, 3)) # -1 <= n <=3 -> 6개

 

 

[itertools]

모든 경우의 수를 고려해야 할 때 사용할 라이브러리이다.

1. 순열(permutations): 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것

• 선택한 r개의 원소의 순서가 다르면 다른 것으로 간주한다.
• 집합 {A, B, C}에서 3개를 선택하여 나열한 순열은 ABC, ACB, BAC, BCA, CAB, CBA 가 된다.
• 모든 순열의 경우의 수:
  • nPr = n * (n - 1) * (n -2) * ... * (n-r-1)
  • 모든 경우의 수가 1000만 이상인 경우 시간초과 판정을 받을 수있음에 주의 한다. (모든 경우의 수 계산 결과는 완전탐색 알고리즘을 요하는 문제인지 확인하는 척도가 될 수 있겠다.)

from itertools import permutations

data = ['A', 'B', 'C']

result = list(permutations(data, 3))
print(result)

 

2. 조합(combinations): 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것

• 선택한 r개의 원소의 순서에 상관없이 동일한 원소들로 구성되어 있으면 동일한 것으로 간주한다.
• 집합 {A, B C}에서 2개를 선택하는 조합은 AB(=BA), AC(=CA), BC(=CB) 총 3개가 된다. 
• 모든 조합의 경우의 수:
  • nCr = n * (n - 1) * (n -2) * ... * (n-r-1) / r!
  • 모든 경우의 수가 1000만 이상인 경우 시간초과 판정을 받을 수 있음에 주의 한다.

from itertools import combinations

data = ['A', 'B', 'C']

result = list(combinations(data, 2))
print(result)

 

3. 중복수열 (각 요소가 정해진 수만큼 중복되어 순열을 구성함)

from itertools import product

data = ['A', 'B', 'C']

result = list(product(data, repeat=3))
print(result)

 

4. 중복조합

from itertools import combinations_with_replacement

data = ['A', 'B', 'C']

result = list(combinations_with_replacement(data, 2))
print(result)

 

 

 

[collections]

1. Counter: 워드클라우드(특정 단어가 많을 수록 강조해 주는 소프트웨어)를 구현할 때 유용하게 사용될 수 있는 라이브러리이다. Counter를 사용하면 반복가능한 객체 내부의 원소별로 객체 내에 동일한 원소가 총 몇개 있는지 확인할 수 있다.

from collections import Counter

data = ["red", "blue", "red", "green", "blue", "blue"]
counter = Counter(data)

print(counter["blue"])      # blue의 횟수 출력
print(counter["green"])     # green의 횟수 출력
print(dict(counter))        # 사전 자료형으로 변환하여 Counter 객체를 출력

2. deque:

    Queue 자료형을 구현하는데 사용한다.

    반복객체들과 같은 인덱싱, 슬라이싱 기능은 사용할 수 없지만 가장 말단의 원소들을 추가, 제거 시에 O(1) 복잡도로 작업수행이 가능하다.

from collections import deque

data_list = [2, 3, 4]
data = deque(data_list)
data.appendleft(1)		# 왼쪽 끝에 요소 추가
data.append(5)			# 오른쪽 끝에 요소 추가

print(list(data))

data.pop()			# 오른쪽 끝에 요소 제거
data.popleft()			# 왼쪽 끝에 요소 제거

print(list(data))

 

 

 

[math]

최대공약수, 팩토리얼, 제곱근 등을 구할 수 있는 함수를 제공한다.

pi와 자연상수와 같은 수학계산에 필요한 상수를 제공한다.

import math


def lcm(a, b):
    return int(a * b / math.gcd(a, b))


print(math.factorial(5))            # 팩토리얼
print(math.sqrt(7))                 # 제곱근
print(math.gcd(21, 14))             # 최대공약수
print(lcm(12, 14), end="\n\n")      # 최소공배수

print(math.pi)                      # pi
print(math.e)                       # 자연상수