파이썬의 정렬과 힙 #1

python의 sort 커스텀

• 정렬의 기준이 되는 가중치를 key 필드로 임의 지정할 수 있다.

# 1. 튜플의 합을 가중치로 두는 정렬
def take_sum(elem):
    return elem[0] + elem[1]

random = [(2, 2), (3, 4), (4, 1), (1, 3)]
sorted_list = sorted(random, key=take_sum)
print('Sorted list:', sorted_list)

원소가 이터러블일때 모두 사용가능하다.

# 2. 문자열의 join를 가중치로 두는 정렬
def comparator(a, b):
    t1 = a + b
    t2 = b + a
    return int(t1) - int(t2)

random = [3, 30, 300, 94, 939, 9, 5, 0]
random = sorted(random, key=functools.cmp_to_key(comparator), reverse=True)

가중치를 자유롭게 지정할 수 있다.

is_prime 구현

• 소수 구하기

def is_prime(number):
    if number < 2:
        return False
    elif number == 2 or number == 3:
        return True
    else:
        i = 2
        root = sqrt(number)
        while i <= root:
            if number % i == 0:
                return False
            i += 1
        return True

heapq, deque 짧은 정리

• 이진트리기반의 heapq와 연결리스트 기반의 데크는 원소를 추가하고 삭제하는 것이 배열보다 비용이 적다.
• heqpq : 우선순위 큐

import heapq

list = [] # 배열을 활용한다
heapq.heapify(list)
heapq.heappush(list, 1)
heapq.heappush(list, 2)
heapq.heappush(list, 3)
heapq.heappop(list)

data = [4,3,5,6,3]
heapq.heapify(data)

• deque : 양 끝단에서 데이터를 넣고 뺄 수 있는 큐

from collections import deque

deque = deque()
deque.append(1)
deque.append(2)
deque.append(3)
deque.appendleft(4)
deque.pop()
dequq.popleft()
deque.reverse()