분류 전체보기 (6) 썸네일형 리스트형 공개 키 암호 공캐 키 암호 방식은 한 쌍의 키 즉, 공개 키 (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 [BOJ] 1348번: 주차장 문제 정의 백준1348 풀이 BFS를 통해 각 차에서 각 주차장까지의 거리를 구한다. 어떤 매칭이 주어졌을 때 모든 차량이 주차장에 주차하는 시간은 해당 매칭에서 거리가 가장 먼 차와 주차장 사이의 거리와 같다. 따라서 차와 주차장을 길이가 각 차와 주차장 사이의 거리와 같은 간선으로 연결한 이분 그래프를 만든 후 길이가 $L$ 이하인 간선들만을 이용하여 이분 매칭 문제를 풀면 된다. 이분 탐색을 통해 완전 매칭이 되게 하는 가장 작은 $L$값을 찾으면 된다. 구현 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172.. [BOJ] 1126번: 같은 탑 백준 1126 풀이 $n$개의 블록이 있고, 각각의 높이가 $h[i]$ ($0\le i \le n-1$) 일 때 $dp[i][j] :=$ 두 탑 사이의 높이 차이가 $i$일 때, $j$ 번째 블록부터 사용하여 만들 수 있는 높이가 같은 2개의 탑의 높이의 최댓값. 만약 높이가 같은 탑을 만들 수 없는 경우 $-\infty$ $$dp[i][j]= \begin{cases} 0 & \mbox{if } i=0\land j=n. \cr -\infty & \mbox{if }i>\lfloor\sum_{k=0}^{n-1} h_{k}/2\rfloor\lor j=n. \cr max(dp[i][j+1], dp[i+h[j]][j+1], h[j]+dp[i-h[j]][j+1]) & \mbox{if } h[j]\le i. \cr .. [BOJ] 1023번: 괄호 문자열 문제 정의 빈 문자열은 괄호 문자열이다. $S$가 괄호 문자열일 때, $(S)$도 괄호 문자열이다. $S$와 $T$가 괄호 문자열이라면, $ST$도 괄호 문자열이다. 모든 괄호 문자열은 위 규칙으로만 만들어진다. 이 문제에서는 괄호 문자열이 아닌 문자열이 나온다. 만약 문자열이 '('와 ')'로만 이루어져 있고, 괄호 문자열이 아니라면, 그 문자열을 괄호ㄴㄴ문자열이라고 한다. 길이가 $n$인 괄호ㄴㄴ문자열 중에 사전순으로 $k$번째인 문자열을 출력하는 프로그램을 작성하시오. 그러한 것이 없으면 $-1$을 출력한다. '('가 ')'보다 사전순으로 앞선다. ( $0 ≤ n ≤ 50 , 0 ≤ k ≤ 2 n − 1$ ) 풀이 17428번: K번째 괄호 .. [BOJ] 17428번: K번째 괄호 문자열 문제 정의 빈 문자열은 괄호 문자열이다. $S$가 괄호 문자열일 때, $(S)$도 괄호 문자열이다. $S$와 $T$가 괄호 문자열이라면, $ST$도 괄호 문자열이다. 모든 괄호 문자열은 위 규칙으로만 만들어진다. 길이 $n$인 괄호문자열 중 사전 순으로 $k$번째 괄호문자열을 출력하는 프로그램을 작성하시오. 사전순으로 가장 앞서는 괄호 문자열은 0번째이다. 그러한 것이 없을 때에는 $-1$을 출력한다. ( $0 ≤ n ≤ 50 , 0 ≤ k ≤ 2 n − 1$ ) 풀이 $dp[i][j]$ := '(', ')'으로 이루어진 길이 $n$인 문자열을 만들 때 앞으로 추가해야 할 문자열의 길이가 $i$이고, 현재까지 만든 문자열 안에 '('의 개수가 ')'.. 이전 1 다음