-
최소 외접원 찾기
서론 최소 외접원 문제는, 2차원 평면 상에 점이 $N$개가 있을 때, 이들을 모두 담는 최소 반지름의 원이 과연 무엇인지를 찾는 문제입니다. 실생활에서 굉장히 많이 사용될 수 있는 문제이며, 예를 들면, 어떤 도시에 기지국을 지어야 하는데, 어느 곳에 지어야 송신소를 모두에게 도달하면서, 최소한의 반지름으로 모든 송신소를 덮을 수 있는 지 등, 효율적인 배치에 관한 문제입니다. 이 게시글에서는 이 문제를 $O(N)$에 푸는 방법을 소개 합니다. 담금질 기법 담금질 기법은, 원래는 모든 최적화 문제에 사용되는 기법입니다. 담금질 기법은,...
-
차분 공격의 이해
개요 차분 공격(Differential Cryptanalysis, 줄여서 DC라고 부르기도 함)는 선형 공격(Linear Cryptanalysis)와 더불어 블럭 암호를 공격하는 아주 강력한 공격 기법으로, 1991년 Eli Biham과 Adi Shamir(RSA을 만드신 그 분입니다!)에 의해 처음 논문으로 제시되었습니다. NSA는 차분 공격을 1974년부터 인지하고 있었고 DES를 설계할 때 차분 공격으로부터 최대한 안전하게끔 만들었다고 추후에 밝혔습니다. DES의 예시와 같이 비록 현대에 들어서는 블럭 암호를 설계할 때 차분 공격에 안전하게끔 설계를 하지만, Higher-order differential cryptanalysis, Truncated differential cryptanalysis, Impossible differential cryptanalysis, Boomerang attack과 같이 다양한...
-
O(1) LCA Algorithm (with Sparse Table)
목표 및 문제 소개 LCA(Lowest Common Ancestor)란 루트가 정해진 트리에서, 두 노드 간의 공통 조상이면서 루트에서 가장 먼 노드를 뜻합니다. 노드가 $N$개인 트리에서 임의의 두 노드 간의 LCA를 쿼리당 $O(lgN)$에 구하는 알고리즘은 잘 알려져 있습니다. 각 노드별로 $ 2^k $ 번째 조상을 미리 계산해둔 뒤, Binary Lifting을 활용해 구하는 방식입니다. 이에 대한 지식이 부족하다면 링크 에서 먼저 공부한 뒤에 이 글을 읽으시는 것을 추천합니다. 이 글에서 소개하고자 하는 알고리즘과 밀접한 관련은 없지만, 전반적인 개념에 도움이...
-
Perfect Elimination Ordering in Chordal Graph
개요 Chordal Graph Chordal Graph란, 길이 4 이상의 모든 simple cycle이 chord를 포함하는 그래프를 말한다. 여기서 chord란 cycle에 포함되는 edge는 아니지만 cycle에 포함하는 두 vertex를 잇는 edge를 뜻한다. 즉, 어떤 4개 이상의 vertex를 고르더라도 그 vertex들로 이뤄진 induced subgraph가 simple cycle이 되지 않는 그래프이다. 두 겹치는 구간을 edge로 연결한 Interval graph가 Chordal graph의 한 예이다. 위는 chordal graph의 예이다. 임의의 길이 4 이상인 cycle이 chord를 포함함을 쉽게 알 수 있다. 위는 chordal graph가 아닌 그래프의...
-
Manacher's Algorithm
목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학기가 시작되어 모든 알고리즘들을 한번씩 보면서 넘어가던 도중 사람들이 잘 관심 가지지 않지만, 알아두면 재미있을법한 알고리즘인 Manacher’s Algorithm 을 소개해보고자 한다. Manacher’s Algorithm은 String 내에 존재하는 모든 Palindrome을 $O(N)$에 구하는 강력한 알고리즘이다. 물론 이 알고리즘이 실전에 출제되는 경우는 매우 드물지만 원리 자체가 재미있고 시간복잡도가 $O(N)$이 되는 원리가 재미있는 알고리즘이므로 자세하게 설명해보고자 한다. 팰린드롬 팰린드롬을 모르는 사람을 위해 간단히...