파이썬 코딩테스트에 자주 사용되는 파이썬 라이브러리

1. 내장함수

• sum(): iterable 객체(List, Dict, Tuple 등)의 모든 원소의 합을 반환

data = [1, 2, 3]
res = sum(data)
print(res)
>>>> 6

• min(): 파라미터가 2개 이상 들어왔을 때 가장 작은 값 반환

data = [1, 2, 3]
res = min(data)
print(res)
>>>> 1 

• max(): 파라미터가 2개 이상 들어왔을 때 가장 큰 값 반환

data = [1, 2, 3] 
res = max(data)
print(res)
>>>> 3 

• sorted(): iterable 객체가 들어왔을 때, 정렬된 결과를 반환

data = [2, 4, 5, 6, 1, 2, 10, 0]

# ASC 정렬 
sorted(data)
>>> [0,1,2,2,4,5,6,10]

# DESC 정렬 
sorted(data, reverse=True)
>>> [10,6,5,4,2,2,1,0] 

# List, Dict 정렬 
data = [{"key":4}, {"key":5}, {"key":2}, {"key":1}, {"key":3}]
sorted(data, key=lambda x: x["key"]) 
>>> [{"key":1}, {"key":2}, {"key":3}, {"key":4}, {"key":5}]

stage_dict = {1: 0.125, 2: 0.42857142857142855, 3: 0.5, 4: 0.5, 5: 0.0}
sorted(stage_dict.items(), key=lambda x: x[1], reverse=True)
>>> [(3, 0.5), (4, 0.5), (2, 0.42857142857142855), (1, 0.125), (5, 0.0)]

stage_dict = {1: 0.125, 2: 0.42857142857142855, 3: 0.5, 4: 0.5, 5: 0.0}
sorted(stage_dict, key=lambda x: stage_dict[x], reverse=True)
>>> [3, 4, 2, 1, 5]

# List, Tuple 정렬 
data = [{"A", 4}, {"B", 1}, {"C", 3}, {"D", 2}, {"E", 5}]
sorted(data, key=lambda x: x[1])
>>> [('B', 1), ('D', 2), ('A', 4), ('E', 5)]

2. itertools 함수
   : 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리

• permutations(순열): iterable 객체에서 n개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)을 계산
  특징: 순서를 고려하므로 중복이 존재

from itertools import permutations 

data = ["A", "B", "C"]
print(list(permutations(data, 3)))
>>> [('A', 'B', 'C'), 
     ('A', 'C', 'B'), 
     ('B', 'A', 'C'), 
     ('B', 'C', 'A'), 
     ('C', 'A', 'B'), 
     ('C', 'B', 'A')]

• combinations(조합): iterable 객체에서 n개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(조합)을 계산
  특징 : 순서를 고려하지 않으므로 중복이 없음

from itertools import combinations 
data = ["A", "B", "C", "D"]
print(list(combinations(data, 2)))
>>> [('A', 'B'), 
     ('A', 'C'), 
     ('A', 'D'), 
     ('B', 'C'), 
     ('B', 'D'), 
     ('C', 'D')]

• product(중복순열): permutations와 같이 iterable객체에서 n개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)를 계산
  특징: permutations에서 데이터 요소 중복을 허용한다

from itertools import product 

data = ["A", "B", "C"]
print(list(product(data, repeat=3)))
>>> [('A', 'A', 'A'), 
     ('A', 'A', 'B'), 
     ('A', 'A', 'C'), 
     ('A', 'B', 'A'), 
     ('A', 'B', 'B'), 
     ('A', 'B', 'C'), 
     ('A', 'C', 'A'), 
     ('A', 'C', 'B'), 
     ('A', 'C', 'C'), 
     ('B', 'A', 'A'), 
     ('B', 'A', 'B'), 
     ('B', 'A', 'C'), 
     ('B', 'B', 'A'), 
     ('B', 'B', 'B'), 
     ('B', 'B', 'C'), 
     ('B', 'C', 'A'), 
     ('B', 'C', 'B'), 
     ('B', 'C', 'C'), 
     ('C', 'A', 'A'), 
     ('C', 'A', 'B'), 
     ('C', 'A', 'C'), 
     ('C', 'B', 'A'), 
     ('C', 'B', 'B'), 
     ('C', 'B', 'C'), 
     ('C', 'C', 'A'), 
     ('C', 'C', 'B'), 
     ('C', 'C', 'C')]

• combinations_with_replacement(중복조합): combinations와 같이 iterable 객체에서 n개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우 (조합)을 계산
  특징: combinations에서 데이터 요소 중복 허용

from itertools import combinations_with_replacement

data = ["A", "B", "C"]
print(list(combinations_with_replacement(data, 3)))
>>> [('A', 'A', 'A'), 
     ('A', 'A', 'B'), 
     ('A', 'A', 'C'), 
     ('A', 'B', 'B'), 
     ('A', 'B', 'C'), 
     ('A', 'C', 'C'), 
     ('B', 'B', 'B'), 
     ('B', 'B', 'C'), 
     ('B', 'C', 'C'), 
     ('C', 'C', 'C')]

3. heapq
   : 파이썬에서 힙 기능을 위해 heapq 라이브러리를 제공. heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용.

import heapq 

def heap_sort_asc(iterable):
    h = []
    res = []

    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)     # 삽입하면서 자동으로 순서대로 나열됨 

    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 
    for i in range(len(h)):
        res.append(heapq.heappop(h))

    return res 

arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heap_sort_asc(arr)
>>> [0,1,2,3,4,5,6,7,8,9]

4. bisect
   : 파이썬에서 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공. "정렬된 배열"에서 특정한 원소를 찾아야할 때 매우 효과적으로 사용.

• bisect_left(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• bisect_right(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

from bisect import bisect_left, bisect_right

data = [1, 4, 5, 2, 2, 3, 19, 192, 39]
target = 2
# bisect를 하면 자동으로 오른차순 정렬이 되고 거기서 target의 index를 찾아 반환 
# [1, 2, 2, 3, 4, 5, 19, 39, 192] 
bisect_left(data, target)
>>> 1 

bisect_right(data, target)
>>> 5

응용하기 : 특정 범위에 속하는 원소의 개수 구하기

관련 문제 : 10816번: 숫자카드 2

from bisect import bisect_left, bisect_right

def calCountsByRange(nums, left_value, right_value):
    r_i = bisect_right(nums, right_value)
    l_i = bisect_left(nums, left_value)
    return r_i - l_i

nums = [-1, -3, 5, 5, 4, 7, 1, 7, 2, 5, 6]
nums.sort()
print(calCountsByRange(nums, 5, 7))    # 5부터 7까지 숫자 몇개? 
>>> 6

5. collections
   : 파이썬의 collections 라이브러리는 유용한 자료구조를 제공하는 표준 라이브러리이다.

• deque: 보통 파이썬에서 deque를 사용하여 큐 구현이 가능하며, 인덱싱, 슬라이싱 등의 기능은 사용 불가. 또한 연속적으로 나열된 데이터의 시작 부분이나 끝 부분에 데이터를 삽입하거나 삭제할 때 매우 효과적

# popleft()    : 첫 번째 원소 제거 
# pop()        : 마지막 원소 제거 
# appendleft(x): 첫 번째 인덱스에 원소 x를 삽입 
# append(x)    : 마지막 인덱스에 원소 x를 삽입 
# Q = deque(data, maxlen=n) : 큐의 사이즈를 정할 수 있다 
# 사이즈보다 더 큰 수가 들어오면 가장 먼저 삽입되었던 값은 자연스레 사라지고 
# 새롭게 들어오는 값은 가장 뒤에 삽입된다.

from collections import deque 

data = [2,3,4]
Q = deque(data)

Q.appendleft("appendleft")
Q.append('append')
print(Q)
>>> deque(['appendleft', 2, 3, 4, 'append'])

data.popleft()
data.pop()
print(data)
>>> deque([2,3,4])

data = [2,3,4]
Q = deque(data, maxlen=len(data))
Q.append(7)
print(Q)
>>> deque([3,4,7])

• Counter: iterable 객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지 카운트 결과를 Dict 형태로 반환
• 관련 문제 : 10816번: 숫자카드 2

from collections import Counter 

data = ["Apple", "Apple", "Apple", "Apple", "Apple", "Banna", "Banna", "Banna", "Banna", "Melon", "Melon"]
counter = dict(Counter(data))
print(counter)
>>> {'Apple': 5, 'Banna': 4, 'Melon': 2}

6. math
   : 자주 사용되는 수학적인 기능을 포함하고 있는 라이브러리

• factorial(x): x! 값을 반환

from math import factorial
print(factorial(3))     #    1 x 2 x 3 = 6
>>> 6

• gcd(a,b): a와 b의 최대 공약수 반환

from math import gcd
print(gcd(4,2))     
>>> 2

• lcm(a,b,...): a와 b의 최소 공배수 반환
  둘 이상의 정수의 공배수 중에서 가장 작은 것을 말함

from math import lcm
print(lcm(2))         
>>> 2

print(lcm(2, 4))         
>>> 4

print(lcm(11, 22, 66))         
>>> 66 

print(lcm(11, 22, 66, 33, 44))         
>>> 132

 

 

스트링 앞에 0을 채우는 방법 zfill, rjust 

 

zfill(width): 문자열을 오른쪽으로 width만큼 0을 채워 넣음

"2".zfill(3) # -> "002"

"5000".zfill(5) # -> "05000"

"123".zfill(5) # -> "00123"

 

rjust(width, [fillchar]): 문자열을 오른쪽으로 width만큼 c를 채워 넣음

"2".rjust(3, "0") # -> "002"

"5000".rjust(5, "0") # -> "05000"

"123".rjust(5, "a") # -> "aa123"

 

 

ljust(width, [fillchar]): 문자열을 왼쪽으로 width만큼 c를 채워 넣음

"2".ljust(3, "0") # -> "200"

"5000".ljust(5, "0") # -> "50000"

"123".ljust(5, "a") # -> "123aa"

 

import re 

import re 
str1 = 'FRANCE'
pattern = re.compile(r'[A-Z]{2}')		# A-Z까지 알파벳을 2개씩 끊어라 
print(pattern.findall(str1))
>>>
['FR', 'AN', 'CE']

# ---------------------------------

import re 

testcase = ['1S2D*3T', '1D2S#10S']
# 0부터9 그리고 10 을 구분해서, S와 D와 T를 구분해서, *와#는 입력될 수도 아닐 수도 있는데 구분
pattern = re.compile(r'([0-9]|10)([SDT])([\*\#]?)')

print(pattern.findall(testcase[0]))
print(pattern.findall(testcase[1]))
>>>
[('1', 'S', ''), ('2', 'D', '*'), ('3', 'T', '')]
[('1', 'D', ''), ('2', 'S', '#'), ('10', 'S', '')]


s = 'aabbaccc'

import re 

for i in range(1, len(s)//2+1):
    pattern = f'[a-z]{{{i}}}'       # 영문자열을 i개씩 끊어서 나눔 
    print(pattern)
    pattern = re.compile(pattern)
    print(pattern.findall(s))

>>>
[a-z]{1}
['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c']
[a-z]{2}
['aa', 'bb', 'ac', 'cc']
[a-z]{3}
['aab', 'bac']
[a-z]{4}
['aabb', 'accc']

https://brownbears.tistory.com/506

[Python] re 모듈 사용법

 

 

라이브러리, 함수 메서드가 기억안날때, 

dir()을 기억하자 

from collections import deque 

dir(deque)

 

 

any(), all() 함수 

파이썬 내장함수 중 any()와 all()이 있다. 둘은 아큐먼트로 iterable한 객체를 받는데 이 객체를 돌면서 조건을 검사해 답을 True/False의 답을 반환한다.

• any() : 하나라도 True인게 있으면 True
• all() : 모두 True여야 True 반환

쉽게 생각해 any는 or, all은 and 연산이라 보면 된다.

 

>>> any([False, False, False])
False
>>> any([False, True, False])
True
>>> all([False, True, False])
False
>>> all([True, True, True])
True

 

cur = 3
temp = [1,3,6,2]
if any(cur<num for num in temp):
	print("There exist number that is larger than 3")

 

집합

{1,2} & {2,3} ==> {2}
{1,2} | {2,3} ==> {1,2,3}
{1,2} - {2,3} ==> {1}
{1,2} ^ {2,3} ==> {1,3}

 

update()

기존 딕셔너리에 새로운 키와 값을 추가하거나 기존 값을 수정할 수 있다. 

sample_dict = {
	'수학':80,
    '국어':90
    }

sample_dict.update({'수학':95, '영어':70})
print(sample_dict)
>>> {'수학':95, '국어':90, '영어':70}

 

items(): 딕셔너리의 키, 값 쌍 얻기 

딕셔너리는 items()함수를 사용하면 딕셔너리에 있는 키와 값들의 쌍을 얻을 수 있다. 

car = {"name" : "BMW", "price" : "7000"} 
car.items() 
>>> 
dict_items([('name', 'BMW'), ('price', '7000')])

items함수를 사용하면 딕셔너리의 값을 반복할때 키와 값을 접근하기가 매우 유용해집니다.

car = {"name" : "BMW", "price" : "7000"} 
for key, val in car.items():
	print("key : {} value : {}".format(key,val)) 

>>> 
key : name value : BMW 
key : price value : 7000

 

enumerate(iterable 객체, 시작 index(default=0))

data = ['a','b','c','d','e']

for i, txt in enumerate(data):
	print(i,txt) 
>>>
(0,'a')
(1,'b') ....

for i, txt in enumerate(data, 1):
	print(i,txt) 
>>>
(1,'a')
(2,'b') ....

 

zip() : zip함수는 동일한 개수로 이루어진 자료형을 묶어주는 역할을 한다. 

A = [1,2,3]
B = [4,5,6]

for node in zip(A,B):
    print(node)
    
>>>
(1, 4)
(2, 5)
(3, 6)

# 행 요소 열 요소 바꾸기 
alist = [
    [1,2,3], 
    [4,5,6], 
    [7,8,9]]

for i in zip(*alist):
    print(i)
    
>>>
(1, 4, 7)
(2, 5, 8)
(3, 6, 9)

for i in map(list, zip(*alist)):
    print(i)

blist = list(map(list, zip(*alist)))
blist
>>> 
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

 

 

시간제한에 따른 알고리즘 설계 

500 (5백)	O(N³)
2,000 (2천)	O(N²)
100,000 (10만)	O(NlogN)
10,000,000 (천만)	O(N)

 

검색 문제, 또는 검색 효율성 문제는 Tree일 가능성이 높다