본문 바로가기

전체 글

(11)

Deterministic Verification of Integer Matrix Multiplication in Quadratic Time 세 개의 $n \times n$ 크기의 정수 행렬 $A, B, C$에 대해 $AB == C$인지 $O(N^2)$에 판별하는 알고리즘을 알아보자.PS에서 보통 사용되는 $O(KN^2)$의 Freivalds' algorithm을 개선한 버전으로 생각할 수도 있지만, 이 알고리즘은 PS에선 쓰이지 않는다. 먼저, naive하게 $AB$를 계산하고 $C$와 비교하는 알고리즘의 시간복잡도는 $O(N^3)$이다. $AB$의 계산에서 $n \times n$ 크기의 두 행렬을 곱해야 하므로 $O(N^3)$의 계산이 필요하고, 계산된 결과가 $C$와 일치하는지 확인하는 데에 $O(N^2)$의 비교가 필요하기 때문이다. 조금 더 효율적인 방법이 없을까? $AB=C$라면 임의의 $n \times 1$ 열벡터 $x$에 대..

간단한 exgcd 1. exgcdtuple extendedGCD(ll a, ll b) { // ax + by = gcd(a, b) if (b == 0) return {1, 0, a}; auto [x2, y2, g] = extendedGCD(b, a % b); return {y2, x2 - (a / b) * y2, g};}베주항등식 $ax_1 + by_1 = g$ 는 항상 해 존재$let)~ a=bk+r$$(bk + r)x_1 + by_1 = g$$b(kx_1+y_1) + rx_1 = g$$let)~ x_2 = kx_1+y_1, y_2=x_1$$\therefore x_1=y_2, y_1 = x_2-ky_2$2. modular inversell modInverse(ll a, ll b) { // a^-1 mod..

오토핫키 롤 튕김 방지 롤할 때 백그라운드에 오토핫키 실행 중이면 데마시아에 잡혀서 강제탈주 당한다. 겜 시작 초반에는 정상적으로 게임이 되는 듯 하지만 15분쯤 지나면 튕기게 되고 이후 무한로딩에 걸린다. 아래 코드를 통해 롤이 실행되면 자동으로 오토핫키가 종료되도록 할 수 있다.모든 오토핫키 파일에 필수로 적어야 될 코드다.Loop{ IfWinExist, ahk_exe LeagueClientUx.exe exitapp} 코드 최상단에 적어야 한다. 핫키나 핫스트링 코드 밑에 적으면 처음 프로그램이 실행될 때 loop가 호출되지 않아 코드를 적어도 의미가 없다.

이전 1 2 다음

티스토리툴바