-
Web Worker-Postable 라이브러리 작성기
필자는 최근 Electron 플랫폼을 기반으로 한 오픈소스 영상 편집 프로그램을 만들고 있습니다. 프리미어 프로의 저질 짝퉁 버전이라고나 할까요. 웹 생태계의 특성상 새로운 기술들이 빠르게 적용되긴 힘들지만, 동시에 웹에 대한 많은 관심이 수년간 이어지면서 이에 대한 논의와 도입이 활발하게 이루어지고 있는것은 굉장히 즐거운 일이라고 생각합니다. 저같이 뭣도 모르는 녀석도 영상 편집 프로그램 같은걸 만들 생각도 할 수 있게 해주니까요. 이 프로그램에서 핵심이 되는 부분 중 하나는 OffscreenCanvas 이라는 기술입니다. 영상 편집 프로그램은 당연히 영상을 렌더링해서 보여주는...
-
빠른 다항식 나눗셈
들어가며 두 다항식의 곱셈에는 다양한 방법들이 있습니다. 항을 하나씩 곱해서 더하는 $O(N^2)$ 알고리즘부터, 분할 정복을 이용해 $O(N^{\log_2 3})$의 시간에 동작하는 카라츠바 알고리즘(Karatsuba algorithm), 빠른 푸리에 변환(Fast Fourier transform)을 이용해 $O(N \log N)$의 시간에 동작하는 알고리즘까지 다양합니다. 이 글에서는 다항식의 곱셈을 빠르게 하는 방법을 알고 있다는 것을 전제로, 다항식의 나눗셈을 빠르게 하는 방법을 소개하고, 얼마나 더 빠른지를 비교해 볼 것입니다. $O(N^2)$ 알고리즘 본격적으로 시작하기 전에, 빠른 다항식 나눗셈 알고리즘이 얼마나 빠른지를 비교해 보기 위해서 $O(N^2)$ 알고리즘을...
-
특별한 정렬 알고리즘들
개요 정렬(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과 같이 다양한...