본문 바로가기

알고리즘

 (3)
Optimal Binary Search Tree 염치 없이 돌아왔다. 이번 학기에는 자료구조 수업을 듣게 되었는데, 상당히 흥미로운 내용이 많아서 정리할 겸 블로그에 올려두려고 한다. 그 첫 시작은 바로 최적 이진탐색트리(OBST)에 관한 것! 1. 문제 정의 보통 우리가 생각하는 이진탐색트리(BST)에 관한 문제는: BST가 어떤 경우에서든 균일한 성능을 보이도록 최적화(AVL, Splay) BST의 높이, 노드 개수 등에 관한 수학적인 탐구 BST를 어떻게 응용할 수 있는가(허프만 인코딩) ..뭐 이런 문제들이다. 근데 이번에는 다루는 문제의 결이 조금 다르다. "각 노드들에 대한 방문횟수가 모두 정해져 있을 때, 탐색횟수가 가장 작은 형태의 BST는 무엇인가?" 즉, 이번에는 BST를 최적화한다기보다도 이론상으로 가장 최적인 BST가 무엇인지, ..
유클리드 호제법 알고리즘의 시간복잡도 예측하기 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. 레이지에 여러 가지 연산 합치기 보통 어려운..

티스토리툴바