언어/파이썬 & 장고
-
[Python] Kruskal Algorithm (크루스칼 알고리즘)언어/파이썬 & 장고 2019. 11. 30. 21:48
크루스칼 알고리즘의 이론은 https://brownbears.tistory.com/396에 설명이 되어 있습니다. 아래는 파이썬으로 기본적인 크루스칼 알고리즘을 어떻게 구현했는지에 대한 내용입니다. 코드에 앞서 크루스칼 알고리즘의 중요한 점은 아래와 같습니다.edge가 가장 작은 순으로 선택해 나감edge 연결 후, cycle이 생기면 안됨 즉, 가장 작은 edge를 선택할 때마다, 그동안 연결한 vertices끼리 cycle이 생기는지 확인을 해야 합니다. 이러한 cycle이 생겼는지 확인하는 것은 union-find (disjoint-set) 알고리즘을 사용합니다. union-find (disjoint-set) 알고리즘의 설명은 https://brownbears.tistory.com/460에 정리되어..
-
[Python] union find (disjoint-set) 알고리즘언어/파이썬 & 장고 2019. 10. 21. 00:16
union find (disjoint-set) 이란?서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조입니다. 간단하게 다수의 노드들 중에 연결된 노드를 찾거나 노드들을 합칠때 사용하는 알고리즘입니다. 아래 예시 그림을 보면 어떤 개념인지 바로 이해가 됩니다.원소(노드)가 1~10까지 있다고 할 때, 해당 원소들은 아래와 같은 리스트의 구조를 갖습니다. 첫 번째 행은 원소의 번호고 두 번째 행은 원소의 관계로 보면 됩니다. 1234567891012345678910 이러한 원소들은 아래와 같은 연결 구조를 갖고 있다고 가정합니다. 위 그림은 원소 1,2,3,4 / 5,6,7,8 / 9,10 과 같이 3개의 그룹으로 묶여 있습니다. 이를 리스트로 표현하면 아래와 같습니..
-
[Python] 조합(combination) 개수 계산하기언어/파이썬 & 장고 2019. 10. 13. 20:51
조합을 구하는 파이썬 내장함수가 있지만 (from itertools import combination) 이 함수는 리스트 조합의 결과를 반환합니다.from itertools import combinations lists = [1,2,3] a = list(combinations(lists, 2)) print(list(a)) # [(1, 2), (1, 3), (2, 3)] 따라서 단순히 개수를 확인할 때 사용하기에는 적합하지 않습니다. 이러한 이유로 아래와 같이 단순 개수만 반환하는 로직을 구현했습니다.import operator as op from functools import reduce def nCr(n, r): if n < 1 or r < 0 or n < r: raise ValueError r = m..
-
[Python] operator 모듈 사용해서 연산 처리 속도 빠르게 하기언어/파이썬 & 장고 2019. 10. 13. 20:44
파이썬에서 문자열을 더하거나 숫자를 곱하는 등의 코딩을 할 때 아래와 같이 연산자를 사용하게 됩니다.result = 'a' + 'b' result2 = 4 * 5여기서 파이썬 내부적으로 operator 모듈을 호출하여 처리를 한 다음 사용자에게 반환하게 됩니다. 만약 속도가 정말 중요한 프로그램에서 연산처리를 조금이나마 빠르게 하려면 operator 모듈을 사용하면 됩니다. 아래는 100만번 반복문을 실행하면서 각 값을 곱하는 예제로 수행속도를 확인한 코드입니다.from functools import reduce import operator import timeit def test1(): return reduce(operator.mul, range(1000000)) def test2(): return r..
-
[Python] functools 모듈의 reduce 함수 사용하기언어/파이썬 & 장고 2019. 10. 13. 20:25
reduce 함수는 아래와 같은 파라미터를 받고 있습니다.reduce(function, iterable, initializer=None)첫 번째 파라미터는 함수가 들어가게 됩니다. 따라서 람다일 수도 있고 정의해놓은 함수가 될 수도 있습니다. 두 번째 파라미터는 계산을 하고자 하는 리스트가 들어가게 됩니다. 아래는 reduce()의 예제입니다.from functools import reduce result = reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) # ((((1+2)+3)+4)+5) print(result) # 15 위 예제는 1,2,3,4,5 값을 전부 더한 결과를 반환합니다. 여기서 초기값 100이 존재한다고 하면 아래와 같이 reduce()에 세번째 파라미터를 지..
-
[Python] 함수 및 코드 실행시간 측정하기 (timeit 모듈 사용법)언어/파이썬 & 장고 2019. 10. 5. 23:24
파이썬에서는 timeit 모듈을 제공하고 있고 이 모듈을 사용하여 특정 프로젝트의 전체 실행시간이 아닌 특정 함수나 코드의 실행시간을 측정하는 방법을 소개합니다.timeit.timeit()timeit.timeit(stmt='pass', setup='pass', timer=, number=1000000, globals=None)timeit 함수의 파라미터는 아래와 같습니다.stmt: 실행측정할 코드 및 함수setup: stmt를 실행하기 위해 사전에 필요한 코드나 함수를 선언. setup의 실행 시간은 전체 측정 실행 시간에서 제외됨timer: Timer 인스턴스number: 선언한 stmt의 수행 횟수. 선언하지 않으면 기본값으로 1000000번이 실행됨예제먼저 사용 방법 예제는 아래와 같습니다.impo..
-
[Python] 소인수 분해, 약수 구하기언어/파이썬 & 장고 2019. 9. 29. 17:07
소인수 분해소인수 분해를 하기 위해선 이전에 정리한 에라토스테네스의 체 방식을 사용한 소수 구하기를 사용하여 변형하는 것이 좋습니다. (https://brownbears.tistory.com/445) 아래는 특정 값이 주어졌을 때, 소인수 분해를 한 예시입니다.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..
-
[Python] 최대공약수, 최소공배수, N개의 최소공배수언어/파이썬 & 장고 2019. 9. 22. 22:33
최대공약수 (Greatest Common Divisor)최대공약수는 주어진 두 수 x, y에서 x의 약수이면서 y의 약수인 수 중 최대값을 의미합니다. 최대공약수를 구하는 간단한 방법은 1에서 x와 y 중 작은 값의 범위에서 공약수(둘 모두 나머지가 0)를 모두 구한 다음 이 수들 중 최대값을 구하는 방법입니다. 1부터 x 또는 y 중 작은 값까지 반복하며 값을 구할 수 있지만 유클리드 호제법(Euclidean algorithm)을 이용하면 간단하게 계산이 됩니다.유클리드 호제법의 공식은 다음과 같습니다.최대공약수를 구하는 함수를 gcd(x,y)라고 가정x % y = 0이라면 gcd(x, y) = y가 성립x % y != 0이라면 gcd(x, y) = gcd(x, x % y)가 성립2번이 될 때까지 2~..
-
[Python] 순열, 조합, 곱집합언어/파이썬 & 장고 2019. 9. 21. 22:54
파이썬에서는 순열, 조합, 곱집합 기능을 내장함수로 제공하고 있습니다.순열 (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, ..
-
[Python] 리스트 slice, pop, del 성능 비교 및 사용방법언어/파이썬 & 장고 2019. 9. 21. 22:24
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] # 2pop() , delpop()과 del은 지우고자 하는 리스트의 인덱스를 받아서 지우는 방식입니다. 두 개의 차이는 pop()은 지워진 인덱스의 값을 반환하지만 del은 반환하지 않습니다. 이 차이 때문에 미세하게 del이 pop()보다 수행속도가 더 빠릅니다. 또한 remove()와 동일하게 pop()..