NOTE (2) 썸네일형 리스트형 공개 키 암호 공캐 키 암호 방식은 한 쌍의 키 즉, 공개 키 (public key)와 비밀 키 (private key)를 사용하는 암호 방식의 한 종류이다. 어떤 공개 키 A와 비밀 키 B가 쌍을 이루고 있을 때, A로 암호화한 메시지는 B로만 복호화 할 수 있고, 반대로 B로 암호화한 메시지는 A로만 복호화 할 수 있는 성질을 가진다. 공개 키 암호화 방식으로 Alice가 Bob에게 비밀 메시지를 보내는 상황을 가정해보자. 메시지의 전달은 다음과 같은 순서로 진행된다. Bob은 공개 키와 비밀 키를 생성하고 공개 키를 공개한다. Alice는 메시지를 작성 후 Bob의 공개 키를 이용하여 암호화 한다. 암호화 한 메시지를 네트워크를 통해 전달한다. Bob은 자신의 개인 키를 이용하여 암호화된 메시지를 복호화 한다. .. DP optimization: Alien's trick 이 주제를 다루고 있는 문서가 몇 있지만, 개인적으로 이해하는데 애를 먹어서 정리해둔다. 내용의 전개는 구사과님 블로그와 같다. 다음과 같은 문제가 있다고 하자. 양의 정수로 이루어진 수열 $v[i]$ ($1\leq i \leq n$)을 연속된 항들을 포함하는 여러 개의 구간으로 나눈다. $i$ 번째 부터 $j$번째 항을 포함하는 구간의 비용이 $c[i][j]$ 라고 할 때 전체 수열을 $m$개의 구간으로 나누는 최소 비용은 얼마인가? (단, $c$는 monge array이며, 모든 $c[i][j]$는 정수이다.) 수열의 $j$번째 항 까지를 $i$개의 구간으로 나누는 최소 비용을 $dp[i][j]$ 으로 나타내자. 이때 점화식은 다음과 같다. $$dp[i][j]=\min_{k 이전 1 다음