파이썬에서는 순열, 조합, 곱집합 기능을 내장함수로 제공하고 있습니다.

순열 (Permutation)

순열이란 순서를 정해서 나열한 것을 말합니다.

nPr로 표시하며 n * (n-1) * (n-2) * ... * (n-r+1) 로 계산됩니다.


예를 들어, 1,2,3의 숫자가 적힌 카드가 있을 때, 이 중 두 장을 꺼내는 경우의 수(여기서 뽑힌 카드의 결과에 대해서 순서를 보장)를 구한다고 할 때, 코딩을 직접 해야 하지만 파이썬에서는 이를 직접 코딩할 필요없이 아래와 같은 기능을 제공해주고 있습니다.

from itertools import permutations

lists = [1,2,3]

a = list(permutations(lists, 2))
print(list(a))

# 결과
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

조합 (Combination)

조합이란 서로 다른 n개에서 순서를 생각하지 않고 r개를 뽑는 것을 말합니다.

nCr로 표시하며 n! / r!(n-r)! 로 계산됩니다.


예를 들어, 1,2,3의 숫자가 적힌 카드가 있을 때, 이 중 두 장을 꺼내는 경우의 수(여기서 뽑힌 카드의 결과에 대해서 순서를 무시)를 구한다고 할 때, 코딩을 직접 해야 하지만 파이썬에서는 이를 직접 코딩할 필요없이 아래와 같은 기능을 제공해주고 있습니다.

from itertools import combinations

lists = [1,2,3]

a = list(combinations(lists, 2))
print(list(a))

# [(1, 2), (1, 3), (2, 3)]

곱집합 (Cartesian product)

곱집합이란 여러 집합들 간에 하나씩 뽑아 조합을 만들 수 있는 모든 수를 뜻합니다.

[1,2,3]과 [a,b,c] 가 있을 때, 모든 각 리스트에서 1개씩 뽑아서 만들 수 있는 모든 조합의 수를 구하는 기능을 파이썬에서는 아래와 같이 제공해주고 있습니다.

from itertools import product

a = [1,2,3]
b = ['a', 'b', 'c']

a = product(a,b)
print(list(a))

# [(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c')]


slice, pop, del 사용방법

remove()

remove()는 지우고자 하는 인덱스가 아닌, 값을 입력하는 방식입니다. 만약 지우고자 하는 값이 리스트 내에 2개 이상이 있다면 순서상 가장 앞에 있는 값을 지우게 됩니다. 해당 값을 삭제 후, 리스트를 재조정합니다.

a = [1,2,1,3,4,5,1]
a.remove(1)


print(a)
print(a[0])
# [2, 1, 3, 4, 5, 1]
# 2

pop() , del

pop()과 del은 지우고자 하는 리스트의 인덱스를 받아서 지우는 방식입니다. 두 개의 차이는 pop()은 지워진 인덱스의 값을 반환하지만 del은 반환하지 않습니다. 이 차이 때문에 미세하게 del이 pop()보다 수행속도가 더 빠릅니다. 또한 remove()와 동일하게 pop()과 del은 특정 인덱스를 삭제한 다음, 리스트를 재조정합니다. 

a = [1,2,1,3,4,5,1]
removed = a.pop(1)


print(a) 
print(removed) 
print(a[0])


# [1, 1, 3, 4, 5, 1] 
# 2 
# 1


a = [1,2,1,3,4,5,1] 
del a[1]


print(a) 
print(a[0])


# [1, 1, 3, 4, 5, 1] 
# 1


del은 pop()과 다르게 리스트의 범위를 지정해 삭제할 수 있습니다.

a = [1,2,1,3,4,5,1]
del a[:2]

print(a)

# [1, 3, 4, 5, 1]

slice

슬라이싱은 위와 같이 리스트의 값을 지우는 것이 아닌, 사용자가 원하고자 하는 범위를 출력합니다. 즉, 원본 리스트는 그대로 존재하며 원하고자 하는 범위만큼 출력을 하기 위해 새로운 리스트가 생성됩니다.

a = [1,2,1,3,4,5,1]
b = a[1:]

print(b)
print(a)


# [2, 1, 3, 4, 5, 1]
# [1, 2, 1, 3, 4, 5, 1]

성능비교

위에서 설명한 것과 같이 리스트를 조작하는 기능은 다양하지만 성능면으로 어떤 것을 사용해야 할 지 몰라서 성능측정을 실험했습니다.


아래 예제는 리스트에 문자를 50개 입력 후, 각각 pop(), 슬라이싱, del, remove()를 한 다음 걸린 시간을 출력한 예시입니다.

import timeit

t1 = timeit.Timer('a=50*[\'a\'];a.pop(0)')
t2 = timeit.Timer('b=50*[\'b\'];b[1:]')
t3 = timeit.Timer('c=50*[\'c\'];del c[0]')
t4 = timeit.Timer('d=50*[\'d\'];d.remove(\'d\')')

r1 = t1.timeit(10000)/10000
r2 = t2.timeit(10000)/10000
r3 = t3.timeit(10000)/10000
r4 = t4.timeit(10000)/10000

print(r1)
print(r2)
print(r3)
print(r4)


# 결과
# 5.434282997157424e-07
# 6.363352003972978e-07
# 3.8072100142017007e-07
# 4.4290010118857026e-07

결과로 보면 슬라이싱이 가장 느리고 del이 가장 빠른 것으로 보입니다.


다음은 50만개를 진행한 예시입니다.

import timeit

t1 = timeit.Timer('a=500000*[\'a\'];a.pop(0)')
t2 = timeit.Timer('b=500000*[\'b\'];b[1:]')
t3 = timeit.Timer('c=500000*[\'c\'];del c[0]')
t4 = timeit.Timer('d=500000*[\'d\'];d.remove(\'d\')')

r1 = t1.timeit(10000)/10000
r2 = t2.timeit(10000)/10000
r3 = t3.timeit(10000)/10000
r4 = t4.timeit(10000)/10000

print(r1)
print(r2)
print(r3)
print(r4)


# 결과
# 0.0023742580446007196
# 0.004082370479300153
# 0.0022798048890021166
# 0.0023372766565007623


위 실험을 통해 봤을 때, del이 가장 빠르고 pop()과 remove()는 비슷한 수행시간을 가지며 슬라이싱이 가장 느립니다.

요약

원본 리스트가 변질이 되지 않아야 하면 슬라이싱을 사용하는 것이 좋다.

하지만 슬라이싱은 데이터를 삭제하는 del, remove(), pop()에 비해 50% 이상 느리다.


먼저 행렬을 곱하기 위해서는 앞 행렬의 열의 수와 뒤 행렬의 행의 수가 같아야 됩니다. 이러한 조건이 맞다면 행렬의 곱셈의 결과 크기는 (앞 행렬의 의 수)×(뒤 행렬의 의 수)가 됩니다. 즉, 앞 행렬이 m X n 이고 뒤 행렬이 n X r 인 경우 곱은 m X r 크기의 행렬이 됩니다.

예를 들어, 2x2 행렬의 곱은 아래와 같습니다.

이를 식으로 표현하면 아래와 같습니다.

따라서 행렬의 곱셈의 복잡도는 O(n^3)입니다.

아래는 복잡도 O(n^3)의 행렬의 곱셈을 구하는 파이썬 코드입니다.

def solution(arr1, arr2):
    answer = []
    for i in range(0, len(arr1)):
        temp_row = []
        for j in range(0, len(arr2[0])):
            value = 0
            for k in range(0, len(arr1[0])):
                value += arr1[i][k] * arr2[k][j]
            temp_row.append(value)
        answer.append(temp_row)
    return answer


이보다 빠른 행렬의 곱셈 알고리즘은 슈트라센 알고리즘 O(n^2807), 위노그라드 알고리즘 O(n^2.795), 코퍼스미스-위노그라드 알고리즘 O(n^2.3737) 등이 존재합니다.

이전에 PostgreSQL에서 사용자가 원하는 정렬을 하는 로직을 정리했습니다. (https://brownbears.tistory.com/384) 여기서는 Djago ORM을 이용하여 사용자가 원하는 order by를 하는 방법을 설명합니다.


PostgreSQL 9.5 이상의 버전이라면 array_position 을 사용해 손쉽게 사용자가 원하는 정렬을 할 수 있지만 Django ORM은 해당 기능을 지원하지 않기 때문에 Case문을 사용해 정의합니다.

from django.db.models import Case, Q

# 아래의 pk 순서대로 정렬하고자 함
pk_list = [2, 10, 1]
preserved = Case(*[When(pk=pk, then=pos) for pos, pk in enumerate(pk_list)])
queryset = MyModel.objects.filter(pk__in=pk_list).order_by(preserved)


소수란 1과 자기 자신만을 가지는 정수입니다. 소수를 구하는 알고리즘은 많지만 여기서 설명하는 알고리즘은 에라토스테네스의 체라고 불리는 알고리즘입니다. 에라토스테네스는 고대 그리스의 수학자로서 마치 체로 걸러 내는 것처럼 수를 걸러 낸다고 하여 에라토스테네스의 체라고 부릅니다.

이 방법은 아주 단순하지만 소수를 구하는데 효과적인 방법입니다.

원리

숫자 1 ~ 120 범위 안에 있는 소수를 모두 계산한다고 가정합니다.

  1. 1은 소수도, 합성수도 아닌 기초수이기 때문에 1을 제거합니다. 
  2. 2는 소수이므로 2를 다른 곳에 기록합니다.
  3. 자기 자신(2)를 제외한 2의 배수를 모두 지웁니다.
  4. 남아있는 수에서 2 다음인 수인 3부터 진행을 시작합니다.
  5. 3은 소수이므로 2를 기록한 곳에 기록합니다.
  6. 자기 자신(3)을 제외한 3의 배수를 모두 지웁니다.
  7. 3 다음의 수는 4이지만 2의 배수로 2번에서 지워졌으므로 남아있는 수에서 3 다음인 수인 5부터 진행을 시작합니다.
  8. 5은 소수이므로 2와 3을 기록한 곳에 기록합니다.
  9. 자기 자신(5)를 제외한 5의 배수를 모두 지웁니다.
  10. 위의 과정을 끝까지 반복하면 구하는 구간의 모든 소수가 남습니다.

위의 과정은 구하고자 하는 120까지의 수를 계속해서 지워나가는 방식입니다. 이 방식은 소수를 확실하게 구할 수 있지만 시간복잡도가 O(n^2)이 발생합니다. 여기서 에라토스테네스의 체를 이용하면 계산하는 범위를 줄일 수 있습니다.

에라토스테네스의 공식은 위 과정을 120까지 할 필요 없이 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 소수를 구할 수 있습니다. 따라서 위의 경우, 2, 3, 5, 7의 배수를 지우고 남은 수는 모두 소수입니다.

즉, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없습니다. 120에 루트를 씌우면 10.954451150103322의 값이 나오는데 이는 11보다 작으므로 11이하의 배수만 체크해도 소수를 구할 수 있습니다. 

코드

import math


def get_primes(n):
    # 구하고자 하는 수만큼 True를 갖는 리스트 생성
    is_primes = [True] * n
    # n의 최대 약수가 sqrt(n) 이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복 횟수 계산
    max_length = math.ceil(math.sqrt(n))

    for i in range(2, max_length):
        # True일 경우, 소수
        if is_primes[i]:
            # i이후 i의 배수들을 지워나감
            for j in range(i+i, n, i):
                is_primes[j] = False

    # 리스트의 True로 남아 있는 인덱스(소수)를 추출
    return [i for i in range(2, n) if is_primes[i]]


a = get_primes(10)
print(a)



파이썬에서 반올림은 보통 아래와 같이 구현합니다.

round(0.6)
# 1
round(2.4)
# 2


round()에 대해 찾아보면 자세한 내용이 있지만 간단하게 우리가 아는 반올림은 통계적인 반올림이고 파이썬의 round()는 수학적 반올림 값을 반환합니다. 이 때문에 나오는 결과에 대해서 사사오입 원칙이라고도 하는데 이를 설명하면 반올림 대상의 값이 5이고, 반올림 대상의 앞자리의 숫자가 짝수면 내림, 홀수면 올림을 진행합니다.

round(4.5)
# 4
round(0.5)
# 0
round(5.5)
# 6
round(1.5)
# 2


위 예시처럼 4.5는 반올림 대상의 앞자리가 짝수이므로 내림이 되었고 5.5에서는 5가 홀수이므로 올림이 되었습니다. 이러한 규칙을 모르고 반올림을 구한다면 시스템에 큰 오류를 범하고 문제 찾는거에 미궁이 빠지게 됩니다.

따라서 사람이 인식하고 있는 반올림을 구현하려면 내장 함수만으로는 불가능하고 반올림 함수를 직접 만들어야 합니다.

+ Random Posts