Processing math: 100%

본문 바로가기

전체 글

(26)

유클리드 호제법 알고리즘의 시간복잡도 예측하기 UPD: 자기 전에 생각해보니, 유클리드 호제법은 끝나기 직전을 제외하고 무조건 2 이상의 수로 나눌 수밖에 없어서 log의 밑이 2보다는 크다. 따라서 아래 글은 전부 헛짓이다.. 오늘 학원에서 공부를 하다가 굉장히 재밌는 논의를 발견했다. 그걸 이용해서 유클리드 호제법 연산 횟수의 상한을 알아내 보았다. 0. 유클리드 호제법 알고리즘 & 왜 이걸 증명하는가 유클리드 호제법은 다음 사실에 기반한다:

$a, b$ 가

$a\geq b$ 를 만족하는 정수이고,

$a=bq+r$ 이 성립할 때,

$gcd(a, b) = gcd(b, r)$ 이다. 그런데,

$gcd(a, 0)=a$ 임을 알고 있고,

$r$ 은

$b$ 보다 작으므로

$min(a, b)$ 는 자연수의 감소수열이 되고, 언젠가 0이 되므로 저 방식을 계속 쓰다 보면 ..

Segment Tree with Lazy Propagations 레이지 프로파게이션..배우겠다고 몇 번을 다짐한 자료 구조 중 하나이다. I. 단순 세그먼트 트리 우리가 처음에 구현한 세그먼트 트리는, 어떤 구간에 대한 연산과 특정 원소 하나를 바꾸는 연산을 모두 O(logN)에 처리한다. void update(ll n, ll k) { n += base; IDT[n] += k; while (n > 1) { n /= 2; IDT[n] = IDT[n * 2] + IDT[n * 2 + 1]; } } ll query(ll s, ll e, ll node, ll nodel, ll noder) { if (nodere) return 0; if (s https://blog.naver.com/insoo0327/222208708167 2. 레이지에 여러 가지 연산 합치기 보통 어려운..

티스토리툴바