-
암호학의 안전성 증명 테크닉
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$...
-
Introduction to Width Independent MWU
Introduction to Width Independent MWU 네트워크 플로우는 효율적인 그래프 알고리즘을 고안하기 위한 기초적인 도구이다. 이미 글을 통해서 여러 번 밝힌 바가 있지만 이 분야에 대해서 수도 없이 많은 연구들이 진행되었고, 최근 Almost-Linear Time Minimum Cost Flow 가 가능하다는 사실이 알려져서 많은 화제를 모은 바도 있다. 이론적으로는 효율적인 네트워크 플로우 알고리즘에 대한 연구가 상당히 진전이 되어 있지만, 정확하게 네트워크 플로우 문제를 해결하려는 경우는 아직 Push-relabel보다 실용적인 방법이 잘 알려져 있지 않다. 이론적으로 효율적인 플로우 알고리즘은, 그...