이것이 취업을 위한 코딩테스트다 with 파이썬
파이썬의 일부 라이브러리는 잘못 사용하면 수행 시간이 비효율적으로 증가하므로 문법과 유의점을 잘 기억해두자.
표준 라이브러리 : 특정 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리
코테에서는 표준 라이브러리를 사용할 수 있도록 허용하므로 표준 라이브러리를 사용하면 소스코드 작성량에 대한 부담을 줄일 수 있다.
C++ 의 STL 와 같이, 파이썬에서는 파이썬 표준 라이브러리를 이용할 수 있다.
필요한 기능이 있다면 찾아서 아래의 공식 문서에서 찾아서 사용하는 습관을 기르자.
https://docs.python.org/ko/3/library/index.html
The Python Standard Library
While The Python Language Reference describes the exact syntax and semantics of the Python language, this library reference manual describes the standard library that is distributed with Python. It...
docs.python.org
파이썬에서 지원하는 표준 라이브러리는 굉장히 다양하지만,
코테에서 반드시 알아야 하는 라이브러리는 6가지 정도이다.
- 내장 함수 : print(), input() 과 같은 기본 입출력 기능, sorted()와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리
- itertools : 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리 - 순열, 조합 라이브러리
- heapq: 힙(Heap) 기능 제공하는 라이브러리 - 우선순위 큐 기능 구현
- bisect : 이진 탐색(Binary Search) 기능 제공 라이브러리
- collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하는 라이브러리
- math : 필수 수학적 기능 제공 라이브러리 - 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수, 파이(pi)와 같은 상수 등
내장 함수
별도의 import 명령어 없이 바로 사용할 수 있는 내장 함수
가장 대표적으로는 input(), print()
sum()
리스트와 같은 iterable 객체 (반복 가능한 - 리스트, 사전 자료형, 튜플 자료형 등) 가 입력으로 주어졌을 때
모든 원소의 합을 반환함.
result = sum([1, 2, 3, 4, 5])
print(result) # 15
min(), max()
result1 = min(7, 3, 5, 2) # 2
result2 = max(7, 3, 5, 2) # 7
eval()
수학 수식이 문자열 형식으로 들어오면 해당 수식 계산 결과를 반환
result = eval("(3 + 5)" * 7")
print(result) # 56
sorted()
iterable 객체가 들어왔을 때 정렬된 결과를 반환
key 속성으로 정렬 기준을 명시할 수 있음.
reverse 속성으로 정렬된 결과 리스트를 뒤집을지의 여부를 설정할 수 있음.
result = sorted([9, 1, 8, 5, 4]) # 오름차순으로 정렬
result = sorted([9, 1, 8, 5, 4], reverse = True) # 내림차순으로 정렬
리스트의 원소로 리스트나 튜플이 존재할 때, key 속성을 명시하여 특정한 기준에 따라서 정렬을 수행할 수 있다.
원소를 튜플의 두 번째 원소(수)를 기준으로 내림차순으로 정렬하는 예시는 아래와 같다.
result = sorted([('홍길동', 35), ('이순신', 75), ('아무개', 50)], key = lambda x: x[1], reverse = True)
print(result) # [ ('이순신', 75), ('아무개', 50), ('홍길동', 35)]
리스트와 같은 iterable 객체는 기본으로 sort() 함수를 내장하고 있어서
굳이 sorted() 함수를 사용하지 않고도 sort() 함수를 사용해서 정렬할 수 있다.
이 경우 리스트 객체의 내부 값이 정렬된 값으로 바로 반영된다.
data = [9, 1, 8, 5, 4]
data.sort()
print(data)
itertools
반복되는 데이터를 처리하는 기능을 포함하는 라이브러리다.
제공하는 다양한 클래스 중, 코테에서 가장 유용하게 사용하는 클래스는 permutations, combinations이다.
permutations
리스트와 같은 iterable객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)을 계산해준다.
permutations는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.
from itertools import permutations
data = ['A', 'B', 'C'] # 데이터 준비
result = list(permutations(data, 3)) # 모든 순열 구하기
print(result) #[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
combinations
리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(조합)를 계산한다.
combinations는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.
from itertools import combinations
data = ['A', 'B', 'C'] # 데이터 준비
result = list(combinations(data, 2)) # 2개를 뽑는 모든 조합 구하기
print(result) #[('A', 'B'), ('A', 'C'), ('B', 'C')]product
permutations 같이 리스트와 같은 iterable 객체에서 r개 뽑는 순열 계산, 다만 원소를 중복해서 뽑음
product 객체를 초기화할 때는 뽑고자 하는 데이터의 수를 repeat 속성값으로 넣어줌.
product는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.
from itertools import product
data = ['A', 'B', 'C'] # 데이터 준비
result = list(product(data, repeat=2)) # 2개 뽑는 모든 순열, 중복 허용
print(result) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
combinations_with_replacement
combinations와 같이 조합, 단 중복 허용
from itertools import combinations_with_replacement
data = ['A', 'B', 'C'] # 데이터 준비
result = list(combinations_with_replacement(data, 2)) # 2개를 뽑는 모든 조합 생성
print(result) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]
heapq
힙 기능을 위해 heapq 라이브러리 제공
다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용함
heapq 외에도 PriorityQueue 라이브러리를 사용할 수 있지만, 코딩테스트 환경에서는 보통 heapq가 더 빠르게 동작하므로 이걸 사용하길 추천.
파이썬의 힙은 최서 힙(Min Heap)으로 되어있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료됨.
보통 최소 힙 자료구조의 최상단 원소는 항상 '가장 작은' 원소이기 때문
힙에 원소를 삽입할 때는 heapq.heappush()
힙에서 원소를 꺼내고자 할 떄는 heapq.heappop()
힙 정렬을 heapq로 구현하는 예제
import heapq
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for _ 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]
파이썬에서는 최대 힙(Max Heap)을 제공하지 않는다.
따라서 heapq 라이브러리를 이용하여 최대 힙을 구현해야 할 때는 원소의 부호를 임시로 변경하는 방식을 사용한다.
힙에 원소를 삽입하기 전에 잠시 부호를 반대로 바꾸었다가, 힙에서 원소를 꺼낸 뒤에 다시 원소의 부호를 바꾸면 된다.
import heapq
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, -value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for _ 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 라이브러리에서 아래의 두 함수가 가장 중요하게 사용되며, 시간 복잡도 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)) # 2
print(bisect_right(a, x)) # 4
bisect_left()와 bisect_right() 함수는 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구하고자 할 때, 효과적으로 사용될 수 있다.
아래의 count_by_range(a, left_value, right_value) 함수 -> 정렬된 리스트에서 값이 [left_value, right_value] 에 속하는 데이터의 개수를 반환한다.
원소의 값을 x 라고 할 때 left_value ≤ x ≤ right_value 인 원소의 개수를 O(logN)으로 빠르게 계산할 수 있다.
from bisect import bisect_left, bisect_right
# 값이 [left_value, 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))
collections
collections 라이브러리 기능 중 코테에서 유용하게 사용되는 클래스는 deque와 Counter이다.
deque
파이썬에서는 deque를 사용해 큐를 구현한다.
별도로 제공되는 Queue 라이브러리가 있는데 일반적인 큐 자료구조를 구현하는 라이브러리는 아니다.
따라서 deque를 이용해 큐를 구현해야 한다는 걸 기억하자.
기본 리스트 자료형은 append()나 pop()메소드 실행 시 '가장 뒤쪽 원소'를 기준으로 수행된다.
따라서 앞쪽에 있는 원소를 처리할 때는 리스트에 포함된 데이터의 개수에 따라 많은 시간이 소요될 수 있다.
| 리스트 | deque | |
| 가장 앞쪽에 원소 추가 | O(N) | O(1) |
| 가장 뒤쪽에 원소 추가 | O(1) | O(1) |
| 가장 앞쪽에 있는 원소 제거 | O(N) | O(1) |
| 가장 뒤쪽에 있는 원소 제거 | O(1) | O(1) |
deque는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능을 사용할 수 없다.
다만, 연속적으로 나열된 데이터의 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때 매우 효과적으로 사용할 수 있다.
deque는 스택이나 큐의 기능을 모두 포함한다고도 볼 수 있기 때문에 스택 혹은 큐 자료구조의 대용으로 사용될 수 있다.
deque는 첫 번째 원소를 제거할 때 popleft()를 사용하며, 마지막 원소를 제거할 때 pop()을 사용한다.
또한 첫 번째 인덱스에 원소 x를 삽입할 때 appendleft(x)를 사용하며, 마지막 인덱스에 원소를 삽입할 때 append(x)를 사용한다.
따라서 deque를 큐 자료구조로 이용할 때, 원소를 삽입할 때에는 append()를 사용하고
원소를 삭제할 때는 popleft()를 사용하면 된다. 이러면 먼저 들어온 원소가 항상 먼저 나가게 된다.
from collections import deque
data = deque([2, 3, 4])
data.appendleft(1)
data.append(5)
print(data) # deque([1, 2, 3, 4, 5])
print(list(data)) # 리스트 자료형으로 변환, 출력: [1, 2, 3, 4, 5]
Counter
collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공한다.
구체적으로 리스트와 같은 iterable 객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지를 알려준다.
따라서 원소별 등장 횟수를 세는 기능이 필요할 때 짧은 소스코드로 이를 구현할 수 있다.
from collections import Counter
counter = Counter('red', 'blue', 'red', 'green', 'blue'])
print(counter['blue']) #'blue'가 등장한 횟수 출력
print(dict(counter)) #사전 자료형으로 변환, 출력: {'red': 2, 'blue': 2, 'green': 1}
math
팩토리얼, 제곱근, 최대공약수(GCD) 등을 계산해주는 기능을 포함하고 있으므로,
수학 계산을 요구하는 문제를 만났을 때 효과적으로 사용될 수 있다.
import math
print(math.factorial(5)) # 5 팩토리얼 출력
print(math.sqrt(16)) # 16의 제곱근을 출력
print(math.gdc(21, 14)) #최대 공약수
print(math.pi) # 파이(pi) 출력
print(math.e) # 자연상수 e 출력
이것이 취업을 위한 코딩테스트다 with 파이썬
파이썬의 일부 라이브러리는 잘못 사용하면 수행 시간이 비효율적으로 증가하므로 문법과 유의점을 잘 기억해두자.
표준 라이브러리 : 특정 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리
코테에서는 표준 라이브러리를 사용할 수 있도록 허용하므로 표준 라이브러리를 사용하면 소스코드 작성량에 대한 부담을 줄일 수 있다.
C++ 의 STL 와 같이, 파이썬에서는 파이썬 표준 라이브러리를 이용할 수 있다.
필요한 기능이 있다면 찾아서 아래의 공식 문서에서 찾아서 사용하는 습관을 기르자.
https://docs.python.org/ko/3/library/index.html
The Python Standard Library
While The Python Language Reference describes the exact syntax and semantics of the Python language, this library reference manual describes the standard library that is distributed with Python. It...
docs.python.org
파이썬에서 지원하는 표준 라이브러리는 굉장히 다양하지만,
코테에서 반드시 알아야 하는 라이브러리는 6가지 정도이다.
- 내장 함수 : print(), input() 과 같은 기본 입출력 기능, sorted()와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리
- itertools : 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리 - 순열, 조합 라이브러리
- heapq: 힙(Heap) 기능 제공하는 라이브러리 - 우선순위 큐 기능 구현
- bisect : 이진 탐색(Binary Search) 기능 제공 라이브러리
- collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하는 라이브러리
- math : 필수 수학적 기능 제공 라이브러리 - 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수, 파이(pi)와 같은 상수 등
내장 함수
별도의 import 명령어 없이 바로 사용할 수 있는 내장 함수
가장 대표적으로는 input(), print()
sum()
리스트와 같은 iterable 객체 (반복 가능한 - 리스트, 사전 자료형, 튜플 자료형 등) 가 입력으로 주어졌을 때
모든 원소의 합을 반환함.
result = sum([1, 2, 3, 4, 5])
print(result) # 15
min(), max()
result1 = min(7, 3, 5, 2) # 2
result2 = max(7, 3, 5, 2) # 7
eval()
수학 수식이 문자열 형식으로 들어오면 해당 수식 계산 결과를 반환
result = eval("(3 + 5)" * 7")
print(result) # 56
sorted()
iterable 객체가 들어왔을 때 정렬된 결과를 반환
key 속성으로 정렬 기준을 명시할 수 있음.
reverse 속성으로 정렬된 결과 리스트를 뒤집을지의 여부를 설정할 수 있음.
result = sorted([9, 1, 8, 5, 4]) # 오름차순으로 정렬
result = sorted([9, 1, 8, 5, 4], reverse = True) # 내림차순으로 정렬
리스트의 원소로 리스트나 튜플이 존재할 때, key 속성을 명시하여 특정한 기준에 따라서 정렬을 수행할 수 있다.
원소를 튜플의 두 번째 원소(수)를 기준으로 내림차순으로 정렬하는 예시는 아래와 같다.
result = sorted([('홍길동', 35), ('이순신', 75), ('아무개', 50)], key = lambda x: x[1], reverse = True)
print(result) # [ ('이순신', 75), ('아무개', 50), ('홍길동', 35)]
리스트와 같은 iterable 객체는 기본으로 sort() 함수를 내장하고 있어서
굳이 sorted() 함수를 사용하지 않고도 sort() 함수를 사용해서 정렬할 수 있다.
이 경우 리스트 객체의 내부 값이 정렬된 값으로 바로 반영된다.
data = [9, 1, 8, 5, 4]
data.sort()
print(data)
itertools
반복되는 데이터를 처리하는 기능을 포함하는 라이브러리다.
제공하는 다양한 클래스 중, 코테에서 가장 유용하게 사용하는 클래스는 permutations, combinations이다.
permutations
리스트와 같은 iterable객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)을 계산해준다.
permutations는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.
from itertools import permutations
data = ['A', 'B', 'C'] # 데이터 준비
result = list(permutations(data, 3)) # 모든 순열 구하기
print(result) #[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
combinations
리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(조합)를 계산한다.
combinations는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.
from itertools import combinations
data = ['A', 'B', 'C'] # 데이터 준비
result = list(combinations(data, 2)) # 2개를 뽑는 모든 조합 구하기
print(result) #[('A', 'B'), ('A', 'C'), ('B', 'C')]product
permutations 같이 리스트와 같은 iterable 객체에서 r개 뽑는 순열 계산, 다만 원소를 중복해서 뽑음
product 객체를 초기화할 때는 뽑고자 하는 데이터의 수를 repeat 속성값으로 넣어줌.
product는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.
from itertools import product
data = ['A', 'B', 'C'] # 데이터 준비
result = list(product(data, repeat=2)) # 2개 뽑는 모든 순열, 중복 허용
print(result) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
combinations_with_replacement
combinations와 같이 조합, 단 중복 허용
from itertools import combinations_with_replacement
data = ['A', 'B', 'C'] # 데이터 준비
result = list(combinations_with_replacement(data, 2)) # 2개를 뽑는 모든 조합 생성
print(result) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]
heapq
힙 기능을 위해 heapq 라이브러리 제공
다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용함
heapq 외에도 PriorityQueue 라이브러리를 사용할 수 있지만, 코딩테스트 환경에서는 보통 heapq가 더 빠르게 동작하므로 이걸 사용하길 추천.
파이썬의 힙은 최서 힙(Min Heap)으로 되어있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료됨.
보통 최소 힙 자료구조의 최상단 원소는 항상 '가장 작은' 원소이기 때문
힙에 원소를 삽입할 때는 heapq.heappush()
힙에서 원소를 꺼내고자 할 떄는 heapq.heappop()
힙 정렬을 heapq로 구현하는 예제
import heapq
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for _ 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]
파이썬에서는 최대 힙(Max Heap)을 제공하지 않는다.
따라서 heapq 라이브러리를 이용하여 최대 힙을 구현해야 할 때는 원소의 부호를 임시로 변경하는 방식을 사용한다.
힙에 원소를 삽입하기 전에 잠시 부호를 반대로 바꾸었다가, 힙에서 원소를 꺼낸 뒤에 다시 원소의 부호를 바꾸면 된다.
import heapq
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, -value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for _ 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 라이브러리에서 아래의 두 함수가 가장 중요하게 사용되며, 시간 복잡도 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)) # 2
print(bisect_right(a, x)) # 4
bisect_left()와 bisect_right() 함수는 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구하고자 할 때, 효과적으로 사용될 수 있다.
아래의 count_by_range(a, left_value, right_value) 함수 -> 정렬된 리스트에서 값이 [left_value, right_value] 에 속하는 데이터의 개수를 반환한다.
원소의 값을 x 라고 할 때 left_value ≤ x ≤ right_value 인 원소의 개수를 O(logN)으로 빠르게 계산할 수 있다.
from bisect import bisect_left, bisect_right
# 값이 [left_value, 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))
collections
collections 라이브러리 기능 중 코테에서 유용하게 사용되는 클래스는 deque와 Counter이다.
deque
파이썬에서는 deque를 사용해 큐를 구현한다.
별도로 제공되는 Queue 라이브러리가 있는데 일반적인 큐 자료구조를 구현하는 라이브러리는 아니다.
따라서 deque를 이용해 큐를 구현해야 한다는 걸 기억하자.
기본 리스트 자료형은 append()나 pop()메소드 실행 시 '가장 뒤쪽 원소'를 기준으로 수행된다.
따라서 앞쪽에 있는 원소를 처리할 때는 리스트에 포함된 데이터의 개수에 따라 많은 시간이 소요될 수 있다.
| 리스트 | deque | |
| 가장 앞쪽에 원소 추가 | O(N) | O(1) |
| 가장 뒤쪽에 원소 추가 | O(1) | O(1) |
| 가장 앞쪽에 있는 원소 제거 | O(N) | O(1) |
| 가장 뒤쪽에 있는 원소 제거 | O(1) | O(1) |
deque는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능을 사용할 수 없다.
다만, 연속적으로 나열된 데이터의 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때 매우 효과적으로 사용할 수 있다.
deque는 스택이나 큐의 기능을 모두 포함한다고도 볼 수 있기 때문에 스택 혹은 큐 자료구조의 대용으로 사용될 수 있다.
deque는 첫 번째 원소를 제거할 때 popleft()를 사용하며, 마지막 원소를 제거할 때 pop()을 사용한다.
또한 첫 번째 인덱스에 원소 x를 삽입할 때 appendleft(x)를 사용하며, 마지막 인덱스에 원소를 삽입할 때 append(x)를 사용한다.
따라서 deque를 큐 자료구조로 이용할 때, 원소를 삽입할 때에는 append()를 사용하고
원소를 삭제할 때는 popleft()를 사용하면 된다. 이러면 먼저 들어온 원소가 항상 먼저 나가게 된다.
from collections import deque
data = deque([2, 3, 4])
data.appendleft(1)
data.append(5)
print(data) # deque([1, 2, 3, 4, 5])
print(list(data)) # 리스트 자료형으로 변환, 출력: [1, 2, 3, 4, 5]
Counter
collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공한다.
구체적으로 리스트와 같은 iterable 객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지를 알려준다.
따라서 원소별 등장 횟수를 세는 기능이 필요할 때 짧은 소스코드로 이를 구현할 수 있다.
from collections import Counter
counter = Counter('red', 'blue', 'red', 'green', 'blue'])
print(counter['blue']) #'blue'가 등장한 횟수 출력
print(dict(counter)) #사전 자료형으로 변환, 출력: {'red': 2, 'blue': 2, 'green': 1}
math
팩토리얼, 제곱근, 최대공약수(GCD) 등을 계산해주는 기능을 포함하고 있으므로,
수학 계산을 요구하는 문제를 만났을 때 효과적으로 사용될 수 있다.
import math
print(math.factorial(5)) # 5 팩토리얼 출력
print(math.sqrt(16)) # 16의 제곱근을 출력
print(math.gdc(21, 14)) #최대 공약수
print(math.pi) # 파이(pi) 출력
print(math.e) # 자연상수 e 출력
