-
특별한 정렬 알고리즘들
개요 정렬(Sorting)은 알고리즘 문제 풀이뿐 아니라, 어떤 분야의 프로그래밍을 하면서도 수없이 마주치는 문제입니다. 일반적으로 정렬에 대해 공부할 때는 $O(N^2)$이지만 기본 개념을 설명하기 위해 배우는 버블 정렬(Bubble sort), 삽입 정렬(Insertion sort), 선택 정렬(Selection sort) 등과, 보다 효율적으로 $O(NlogN)$ 시간에 해결해주는 퀵정렬(Quicksort), 병합 정렬(Merge sort), 힙정렬(Heapsort), 그리고 비교 기반이 아닌 자릿수(digit) 기반으로 $O(N)$에 해결하는 기수 정렬(Radix sort), 카운팅 정렬(Counting sort) 정도를 배우게 됩니다. 굉장히 많은 종류의 정렬을 배운 것 같지만, 정렬에 대해 더 깊이 파고 들어가보면 이...
-
최소 외접원 찾기
서론 최소 외접원 문제는, 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가 아닌 그래프의...