-
Li Chao Tree의 Lazy Propagation
개요 리차오 트리는 직선들을 관리하는 동적 세그먼트 트리의 일종으로, Convex Hull Trick 등등에서 쓰이는 자료구조입니다. 다른 세그먼트 트리와 마찬가지로 리차오 트리에도 레이지 프로퍼게이션을 적용할 수 있지만, 이에 대해서는 잘 알려져 있지 않습니다. 이 글에서는 리차오 트리에 레이지 프로퍼게이션을 적용한 확장 연산들과 그 활용에 대해 소개합니다. 리차오 트리 좌표 범위가 $N$일 때, 기본적인 리차오 트리는 다음과 같은 연산들을 할 수 있습니다. insert(a,b) : 새로운 직선 $y=ax+b$를 삽입한다. $O(\log{N})$ get(x) : 주어진 $x$좌표에서 $y$좌표의 최솟값을 구한다. $O(\log{N})$...
-
다양한 생성함수와 그 응용 (1)
개요 어떤 주어진 성질을 만족하는 것의 가짓수를 세는 문제를 연구하는 학문을 조합론이라 하며, PS 분야 뿐만 아니라 통계학, 수리물리학 등 다양한 분야에서 중요하게 다루어진다. 일반적으로, PS 분야에서 조합론 문제는 Dynamic Programming 테크닉을 이용하여 효율적으로 해결할 수 있다. 하지만, DP 수열을 정의하는 점화식을 알아내는 작업은 조합론의 영역이지만, 그렇게 정의된 DP 수열을 빠르고 효율적으로 계산하는 작업은 알고리즘의 영역에 속한다. 본 글은, 후자의 알고리즘 문제를 해결하는 좋은 방법에 대하여 수학적으로 기술한다. 점화식 형태로 정의된 수열이 주어질...
-
Ciphers for MPC and FHE
1. Introduction 최근의 두 포스트에서 Multi-party computation에 대해 다루었습니다. Garbled circuit의 발전사와 최종적인 형태를 보면 결론적으로 AND 연산의 수가 적으면 적을수록 MPC의 성능이 올라감을 알 수 있습니다. 또한 ZK(Zeroknowlege Proof, prover가 verfier에게 어떤 문장이 참임을 증명할 때 그 문장이 참이라는 것을 제외하면 그 어떤 정보도 prover에게 노출하지 않는 프로토콜),FHE(Fully Homomorphic Encryption, 데이터를 암호화한 상태로 연산할 수 있는 암호화 방법) 등에서도 AND 연산이 XOR 연산에 비해 훨씬 큰 비중을 차지합니다. 기존에 널리 쓰이는 암호화 알고리즘으로는 AES가...
-
헝가리안 알고리즘
안녕하세요? 오늘은 헝가리안 알고리즘(Hungarian Algorithm)에 대해 살펴보겠습니다. 헝가리안 알고리즘은 가중치가 있는 이분 그래프(weighted bitarted graph)에서 maximum weight matching을 찾기 위한 알고리즘입니다. 이분 그래프의 Matching M이 edge들의 부분집합이고, 모든 vertex들에 M에 속한 edge가 최대 한 개 연결되어 있을 때, 이러한 M을 그래프의 matching이라고 합니다. 일반적인 이분 그래프에서 최대 매칭은 최대 유량을 구하는 알고리즘을 통해 구할 수 있다는 사실이 잘 알려져 있습니다. Matching M의 weight는 M에 속한 edge들의 가중치의 합으로 정의할 수 있습니다. 이제 우리는 Matching 중...
-
Shortest Path Algorithm - Dijkstra
Dijkstra 다익스트라 알고리즘은 그래프에서 한 정점(시작 정점)에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘입니다. 여기서 최단경로란, 정점과 정점 사이를 잇는 간선이 가중치를 가지고 있을 때, 한 정점에서 다른 정점으로 간선을 타고 이동할 수 있는 경로중 가중치의 합이 가장 작은 경로를 말합니다. 다익스트라는 한 정점으로부터 다른 정점으로의 최단경로와 그 과정에서 거치는 간선들의 가중치 합을 알아낼 수 있습니다. 다익스트라는 알고리즘의 구조 상 다음과 같은 성질들을 가지게 됩니다. 그래프 내에 음의 가중치 합을 가지는 사이클이 있을 경우에, 다익스트라를 통한...