-
Tweakable block ciphers
1. Introduction 안녕하세요, 이번 글에서는 Moses Liskov, Ronald L. Rivest and David Wagner가 작성한 Tweakable Block Ciphers(링크) 논문을 주제로 정했습니다. 참고로 저자중 2번째에 위치한 Ronald L. Rivest는 RSA의 R입니다. 이 논문에서 최초로 Tweakable Block Ciphers라는 개념을 제안했고 이후 Tweak이라는 개념은 대칭키 분야에서 중요하게 쓰이고 있고 최근까지도 관련된 논문이 계속 제시되고 있습니다. 진정한 대가들은 학문에서 새로운 방향성을 제시한다고 하는데 이 논문이 딱 그런 상황에 걸맞는 논문이 맞지 않나 하는 생각이 듭니다. 이번 글을 통해 Tweakable block...
-
Sum over Subsets (SOS) DP
이번 글에서는 다이나믹 프로그래밍으로 Sum over Subsets (SOS) 문제를 푸는 방법을 대해 소개하겠습니다. SOS DP는 Codeforces에서 중상급 난이도의 문제로 종종 출제되는 흥미로운 테크닉이지만, 지금껏 한국어 자료를 찾아보기 어려웠기 때문에 SOS DP를 소개하는 Codeforces 블로그 글의 구성을 참고해서 한국어 소개글을 작성해 보았습니다. 또한 기존 글에서 한발 나아가서 어떤 직관을 통해 SOS DP를 이해할 수 있는지도 소개하려고 합니다. 이 글에서는 다음과 같은 표기를 사용할 것입니다. 비트마스크를 집합처럼 취급합니다. 예를 들어, $1101_{(2)} = 2^0 + 2^2 + 2^3$은...
-
Push Relabel Algorithm (2)
2월의 Push-Relabel algorithm 관련 글에 이어서 Push-relabel에 기반한 다항 시간 MCMF 알고리즘 (Cost Scaling)에 대해서 다룰 예정이다. 이 글에서는 일반적으로 알려진 Successive Shortest Path Algorithm보다 훨씬 더 효율적인 알고리즘을 다룬다. MCMF (Minimum-Cost Maximum-Flow) 문제는 알고리즘 대회 입문서에 다 소개되어 있는 중요한 문제이다. 2월 중순에 글이 올라온 뒤, 3월 1일 Almost-Linear Time Minimum Cost Flow 가 가능하다는 사실이 알려져서 많은 화제를 모았다. 당연하지만 이론전산에서 아주 중요한 연구 결과이고, 저자들은 아마 권위있는 상 하나 정도는 수상하지 않을까...
-
Finite Nimber 계산
Aeren 님의 Nimber 포스트에서도 알 수 있듯이 $2^{2^k}$ 미만의 음이 아닌 정수는 nimber 덧셈(xor)과 nimber 곱에 대해서 체를 이룹니다. 이 글에서는 finite nimber에 대해서 nimber 곱, 제곱근, 곱셈 역원 등을 실제로 계산하기 위한 알고리즘을 소개합니다. https://www.ics.uci.edu/~eppstein/numth/를 참고했습니다. 기본 규칙 이 파트에서 소개하는 성질을 포함해서 앞으로 nimber의 몇가지 성질을 증명하지 않고 주어진 것으로 받아들이도록 하겠습니다. Nimber는 체를 이루므로 덧셈, 곱셈에 대해서 교환 법칙, 결합 법칙, 분배 법칙 등이 성립합니다. 따라서 앞으로 표기에서 불필요한 괄호를 생략하고, 곱셈은...
-
Vision Transformer (1)
들어가며 현재 컴퓨터 비전에서 가장 뜨거운 주제 중 하나는 vision transformer (ViT) 이다. 2017년에 발표되었지만 벌써 4만 번 가까이 인용된 [](https://arxiv.org/pdf/2010.11929.pdf) 논문 이후 본래 자연어처리를 위해 고안된 transfomer를 컴퓨터 비전에 사용하기 위한 연구가 이루어졌고, 2021년 ICLR에서 Google Brain 팀이 [<An Image Is Worth 16X16 Words: Transformers for Image Recognition at Scale>](https://arxiv.org/abs/2010.11929)라는 제목으로 ViT를 발표하면서 ViT를 image recognition, object detection, image restoration 등 수많은 컴퓨터 비전의 태스크에 적용한 연구가 쏟아져 나왔다. ViT를 소개하기 앞서 오늘은 transformer가...