확장 유클리드 알고리즘
objective
Posts by Category
algorithm
카라츠바 알고리즘
소개 카라츠바 알고리즘은 분할정복을 이용하여 곱셈을 최적화시킨 알고리즘이다. 기존 우리가 하던 방식으로는 의 시간복잡도를 가지지만, 카라츠바 알고리즘은 이것을 의 시간복잡도로 바꿔준다.
math
확장 유클리드 알고리즘
objective
카라츠바 알고리즘
소개 카라츠바 알고리즘은 분할정복을 이용하여 곱셈을 최적화시킨 알고리즘이다. 기존 우리가 하던 방식으로는 의 시간복잡도를 가지지만, 카라츠바 알고리즘은 이것을 의 시간복잡도로 바꿔준다.
ps
10986 - 나머지 합
최적화 하는데서 좀 많이 헤맴. 처음에 아 걍 prefix sum이네! 하고 바로 짰는데 터짐. 간단하게 접근하면 제곱시간이 나오는데 그러면 시간초과나서 터짐.(제한시간 1초) 따라서 더 간단히 최적화할 방법을 찾아야함. 를 i까지의 부분합이라고 하자. 구간...
reversing
오늘 푼 리버싱 문제
jit in my pants 매우 자명하게도 jit의 동작방식을 생각해보면 mprotect와 memcpy를 호출하는 쪽에서 jit코드를 복사하는 부분이 있을것임.(내가 개발자라면 그렇게 함.)