-
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가...
-
암호학의 안전성 증명 테크닉
1. Introduction 안녕하세요, 이번 글에서는 암호학에서 특정 구조에 대한 안전성을 증명하는 테크닉을 알아보겠습니다. 이 테크닉을 통해 실제 Feistel cipher의 안전성을 증명해볼 것입니다. 2. 암호학의 안전성 암호학의 안전성에 대해서는 지금으로부터 대략 1년 전에 이미 포스팅을 한 적이 있습니다. Indistinguishability(구분 불가능성)이라는 용어를 처음 들어보신다면 해당 포스팅을 먼저 확인해보시는걸 추천드립니다. 이전 글에서도 언급했듯 Indistinguishability는 달성이 굉장히 어려운 성질입니다. 또한 만약 어떤 암호 체계가 랜덤한 메시지와 구분 불가능하다는건 공격자의 입장에서 그 어떤 방법으로 공격을 시도하더라도 아무런 의미있는 정보를 얻을...
-
Casual Inference and Diagram
Introduction Simpson’s Paradox 한 제약회사가 어떤 질병에 대해 치료제를 개발한 후 이 치료제가 실제로 효과가 있는지 700명의 환자들을 대상으로 실험을 진행하였다. 환자들의 3개월간 회복 경과를 지켜본 결과 아래와 같이 나타났다. 치료제 사용 치료제 미사용 남성 81/87 회복 (93%) 234/270 회복 (87%) 여성 192/263 회복 (73%) 55/80 회복 (69%) 합산 273/350 회복 (78%) 289/350 회복 (83%) 각각의 성별에 대해서는 분명 치료제를 사용한 경우에 더 회복률이 높았지만, 합산 회복률은 치료제를 사용하지 않았을 때 오히려 더 높게...
-
알고리즘 문제 접근 과정 9
알고리즘 문제 접근 과정 9 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 짐 정리 - KOI 2007 지역본선 중등부 4번 풀이 문제를 간략화하기 위해, 짐들을 옮길 때 드는 힘을 생각하지 않고, 최소 몇 번 만에 짐을 옮겨 정렬할 수 있는지 위 그림을 예시로 확인해봅시다. i)...
-
실무에서 빠르게 LCS를 계산하는 실용적인 Hunt-Szymanski 알고리즘에 관하여
개요 두 문자열의 가장 긴 공통 부분문자열을 찾는 Longest Common Subsequence (LCS) 문제는 정보과학에서 기초가 되는 잘 알려진 문제이다. 이렇게 기초적임에도 불구하고, LCS 문제는 생물정보학이나 전산언어학, 그리고 실생활에서 자주 사용하는 검색 엔진 등 다양한 학문과 분야에서 활용되는 아주 중요한 문제이다. 길이가 각각 $L_1, \cdots, L_N$인 문자열 $N$개의 LCS는 다이나믹 프로그래밍 기법을 이용하여 $\displaystyle \mathcal{O} \left( N \prod _{k=1}^{N} L _k \right) $의 시간 복잡도로 해결할 수 있음이 잘 알려져 있다. 본 글은 길이 $N$, $M$...