※찾으실게 있으시다면 Ctrl + F 활용하시면 편합니다 !
● max()/min()
문자 그대로 최댓값 / 최솟값을 찾아주는 메소드이다.
max([1,2,3]) #3
min([1,2,3]) #1
max(27, 10) #27
min(27, 10) #10● sorted()
iterable에 대해서 정렬하는 메소드이다. 반환 결과는 무조건 리스트로 반환되며, 파라미터를 통해 정렬 방식을 정할 수 있다.
◎ reverse : True면 내림차순, False면 오름차순(기본은 False)
◎ key : 정렬되는 기준, (ex. 딕셔너리에서 값을 기준으로 정렬하고 싶을 때)
- key 예시
arr = ["banana", "apple", "kiwi"]
# 길이 기준 정렬
sorted(arr, key=len)
# ['kiwi', 'apple', 'banana']
# 람다 사용
arr = [(1, 3), (2, 1), (3, 2)]
sorted(arr, key=lambda x: x[1])
# [(2,1), (3,2), (1,3)] ← 튜플 두번째 값 기준
- reverse 예시
sorted([3, 1, 2], reverse=True)
# [3, 2, 1]※ from itertools : 순열(permutations) , 조합(combinations) , 중복 순열(product)을 생성해준다
● permutations(iterable, r)
iterable에 대해서 r개를 뽑는 모든 경우의 순열을 생성해줌
-> 순서가 있고, 중복 없이 뽑는다
ex)
from itertools import permutations
list(permutations([1, 2, 3], 2))
# [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]
- 결과 개수 : n! / (n-r)! → 3!/(3-2)! = 6개
● combinations(iterble, r)
iterable에 대해서 r개를 뽑는 모든 경우의 조합을 생성해줌
-> 순서가 없고, 중복 없이 뽑는다
ex)
from itertools import combinations
list(combinations([1, 2, 3], 2))
# [(1,2), (1,3), (2,3)]
- 결과 개수 : n! / r!(n-r)! → 3!/2!1! = 3개
● product(iterable, repeat = r) :
iterable에 대해서 r개를 뽑는 모든 경우의 중복 순열을 생성해줌
ex)
from itertools import product
list(product([1, 2, 3], repeat=2))
# [(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]
- 결과 개수 : n^r → 3² = 9개
※ from collections
● deque()
BFS에서 많이 사용
양쪽 끝에서 삽입/삭제가 가능한 자료구조(double-ended-que)를 생성 (deque 구조 설명 Link ←)
ex)
from collections import deque
dq = deque([1, 2, 3])
# 삽입
dq.append(4) # 오른쪽 추가 → [1,2,3,4]
dq.appendleft(0) # 왼쪽 추가 → [0,1,2,3,4]
# 삭제
dq.pop() # 오른쪽 제거 → 4
dq.popleft() # 왼쪽 제거 → 0
# 회전
dq.rotate(1) # 오른쪽으로 한칸 회전 → [3,1,2]
dq.rotate(-1) # 왼쪽으로 한칸 회전 → [1,2,3]
●Counter()
문자 그대로 요소의 빈도수를 자동으로 세어준다.
ex)
from collections import Counter
# 문자열
Counter("hello")
# Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})
# 리스트
Counter([1, 1, 2, 3, 3, 3])
# Counter({3: 3, 1: 2, 2: 1})
# 가장 많은 요소 top 2
c = Counter("hello world")
c.most_common(2) # [('l', 3), ('o', 2)]
# 카운터끼리 연산도 가능
a = Counter("aab")
b = Counter("abc")
a + b # Counter({'a': 3, 'b': 2, 'c': 1})
a - b # Counter({'a': 1})● defaultdict(기본값 자료형)
원래 dictionary에서 없는 값에 접근하면 KeyError가 발생하지만, 없는 키에 접근해도 기본값으로 초기화되는 딕셔너리를 생성해준다.
ex)
from collections import defaultdict
# int → 기본값 0
d = defaultdict(int)
d["a"] += 1 # KeyError 없이 0으로 초기화 후 +1
d["a"] += 1
print(d["a"]) # 2
# list → 기본값 []
d = defaultdict(list)
d["a"].append(1)
d["a"].append(2)
print(d["a"]) # [1, 2]
# set → 기본값 set()
d = defaultdict(set)
d["a"].add(1)
d["a"].add(1)
print(d["a"]) # {1}※ from bisect
정렬된 배열에서 이진탐색으로 위치를 찾아준다.
-> 시간복잡도 O(log n)이어서 빠르게 탐색/삽입이 가능하다 !
-> 하지만 무조건 정렬된 배열에서 사용해야 해서 sort()이후 사용하는 경우가 많음
● bisect_left(arr, r)
arr(정렬된 배열)에서 r이 들어갈 가장 왼쪽(앞) 위치를 반환해준다.
ex)
from bisect import bisect_left
arr = [1, 2, 4, 4, 4, 5]
# 0 1 2 3 4 5
bisect_left(arr, 4) # 2 ← 4가 처음 나오는 위치
bisect_left(arr, 3) # 2 ← 3이 들어갈 왼쪽 위치
bisect_left(arr, 6) # 6 ← 맨 끝
●bisect_right(arr, r)
arr(정렬된 배열)에서 r이 들어갈 가장 오른쪽(뒤) 위치를 반환해준다.
ex)
from bisect import bisect_right
arr = [1, 2, 4, 4, 4, 5]
# 0 1 2 3 4 5
bisect_right(arr, 4) # 5 ← 4가 끝나는 위치 다음
bisect_right(arr, 3) # 2 ← 3이 들어갈 오른쪽 위치
bisect_right(arr, 6) # 6 ← 맨 끝
●insort(arr, r)
정렬이 되어있는 상태로 삽입을 한다( = insort_right)
-> 기본적으로 insort는 insort_right와 동일하다. 왼쪽에 삽입하고 싶다면 insort_left 사용
ex)
from bisect import insort
arr = [1, 2, 4, 5]
insort(arr, 3)
print(arr) # [1, 2, 3, 4, 5]
insort(arr, 4)
print(arr) # [1, 2, 3, 4, 4, 5]
insort_left, insort_right
from bisect import insort_left, insort_right
arr = [1, 2, 4, 4, 5]
insort_left(arr, 4) # [1, 2, 4, 4, 4, 5] ← 4 중 가장 왼쪽에 삽입
insort_right(arr, 4) # [1, 2, 4, 4, 4, 5] ← 4 중 가장 오른쪽에 삽입● heapq - 우선순위 큐
값이 작을수록 먼저 나오는 자료구조이다. pop을 진행할때 언제나 최소값을 꺼내온다.
삽입/삭제가 빈번할 때 시간복잡도가 매우 유리하다 : O(log n)
기본 사용법
import heapq
heap = []
# 삽입
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
# 꺼내기 (항상 최솟값)
heapq.heappop(heap) # 1
heapq.heappop(heap) # 3
heapq.heappop(heap) # 5
최댓값 꺼내기
파이썬의 heapq에서는 최소값을 반환하는 pop밖에 없기 때문에, 저장할 때 음수로 저장해서 넣고, 꺼낼 때 다시 음수로 변환해서 꺼내는 트릭을 이용해서 최댓값을 꺼낼 수 있다.
heap = []
heapq.heappush(heap, -5)
heapq.heappush(heap, -1)
heapq.heappush(heap, -3)
-heapq.heappop(heap) # 5 (최댓값)
튜플로 우선순위 지정하기
(우선순위, 값) 형태로 지정하여 우선순위 낮은것부터 뽑아올 수 있어 알고리즘에서 자주 쓰인다.
- 최단 경로, 작업 스케줄링, 최솟값 찾기 등등
heap = []
# (우선순위, 값) 형태로 삽입
heapq.heappush(heap, (2, "작업B"))
heapq.heappush(heap, (1, "작업A"))
heapq.heappush(heap, (3, "작업C"))
heapq.heappop(heap) # (1, "작업A") ← 우선순위 낮은 것부터
heapq.heappop(heap) # (2, "작업B")
heapq.heappop(heap) # (3, "작업C")