Boruvka’s MST Algorithm 프림, 크루스칼보다는 느리다. O(mlogm) 모든 노드는 가장 작은 인접엣지를 고른다. 가장 작은 인접엣지는 항상 MST에 들어간다. a→b가 들어가지 않는다면 a→c→b와 같이 다른 엣지를 경유해서 들어온 것이 된다. 그러나 a→b 가 가장 작은 웨이트라면 그냥 a→c→b 대신에 a→c, a→b를 하면된다. 따라서 가장 작은 인접엣지는 항상 MST에 들어간다. 그러면 컴포넌트가 생긴다. 만약 두 노드가 고른 엣지가 겹치면, 전체 그래프는 분리되서 여러개의 컴포넌트가 생길 수도 있다. 최악의 경우 n/2 개 생긴다. (노드 2개씩은 무조건 연결되서 컴포넌트가 생기므로) 따라서 알고리즘을 그 상태로 다시 시도한다. (이부분 때문에 프림과 크루스칼보다 느리다.) ..

Lowest Common Ancestor LCA 노드 a와 b의 공통 조상중 제일 최소 찾기. logn 모든 노드가 자신의 부모, 조상, … 을 전부다 가지게 하자. A[i][j] 를 계산하면 된다. A[i][j] : 노드 i에서 위로 2^j 만큼 올라간 노드의 번호. 즉, A[i][0] 은 노드 i의 부모이다. 만약 A[i][j] = k가 있다고 가정하면 A[i][j+1] = A[k][j] 이다. (직접 그려서 확인해보면 맞다는 걸 알 수 있다.) A 배열의 크기가 i는 1~n 이고, j는 0~logn 이므로 전체 배열의 값을 작성하는데 nlogn이 걸린다. ⇒ 모든 조상노드를 자유롭게 순회할 수 있다. 이후 LCA를 구한다. 만약 a가 b보다 위에 존재한다면 a의 링크를 따라서 b와 같은 레벨의 a’..

Primality Test (Monte Carlo) n이 소수인가? 페르마 정리 1. 8377이 소수라면, 모든 a에 대하여 a^8376 = 1 mod 8377 이다. 2. 8377이 소수가 아니라면, 어떤 a에 대하여 a^8376 ≠1mod8377 이다. 이때 1

Linked List in an Array (Las Vegas) 링크드 리스트에서 x 찾기 기존 링크드 리스트는 O(n) 1. 배열에서 루트n개를 랜덤하게 고른다. 2. 골라진 애들중 X보다 작은애들을 고른다. 3. 작은 애들중 가장 큰 애 Y를 고른다. 4. Y의 링크를 타면서 간다. 기댓값 계산 및 검증 배열에서 k개를 골랐다고 가정했을 때 O(k + f(n, k))가 걸린다. f(n, k) 는 Y와 x 사이의 거리가 d일 확률의 기댓값이다. P[D=d] = P[D≤d] - P[D≤d-1] 이므로 =((n-d)/n)^k - ((n-d-1)/n)^k 따라서 기댓값 f(n, k) = sigma_{d=1}^{n} d * P[D=d] 이다. 즉, k + f(n, k) = k + n/(k+1) 이므로 대략 k..

Las Vegas 답은 항상 나오지만, 시간이 랜덤 Monte carlo 답이 랜덤이지만, 시간이 항상 일정 Las vegas → Monte carlo 그냥 시간되면 짜르면된다. 그때까지 답 나왔으면 나온거고, 안나왔으면 안나온거고. Monte Carlo → Las vegas 답 안나왔으면 다시 돌린다. 답 나올때까지.. Randomized QuickSort Pivot을 매번 랜덤하게 결정하기. 기존에는 특정입력에 대하여 항상 최악의 경우 O(n^2) 이지만 랜덤 quicksort는 모든 입력에 대하여 낮은 확률의 최악의 경우가 발생 가능. 따라서 특정 입력을 계속 사용해야만 하는 경우에 효과적인 알고리즘.