복습용 블로그

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 새로 이사 온 곳에 친구가 없어서 풀어 본 문제입니다 ㅠㅠㅠ 문제는 간단합니다. 친구의 친구도 친구로 치는데 이 때 무리들에게 최소 얼마를 줘야 모두 친구가 될 수 있는 지 문제입니다. 먼저 친구 그래프를 만든 뒤, dfs 로 해당 그래프에서 가장 작은 친구비를 요구하는 친구들만 골라 합을 구하면 됩니다. 만약 k보다 합이 크면 Oh no 입니다.

요즘 go 문법 공부 중인데 slice를 처음보고 파이썬 리스트랑 비슷하다 생각했지만 개념적으로 좀 다른 부분이 있어 기본적인 slice 개념을 정리를 하고자 한다. 1. 배열과 슬라이스 차이 배열 : 정적 할당 슬라이스 : 동적 할당 인 줄 알았는데 조금 다르다. 슬라이스의 구조는 다음과 같다. (reflect.SliceHeader) type SliceHeader struct { Data uintptr Len int Cap int } Data : 슬라이스가 가리키는 배열의 시작 포인터 Len : 슬라이스의 길이 Cap : 슬라이스의 capacity 이 구조로 인해 어떤 경우에는 슬라이스 간에 영향이 생기고 어떤 경우에는 영향이 안 생긴다. (밑에서 설명) 그리고 슬라이스는 해당 배열을 가리키는 포인터를..

고려대 정보보호대학원 2022학년 전기 석사 신입생으로 입학하게 되었습니다. 컨택한 연구실 랩장 형님께서 공부해오라고 하신 blind signature 내용을 간단히 정리하겠습니다. https://sceweb.sce.uhcl.edu/yang/teaching/csci5234WebSecurityFall2011/Chaum-blind-signatures.PDF David Chaum이 1983년 발표한 blind signature는 서명하는 사람이 서명하는 내용이 어떤 것인지 모르게하기 위한 것입니다. 논문 원본 내용을 그대로 빌려 쓰자면, "어음과 같은 익명 지불 시스템은 통제와 보안에 취약하다. 지불에 대한 증명 부족과 훔쳐진 것인지, 암시장에 의한 것인지 등의 문제가 있다." 로 표현합니다. (지금은 은행 ..

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 와 같은 그래프가..