PYTHON
-
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와 ..
-
파이썬 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 ..
-
Python Microsoft Playwright컴퓨터/파이썬 2020. 8. 16. 17:05
Playwright microsoft/playwright-python Python version of the Playwright testing and automation library - microsoft/playwright-python github.com 소개 : playwright는 원래 JS 버전만 있었는데, python버전도 출시가 되었다. playwright는 chromium, firefox, webkit 오토메이션 툴이다. (macro) (주로 cross-browser 테스트로 많이 쓰이는 듯) 특징 기능 : action 실행 전 element auto-wait (ex. 지정한 HTML 요소가 나오면 클릭) 네트워크 요청받기 / 보내기 모바일 디바이스, 권한, 위치 에뮬레이션 shadow-pi..
-
파이썬 정렬 알고리즘 모음 + 속도 테스트컴퓨터/파이썬 2020. 8. 10. 16:34
15개 정렬 알고리즘 소개 0. 정렬 알고리즘 속도 테스트 코드 big-O-calculator 이용 @설치 링크 import bisect import heapq import inspect from random import randint, shuffle from statistics import mean from timeit import default_timer, repeat import matplotlib.pyplot as plt from bigO import BigO from win10toast import ToastNotifier # timeit.repeat 이용 def runAlgorithm(algorithm, array, timeResults): setup_code = f"from __main__ ..
-
파이썬 OpenCV 이미지 차이 구하기컴퓨터/파이썬 2020. 8. 6. 17:49
OpenCV OpenCV About the author:Pau Rodríguez is a research scientist at Element AI, Montreal. He earned his Ph.D. opencv.org 할 것 이미지 차이를 구해서 빨간색으로 칠하기 1. OpenCV 설치 pip install opencv-python 2. 이미지 설정 imageA = 원본, imageB = 비교 대상, imageC = 원본 복사 grayA = imageA를 gray scale, grayB = imageB를 gray scale cvtColor 문서 import cv2 from skimage.measure import compare_ssim imageA = cv2.imread("D:\DEV\Code\Py..
-
파이썬 Smooth Sort (부드러운 정렬 알고리즘)컴퓨터/파이썬 2020. 8. 3. 13:12
Smooth Sort 소개 : 부드러운 정렬은 길 찾기로 유명한 데이크스트라분이 1981년에 발표한 정렬 알고리즘이다. HeapSort의 변형 중 하나이며, in-place, not stable 시간 복잡도는 최고 : O($n$) = (대부분 정렬된 상태일 경우) 평균 : O($nlogn$), 최악 : O($nlogn$) 공간 복잡도는 총 O($n$), 보조(O($1$)) 특이한 점은 Leonardo number라는 수학 개념을 Heap Sort에 적용시킨 점이다. 1. Leonardo Number 피보나치 수열과 비슷한데, 다음과 같이 진행된다. $1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361 ....
-
Docker + Flask 튜토리얼컴퓨터/파이썬 2020. 7. 30. 22:14
Docker 1. 사전 준비 Docker, WSL2 (윈도우를 위한 Linux 시스템) WSL 2 Linux용 Windows 하위 시스템 2 docs.microsoft.com 아래 flask-app.zip 압축 해제한다. 2. DockerFile 우선 DockerFile 구조를 한 번 살펴보겠다. FROM python:3 # set a directory for the app WORKDIR /app # copy all the files to the container COPY . . # install dependencies RUN pip install --no-cache-dir -r requirements.txt # tell the port number the container should expose EX..
-
파이썬 A* (A-star) 최단 경로 찾기 알고리즘컴퓨터/파이썬 2020. 7. 20. 16:02
A* 길 찾기 알고리즘은 1968년에 Peter Hart, Nils Nilsson, Bertram Raphael에 의해 최초 공개됐다.우선 Node 클래스는 아래와 같이 구현될 것이며, 아래 클래스를 보고 글을 읽으면 좀 더 편할 것이다.class Node: def __init__(self, parent=None, position=None): self.parent = parent # 이전 노드 self.position = position # 현재 위치 self.f = 0 self.g = 0 self.h = 0ex) 노드의 현재 위치는 xy좌표계를 사용한다.start = (0, 0), end = (9,9)aSta..