Python for Coding test 3

heapq

파이썬에서는 힙 기능을 위해 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))
    result result
 -
 reulst = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
 print(result) 

파이썬에서는 최대 힙을 제공하지 않는다. 따라서 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
   -
reulst = 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_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• bisect_right(a, x) : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

또한 bisect_left() 함수와 bisect_right() 함수는 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구하고자 할 때, 사용될 수 있다.

원소의 값을 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를 사용해 큐를 구현해야 한다.
리스트를 추가하거나, 삭제할 때는 '가장 뒤쪽 원소'를 기준으로 수행되므로 앞쪽에 있는 원소를 처리할 때는 많은 시간이 소요될 수 있다.
리스트에서 앞쪽에 있는 원소를 삭제하거나 추가할 때의 시간 복잡도는 O(N)이다.

deque에서는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없으나 연속적으로 나열된 데이터의 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때는 매우 효과적으로 사용될 수 있다.

deque는 스택, 큐의 기능을 모두 포함한다고도 볼 수 있기 때문에 스택 혹은 큐 자료구조의 대응으로 사용될 수 있다.

deque는 첫 번째 원소를 제거할 때 popleft()를 사용하며, 마지막 원소를 제거할 때 pop()을 사용한다.
또한 첫 번째 인덱스에 원소 x를 삽입할 때 appendleft(x)를 사용

from collections import deque
  -
data = deque([2, 3, 4])
data.appendleft(1)
data.append(5)
  -
print(data)
print(list(data)) #리스트를 자료형으로 변환 

파이썬 collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공한다.
리스트와 같은 iterable 객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지를 알려준다.

from collections import Counter
- 
counter = Counter(['red', 'blue', 'green', 'blue', 'blue'])
-
print(counter['blue']) # 'blue'가 등장한 횟수 출력
print(counter['green']) # 'green'이 등장한 횟수 출력
print(dict(counter)) # 사전 자료형으로 변환