-
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보다 실용적인 방법이 잘 알려져 있지 않다. 이론적으로 효율적인 플로우 알고리즘은, 그...
-
라틴 직사각형과 홀의 결혼 정리
라틴 방진과 스도쿠 라틴 방진 (Latin Square)은 서로 다른 $n$가지 기호로 구성되며, 각 행과 열에 $n$가지 기호가 모두 한 번씩 등장하게 만든 $n\times n$ 행렬입니다. 편의를 위해 $n$가지 기호 대신 $1$부터 $n$까지의 수 배열이라고 생각합시다. 라틴 방진을 만드는 방법은 여러 가지가 있는데, 가장 간단하게 생각할 수 있는 방법은 다음과 같습니다. 첫 번째 행에 $1$부터 $n$까지의 수를 순서대로 적는다. $k$번째 행에는 $k-1$번째 행을 왼쪽으로 한 칸 회전한 배열을 적는다. $(2 ≤ k ≤ n)$ 왼쪽으로 한...