파이썬
-
Python random 모듈 구현하기컴퓨터/파이썬 2020. 10. 14. 15:52
Python python/cpython 파이썬 언어 오픈소스 github.com 0. MT19937 소개 파이썬에서 random.randint, random.randrange, random.seed...등은 모두 메르센-트위스터 기법 기반으로 제작되었다. 메르센 트위스터란 유사난수 생성기 중 하나이며, 주기는 2**19937-1 이며, 가장 널리 알려지고 다이하드 테스트와 같은 확률적 시험을 통과한 기법이다. (Dieharder test > diehard test, 생일 문제 등을 포함한 테스트임) 이 글에서 파이썬 버전과 일치하진 않지만, seed 함수, randrange 함수, randint 함수, random 함수를 구현해 볼 것이다. (원본 파이썬 버전은 맨 아래 참고 링크 파이썬에선 SHA-1,..
-
Python Tkinter 피보나치 수열, 소수 생성기 GUI컴퓨터/파이썬 2020. 9. 30. 22:37
tkinter tkinter은 파이썬 내장 GUI 라이브러리이다. tkinter — Tcl/Tk 파이썬 인터페이스 — Python 3.8.6 문서 tkinter — Tcl/Tk 파이썬 인터페이스 소스 코드: Lib/tkinter/__init__.py tkinter 패키지(《Tk 인터페이스》)는 Tk GUI 툴킷에 대한 표준 파이썬 인터페이스입니다. Tk와 tkinter는 대부분의 유닉스 플랫폼과 윈�� docs.python.org # 2020-09-30 공부 일지 1. 피보나치 생성 함수 원하는 숫자까지의 피보나치 수를 모두 저장한다. (less or equal) ex) n = 13이면, 0, 1, 1, 2, 3, 5, 8, 13을 보여줌 (시간 복잡도 O(n) | 공간 복잡도 O(1)) (하지만 tki..
-
Python Fast inverse square root컴퓨터/파이썬 2020. 9. 28. 20:18
고속 역 제곱근 Fast inverse square root - Wikipedia Fast inverse square root, sometimes referred to as Fast InvSqrt() or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates 1⁄√x, the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number x in IE en.wikipedia.org (Fast inverse square root) 1. 소개 IEEE 754 부동소수점 체계의 32비트 실수에 대한 제곱근의 역수를 계산하기 위한 알고리..
-
Python 중국인의 나머지 정리컴퓨터/파이썬 2020. 9. 25. 15:38
Chinese Remainder Theorem (중국인의 나머지 정리, 이하 CRT) 소개 CRT는 손자산경에, (손자병법 손자 아님), 3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고,7로 나누었을 때 2가 남는 수는 무엇인가? 간단해보이지만, 일반 방정식으로 해결하려해보면 꽤나 복잡하다. 필요한 사전 지식은, 연합 합동식을 알아야한다. 이 글에선, 식의 증명보다는 실제 몇 예제를 통해 문제를 푸는 법과, 파이썬 코드로 작성만 해볼 것이다. (증명은 맨 아래 참고 사이트를 이용) 합동식이란? 합동식만 먼저 설명하자면, $m~|~(a - b)$ 일 때 (m이 a-b로 나누어 떨어질 때), a는 법(modular) m에 대하여 b와 합동이다. 기호는 $a ≡ b~(mod~m)$ ex) $15 ..
-
Python Karatsuba(카라추바) 곱셈 알고리즘컴퓨터/파이썬 2020. 9. 24. 18:56
Karatsuba 알고리즘 1. 소개 카라추바 알고리즘이란, 큰 수에 대해 효과적인 곱셉 알고리즘이다. (23살에 1주일 만에 발견한 알고리즘) (보통 두 수 곱 시간 복잡도는 $O(n^2)$ 이지만 카라추바 알고리즘을 사용하면 O(n^1.585)가 나온다.) (실제로 파이썬도 일반적인 곱셉 알고리즘을 사용하지만, 매우 큰 수에 대해선 카라추바 알고리즘을 사용) (2019년에 나온 Harvey and van der Hoeven의 $O(nlogn)$ 곱셈이 가장 빠른데, 이 기법은, 10^850억 자리 이상의 수에서 작동한다. 카라추바처럼 수를 작은 파트로 쪼개지만, FFT (Fast Fourier Transform)를 사용해서 합친다. ) 2. 작동 방식 카라추바 알고리즘의 기본 단계는 큰 두 수 x와 ..
-
파이썬 Jest pytest 이용하기컴퓨터/파이썬 2020. 9. 22. 16:47
Jest는 심플함에 초점을 둔 자바스크립트 테스팅 프레임워크이다. Jest 파이썬 버전도 unittest, pytest 대신 사용할 수 있는 테스팅 프레임워크이다. 1. 설치 및 설정 yarn add jest-pytest pip install pytest-jest --upgrade pip install snapshottest 설치 후, package.json에 아래처럼 추가한다. "jest": { "moduleFileExtensions": [ "py" ], "runner": "jest-pytest", "testPathIgnorePatterns": [ "snap_.*\\.py" ], "testMatch": [ "/tests/test_*.py" ] } 개인 setup.cfg에 사용 중인 flake 및 pyt..
-
Python QuickSort 최적화에 따른 속도컴퓨터/파이썬 2020. 9. 20. 20:06
인터넷에 있는 QuickSort 중 제일 빠른 방법은 무엇일까라는 생각이 들어 테스트를 진행해보았다. (big-O-calculator와 런타임으로 비교) 결과는 다를 수 있음 (페이스북 코딩 면접 중 한 문제는 quickSort 작성이었다.) - TechLead 0. 속도 테스트 코드 from bigO import BigO lib = BigO() size = 10_000 lib.test_all(quickSort) lib.runtime(quickSort, "random", size) lib.runtime(quickSort, "sorted", size) lib.runtime(quickSort, "reversed", size) lib.runtime(quickSort, "partial", size) lib.ru..
-
파이썬 go-lang sort() 구현컴퓨터/파이썬 2020. 8. 29. 10:13
go-lang.sort() golang/go The Go programming language. Contribute to golang/go development by creating an account on GitHub. github.com 1. 소개 Go언어의 기본 정렬은 quickSort 변형을 사용하고 있다. 계산해보면, 시간 복잡도는 모든 상황에서 $O(nlog(n))$ | 공간 복잡도는 $O(1)$ Pseudo Code # Go Sort procedure sort(A : array): let maxdepth = log2(length(A) - 1) × 2 quickSort(A, 0, len(A), maxdepth) procedure quickSort(A, a, b, maxdepth): n ← b ..