Blind signature
고려대 정보보호대학원 2022학년 전기 석사 신입생으로 입학하게 되었습니다. 컨택한 연구실 랩장 형님께서 공부해오라고 하신 blind signature 내용을 간단히 정리하겠습니다. https://sceweb.sce.uhcl.edu/yang/teaching/csci5234WebSecurityFall2011/Chaum-blind-signatures.PDF David Chaum이 1983년 발표한 blind signature는 서명하는 사람이 서명하는 내용이 어떤 것인지 모르게하기 위한 것입니다. 논문 원본 내용을 그대로 빌려 쓰자면, "어음과 같은 익명 지불 시스템은 통제와 보안에 취약하다. 지불에 대한 증명 부족과 훔쳐진 것인지, 암시장에 의한 것인지 등의 문제가 있다." 로 표현합니다. (지금은 은행 ..
백준 11402 이항계수 4 C++
https://www.acmicpc.net/problem/11402 11402번: 이항 계수 4 첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수) www.acmicpc.net Lucas 정리라는 것을 새롭게 알게 된 문제입니다. Lucas 정리는 nCr % p (p : 소수) 를 쉽게 구할 수 있는 방법입니다. 일반적으로 공식을 이용하거나 ( nCr = n! / ((n-r)! * r!) ) dp 등을 이용해 풀 수 있습니다. (nCr = n-1Cr-1 + n-1Cr 이용한 dp) Lucas 정리는 mCn % p 를 다음과 같이 나타낼 수 있습니다. 여기서 m_i, n_i 는 다음과 ..
https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net SCC를 새롭게 공부할 수 있었습니다. SCC는 A, B, C, ... 노드가 방향 그래프로 주어져있을 때 어떤 노드끼리 순회할 수 있는지를 모아놓은 것입니다. 예를 들어 A->B, B->C, C->A 와 같은 그래프가 주어져있으면 A,B,C는 SCC 입니다. 그리고 A->B, B->C, C->A, A->D 와 같은 그래프가..
https://www.acmicpc.net/problem/11812 11812번: K진 트리 첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y www.acmicpc.net 처음에 k진 트리의 각 depth 별 마지막 노드가 k^n + k^(n-1) + ... + 1 번이 됨을 이용하여 각 노드의 부모를 찾은 뒤 그 부모 노드로부터 또다시 부모 노드를 찾는 방법을 시도하였지만 10% 정도 맞춘 뒤 시간초과가 계속 나와 다른 방법으로 풀었습니다. (생각하면 할 수록 무한루프 도는 구간이 발견되어 때려치웠다...
https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 처음에는 범위가 작은 순으로 먼저 책을 주려했는데 반례가 있다는 걸 깨달았습니다. 책을 원하는 사람들의 정보에 대해 끝 번호가 오름차순이 되면서 끝 번호가 같은 경우 범위가 오름차순이 되도록하면 됩니다. 이렇게 하면 될 거 같아서 해봤는데 맞았네요... 그리디 느낌으로 접근해서 풀이를 어떻게 해야할지 모르겠습니다.... 코드는 다음과 같습니다. #include #include #include #inc..