출처: [이것이 취업을 위한 코딩테스트다 - 나동빈 저](https://ridibooks.com/books/443000825
배너: godori님이 만드신 배너 메이커 활용

코딩 테스트 준비 시 반드시 알아두어야 할 파이썬 라이브러리

• 내장 함수: print(), input()과 같은 기본 입출력 기능부터 sorted()와 같은 정렬 기능을 포함하는 내장 라이브러리.
• itertools: 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리. 순혈과 조합 라이브러리를 제공한다.
• heapq: 힙(Heap) 기능을 제공하는 라이브러리. 우선순위 큐 기능을 구현하기 위해 사용한다.
• bisect: 이진 탐색(Binary Search) 기능을 제공한느 라이브러리다.
• colletions: 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하는 라이브러리다.
• math: 필수적인 수학적 기능을 제공하는 라이브러리다. 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이(pi)와 같은 상수를 포함하고 있다.

내장함수

• sum(): iterable 객체가 입력으로 주어졌을 때, 모든 원소의 합을 반환한다.
  - 파이썬에서 iterable은 반복가능한 객체를 말하며, 리스트, 딕셔너리, 튜플, set 등이 해당한다.
• max(): 파라미터가 2개 이상 들어왔을 때 가장 큰 값을 반환한다.
• min(): 파라미터가 2개 이상 들어왔을 때 가장 작은 값을 반환한다.
• eval(): 수학 수식이 문자열 형식으로 들어오면 해당 수식을 계산한 결과를 반환한다.
• sorted(): iterable 객체가 들어왔을 때, 정렬된 결과를 반환한다.
  - key 속성으로 정렬 기준을 명시할 수 있고, reverse 속성으로 정렬된 결과 리스트를 뒤집을지의 여부를 정할 수 있다.

eval() 사용 예시 소스코드

result = eval("(2 + 4) * 6")
print(result)

출력

36

sorted() 사용 예시 소스코드

result = sorted([9, 3, 2, 7, 4]) # 오름차순으로 정렬
print(result)

result = sorted([9, 3, 2, 7, 4], reverse = True) # 내림차순으로 정렬
print(result)

출력

[2, 3, 4, 7, 9]

[9, 7 ,4, 3, 2]

파이썬에서 리스트의 원소로 리스트나 튜플이 존재할 때 특정한 기준에 따라서 정렬을 수행할 수 있다.
정렬 기준은 key 속성을 통해 명시한다.

key 속성 사용 예시

리스트에 튜플이 원소로 있을 때, 이를 튜플의 두 번째 원소를 기준으로 내림차순 정렬하는 예시

result = sorted([('박성재', 27), ('김프론', 33), ('이서버', 42)], key = lambda x: x[1], reverse = True)
print(result)

츌력

[('이서버', 42), ('김프론', 33), ('박성재', 27)]

리스트와 같은 iterable 객체는 기본으로 sort() 함수를 내장하고 있어서 굳이 sorted() 함수를 사용하지 않아도 정렬할 수 있다. 이 경우 리스트 객체의 내부 값이 정렬된 값으로 바로 변경된다.

sort() 함수 예시 소스코드

data = [9 ,3, 2, 5, 6]
data.sort()
print(data)

출력

[2, 3, 5, 6, 9]

itertools 라이브러리

itertools는 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리다.
제공하는 클래스는 매우 다양한지만, 코딩 테스트에서 가장 유용하게 사용할 수 있는 클래스는 다음과 같다.

• permutations: 순열
• combinations: 조합
• product: 중복 허용 순열
• combinations_with_replacement: 중복 허용 조합

모두 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하여(or 고려하지 않고) 중복을 허용하여(or 허용하지 않고) 나열하는 모든 경우를 계산한다.

• 데이터 목록과 뽑을 데이터의 개수를 인자로 넘겨준다

모두 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.

소스코드

from itertools import permutations, combinations, product, combinations_with_replacement

data = ['A', 'B', 'C'] # 데이터 준비
result = list(permutations(data, 3)) # 모든 순열 구하기
print(result)

result = list(combinations(data, 2)) #2개를 뽑는 모든 조합 구하기
print(result)

result = list(product(data, repeat=2)) # 2개를 뽑는 모든 순열 구하기(중복 허용)
print(result)

result = list(combinations_with_replacement(data, repeat=2)) # 2개를 뽑는 모든 조합 구하기(중복 허용)
print(result)

출력

#3개를 뽑는 순열
[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
#2개를 뽑는 조합
[('A', 'B'), ('A', 'C'), ('B', 'C')]
#2개를 뽑는 중복허용 순열
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
#2개를 뽑는 중복허용 조합
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

heapq 라이브러리

• 힙(Heap) 기능 제공
• 다익스트라 최단 경로 알고리즘을 비롯한 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용
• PriorityQueue 라이브러리도 사용가능하지만, 코딩 테스트 환경에서 보통 heapq가 더 빠르게 동작
• 파이썬의 힙은 최소 힙으로 구성되어 있어서 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간복잡도 O(NlogN)에 오름차순 정렬이 오나료된다. (보통 최소 힙 자료구조의 최상단 원소는 '가장 작은' 원소이기 때문)
• 힙에 원소를 삽입할 때는 heap.heappush() 메서드를 사용
• 힙에서 원소를 꺼재고자 할 때는 heap.heappop() 메서드를 사용

오름차순 힙정렬 예시 소스코드

improt heapq

def heapsort(iterable):
	h = []
    result = []
    # 모든 우너소를 차례대로 힙에 삽입
    for value in iterable:
    	heapq.push(h, vlaue)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내서 담기
   	for i in range(len(h)):
    	result.append(heapq.heappop(h))
    return result

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

출력

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

파이썬에서는 최대 힙을 제공하지 않기 때문에, heapq 라이브러리를 이용해서 최대 힙을 구현해야 할 때는 원소의 부호를 임시로 변경하는 방식을 사용한다.
힙에 원소를 삽입하기 전에 잠시 부호를 반대로 바꾸었다가, 힙에서 원소를 꺼낸 뒤에 다시 원소의 부호를 바꾸면 된다.

내림차순 힙정렬 예시 소스코드

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

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

출력

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

bisect 라이브러리

• 이진 탐색을 쉽게 구현할 수 있도록 해주는 라이브러리
• '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다.
• bisect_left()와 bisect_right() 함수가 가장 중요하게 사용되며, 이 두 함수가 동작하는 시간 복잡도는 O(logN)이다.
• bisect_left(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• bisect_right(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

예시 소스코드

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
4

위 두 함수는 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구하고자 할 때, 효과적으로 사용될 수 있다. 시간복잡도는 O(logN)이다.

활용 예시 소스코드

from bisect import bisect_left, bisect_right

# 값이 [left_vlaue, right_value] 범위에 속하는 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index
    
# 리스트 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4)

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3)

출력

2
6

collections 라이브러리

• 유용한 자료구조를 제공하는 표준 라이브러리
• 코딩 테스트에서 유용하게 사용되는 클래스는 deque와 Counter이다.

deque

• 파이썬에서는 보통 deque를 통해 큐를 구현한다.
• 리스트의 경우 맨 뒤에 원소 추가 및 제거의 시간복잡도는 O(1)이지만, 맨 앞에 원소 추가 및 제거는 O(N)이 걸린다.
• deque의 경우 맨 앞과 뒤 모두 원소를 추가하거나 제거할 때 시간복잡도가 O(1)이다.
• deque는 리스트와 다르게 인덱싱, 슬라이싱 기능은 없지만, 연속적으로 나열된 데이터의 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때는 매우 효과적이다.

deque는 데이터의 맨 앞과 맨 뒤 모두에서 삽입과 삭제가 가능하기 때문에 스택으로도 쓸 수 있고, 큐로도 쓸 수 있다.

• 큐로 사용할 때: popleft()로 맨 앞 원소 제거, append(x)로 맨 뒤에 원소 x 삽입
• 스택으로 사용할 때: pop()로 맨 뒤 원소 제거, append(x)로 맨 뒤에 원소 x 삽입
• 맨 앞에 원소 x 삽입: appendleft(x)

deque 활용 예시 소스코드

from collections import deque

data = deque([2, 3, 4])
data.appendleft(1)
data.append(5)

print(data)
print(list(data)) # 리스트 자료형으로 변환

data.popleft()
data.pop()
print(list(data))

출력

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

[1, 2, 3, 4, 5]

[2, 3, 4]

Counter

• 등장 횟수를 세는 기능 제공
• 리스트와 같은 iterable 객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지를 알려준다.
• 원소별 등장 횟수를 세는 기능이 필요할 떄 짧은 소스코드로 이를 구현할 수 있다.

Counter 활용 예시 소스코드

from collections import Counter

counter = Counter(['red', 'blue', 'red' ,'green', 'blue', 'blue'])
print(counter['red']) # 'red'가 등장한 횟수 출력
print(counter['blue']) # 'blue'가 등장한 횟수 출력
print(dict(counter)) # 딕셔너리형으로 변환

출력

2
3
{'red': 2, 'blue': 3, 'green': 1}

math 라이브러리

• 자주 사용되는 수학적인 기능을 포함하고 있는 라이브러리
• factorial(n): n!
• sqrt(x): x의 제곱근
• gcd(a, b): a와 b의 최대 공약수
• pi: 상수 파이(pi)
• e: 자연상수 e

math 활용 예시소스코드

import math

print(math.factorial(5)) # 5 팩토리얼

print(math.sqrt(6)) # 6의 제곱근 출력

print(math.gcd(35, 14))

print(math.pi)

print(math.e)

출력

120

2.449489742783178

7

3.141592653589793

2.718281828459045