내장함수
파이썬에는 별도의 import 명령어 없이 바로 사용할 수 있는 내장 함수가 존재한다. 내장 함수는 print(), input()과 같은 기본 입출력 기능부터 sorted()와 같은 정렬 기능을 포함하고 있다. 우리가 코딩테스트를 준비하기 위해 반드시 알아야 할 함수 몇 개를 알아보자. ㅇㅅㅇ
sum()
sum() 함수는 iterable 객체가 입력으로 주어졌을 때, 모든 원소의 합을 반환한다. 다음의 예시를 확인해보자.
# 입력
result = sum([1, 2, 3, 4, 5])
print(result)
# 출력
15
min()
min() 함수는 파라미터가 2개 이상 들어왔을 때 가장 작은 값을 반환한다. 다음의 예시를 확인해보자.
# 입력
result = min([6, 3, 7, 2, 4])
print(result)
# 출력
2
max()
max() 함수는 min() 함수의 반대다. 파라미터가 2개 이상 들어왔을 때 가장 큰 값을 반환한다. 바로 예시를 확인해보자.
# 입력
result = max([6, 3, 7, 2, 4])
print(result)
# 출력
7
eval()
eval() 함수는 수학 수식이 문자열 형식으로 들어오면 해당 수식을 계산한 결과를 반환한다. 예를 들면 다음과 같다.
# 입력
result = eval("(2 + 4) * 7")
print(result)
# 출력
42
sorted()
sorted() 함수는 iterable 객체가 들어왔을 때, 정렬된 결과를 반환한다. key 속성으로 정렬 기준을 명시할 수 있으며, reverse 속성으로 정렬된 결과 리스트를 뒤집을지의 여부를 설정할 수 있다. 다음의 예시들을 확인해보자.
# 입력
result = sorted([6, 2, 3, 5, 4])
print(result)
result = sorted([6, 2, 3, 5, 4], reverse = True)
print(result)
# 출력
[2, 3, 4, 5, 6]
[6, 5, 4, 3, 2]
# 입력
result = sorted([('윤석열', 55), ('문재인', 35), ('박근혜', 25)], key = lambda x: x[1], reverse = True)
print(result)
# 출력
[('윤석열', 55), ('문재인', 35), ('박근혜', 25)]
리스트와 같은 iterable 객체는 기본으로 sort() 함수를 내장하고 있어서 굳이 sorted() 함수를 사용하지 않고도 sort() 함수를 사용해서 정렬할 수 있다. 이 경우 리스트 객체의 내부 값이 정렬된 값으로 바로 변경된다. 다음의 코드를 보자.
# 입력
data = [7, 1, 8, 5, 3]
data.sort()
print(data)
# 출력
[1, 3, 5, 7, 8]
itertools
itertools는 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리다. 제공하는 클래스는 매우 다양하지만, 코딩테스트에서 가장 유용하게 사용할 수 있는 클래스는 permutations, combinations이다.
permutations
permutations는 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산해준다. 우리가 학창시절에 배웠던 순열과 같은 개념이다. 리스트에서 원소 3개를 뽑아 나열하는 모든 경우를 출력하는 예시를 보자.
# 입력
import itertools
data = ['A', 'B', 'C']
nPr = list(itertools.permutations(data, 3))
print(nPr)
print(len(nPr))combinations
combinations는 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우를 계산해준다. 우리가 학창시절에 배웠던 조합과 같은 개념이다. 리스트에서 원소 2개를 뽑아 순서와 상관없이 나열하는 모든 경우를 출력하는 예시를 보자.
# 입력
import itertools
data = ['A', 'B', 'C']
nCr = list(itertools.combinations(data, 2))
print(nCr)
print(len(nCr))
# 출력
[('A', 'B'), ('A', 'C'), ('B', 'C')]
3
product
product는 permutations와 같이 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산한다. 다만, 원소를 중복하여 뽑으므로 중복순열의 개념과 같다. product를 초기화할 때는 뽑고자 하는 데이터의 수를 repeat 속성값으로 넣어준다. product는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다. 리스트에서 중복을 포함하여 원소 2개를 뽑아 나열하는 모든 경우를 출력하는 예시는 다음과 같다.
# 입력
import itertools
data = ['A', 'B', 'C']
result = list(itertools.product(data, repeat=2))
print(result)
print(len(result))
# 출력
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
9
순열과 조합에 관한 이야기는 다른 포스트에서도 다룬 적이 있으므로 시간이 나면 참고하자.
https://vegetableworld.tistory.com/125
[Python] 순열과 조합 (permutations & combinations)
순열이란 서로 다른 n개의 원소에서 r개를 중복없이 순서를 고려하여 선택 혹은 나열하는 것을 의미한다.파이썬에서는 itertools를 이용하면 순열 내장함수인 permutations를 사용할 수 있다. 하나의
vegetableworld.tistory.com
heapq
파이썬에서는 힙 기능을 위해 heapq 라이브러리를 제공한다. heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용된다. heapq 외에도 PriorityQueue 라이브러리를 사용할 수 있지만, 코딩테스트 환경에서는 보통 heapq가 더 빠르게 동작하므로 이걸 사용하도록 하자.
파이썬의 힙은 최소 힙으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다. 보통 최소 힙 자료구조의 최상단 원소는 항상 '가장 작은' 원소이기 때문이다.
힙에 원소를 삽입할 때는 headq.heappush() 메서드를 이용하고, 힙에서 원소를 꺼내고자 할 때는 heapq.headpop() 메서드를 이용한다. 힙 정렬을 headq로 구현하는 예제를 통해 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]
또한 파이썬에서는 최대 힙을 제공하지 않는다. 따라서 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 라이브러리를 제공한다. bisect 라이브러리를 '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다. bisect 라이브러리에서는 bisect_left() 함수와 bisect_right() 함수가 가장 중요하게 사용되며, 이 두 함수는 시간 복잡도 O(NlogN)에 동작한다.
- bisect_left(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽일할 가장 왼쪽 인덱스를 찾는 메서드
- bisect_right(a, x): 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
예를 들어 정렬된 리스트 [1, 2, 4, 4, 8]이 있을 때, 새롭게 데이터 4를 삽입하려 한다고 가정하자.
이 때, bisect_left(a, 4)와 bisect_right(a, 4)는 각각 인덱스값으로 2와 4를 반환한다.
이를 소스코드로 구현하면 다음과 같다.
# 입력
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
또한 bisect_left() 함수와 bisect_right() 함수는 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구하고자 할 때, 효과적으로 사용될 수 있다.
아래의 count_by_range(a, left_value, right_value) 함수를 확인해보자. 이는 정렬된 리스트에서 값이 [left_value, right_value]에 속하는 데이터의 개수를 반환한다. 다시 말해 원소의 값을 x라고 할 때, left_value 〈= x 〈= right_value 인 원소의 개수를 O(NlogN)으로 빠르게 계산할 수 있다.
# 입력
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))
# 출력
2
6
collections
파이썬의 collections 라이브러리는 유용한 자료구조를 제공하는 표준 라이브러리다. collections 라이브러리의 기능 중에서 코딩 테스트에서 유용하게 사용되는 클래스는 deque과 Counter이다. 이 2가지에 대해서 차례대로 알아보자.
deque
보통 파이썬에서는 deque를 사용해 큐를 구현한다. 별도로 제공되는 Queue 라이브러리가 있는데 일반적인 큐 자료구조를 구현하는 라이브러리는 아니다. 따라서 deque을 이용해 큐를 구현해야 한다는 점을 기억하자.
기본 리스트 자료형은 데이터 삽입, 삭제 등의 다양한 기능을 제공한다. 리스트가 있을 때 중간에 특정한 원소릉 삽입하는 것도 가능하다. 하지만 리스트 자료형은 append() 메서드로 데이터를 추가하거나, pop() 메서드로 데이터를 삭제할 때 '가장 뒤쪽 원소' 를 기준으로 수행된다. 따라서 앞쪽에 있는 원소를 처리할 때에는 리스트에 포함된 데이터의 개수에 따라서 많은 시간이 소요될 수 있다. 리스트에서 앞쪽에 있는 원소를 삭제하거나 앞쪽에 새 원소를 삽입할 때의 시간 복잡도는 O(N)이다. 이를 비교하면 다음의 표와 같다.
| 리스트 | deque | |
| 가장 앞쪽에 원소 추가 | O(N) | O(1) |
| 가장 뒤쪽에 원소 추가 | O(1) | O(1) |
| 가장 앞쪽에 있는 원소 제거 | O(N) | O(1) |
| 가장 뒤쪽에 있는 원소 제거 | O(1) | O(1) |
deque에서는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없다. 다만, 연속적으로 나열된 데이터의 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때는 매우 효과적으로 사용될 수 있다. deque는 스택이나 큐의 기능을 모두 포함한다고도 볼 수 있기 때문에 스택 혹은 큐 자료구조의 대용으로 사용될 수 있다.
deque는 첫 번째 원소를 제거할 때 pop(left)를 사용하며, 마지막 원소를 제거할 때 pop()을 사용한다. 또한 첫 번째 인덱스에 원소 x를 삽입할 때 appendleft(x)를 사용하며, 마지막 인덱스에 원소를 삽입할 때 append(x)를 사용한다.
따라서 deque를 큐 자료구조로 이용할 때, 원소를 삽입할 때에는 append()를 사용하고 원소를 삭제할 때에는 popleft()를 사용하면 된다. 그러면 먼저 들어온 원소가 항상 먼저 나가게 된다. 리스트 [2, 3, 4]의 가장 앞쪽과 뒤쪽에 원소를 삽입하는 예시는 다음과 같다.
# 입력
from collections import deque
data = deque([2 ,3, 4])
data.appendleft(1)
data.append(5)
print(data)
print(list(data)) # 리스트 자료형으로 변환
# 출력
deque([1, 2, 3, 4, 5])
[1, 2, 3, 4, 5]
Counter
파이썬 collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공한다. 구체적으로 리스트와 같은 iterable 객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지를 알려준다. 따라서 원소별 등장 횟수를 세는 기능이 필요할 때 짧은 소스코드로 이를 구현할 수 있다.
# 입력
from collections import Counter
counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])
print(counter['blue'])
print(counter['green'])
print(dict(counter))
# 출력
3
1
{'red': 2, 'blue': 3, 'green': 1}
이 글은 '이것이 코딩테스트다' 라는 서적을 참고하여 작성했습니다.
'Algorithm > Python' 카테고리의 다른 글
| [Python] zip함수(두 개의 리스트를 묶어주기) (0) | 2024.07.07 |
|---|---|
| [Python] format 함수(인자 전달) (0) | 2024.07.06 |
| [Python] 리스트 안의 특정 원소를 전부 삭제하는 법 (remove) (0) | 2024.06.30 |
| [Python] set 함수 (중복제거) (0) | 2023.09.27 |
| [Python] 순열과 조합 (permutations & combinations) (0) | 2023.09.17 |
