참고 : https://blog.kiwiyou.dev/ps/rust-ps-tips/ 1. 숫자만 줄바꿈, 스페이스 등으로 구분되게 입력 후 출력 예제 : https://www.acmicpc.net/problem/10950 test case 5 1 1 2 3 3 4 9 8 5 2 2 5 7 17 7 code 2. 테스트케이스 (숫자) 마다 string 다루기 예제 : https://www.acmicpc.net/problem/8958 test case 5 OOXXOXXOOO OOXXOOXXOO OXOXOXOXOXOXOX OOOOOOOOOO OOOOXOOOOXOOOOX 10 9 7 55 30 code 3. 입력된 값 벡터로 처리 예제 : https://www.acmicpc.net/problem/1032 tes..
https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 제한 시간을 10초나 주길래 별 생각 없이 풀다가 낭패를 본 문제입니다. 처음 생각했던 방안은 놓일 수 있는 모든 위치에 대해서 하나씩 놓아보면서 현재 최대값 결과인 result >= 현재까지 놓인 개수 res + 뒤에 남은 1인 칸 이면 탐색을 종료하도록 구성하였습니다. 하지만 이렇게 구성하니 시간초과가 떴고, 해당 방법을 이용하면 복잡도가 O(2^(N*N)) 임을 알게 되었습니다. 이를 해결하기 위해 ..
https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 노란색 칸은 배양액을 뿌릴 수 있는 위치, 흰색은 배양액을 뿌릴 수는 없지만 퍼질 수 있는 위치, 파란색은 호수로 이루어져 있습니다. 이 때 빨간색 배양액과 초록색 배양액을 모두 뿌렸을 때 (겹치게 뿌리면 안 됨) 동시에 만나는 지점에서 꽃이 피고, 이 때 꽃의 최대 개수를 구하는 문제입니다. 전체 칸이 50x50, 배양액 개수가 최대 5..
Crystals-Dilithium 리뷰
NIST PQC round 3까지 통과한 서명 스킴인 dilithium 논문 리뷰를 해봅니다. PQC, lattice를 위주로 연구하는 중은 아니어서 security 관점이나 이런 부분은 잘 모르기 때문에 생략하도록 하고, 전체적으로 스킴이 어떻게 구성되어 있는 지 위주로 살펴보겠습니다. dilithium 의 최종 페이퍼는 아래 링크에서 확인하실 수 있습니다. Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehlé - CRYSTALS-Dilithium, Algorithm Specifications and Supporting Documentation, 2..
https://www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 간단한 dp 문제였지만 아이디어 떠올리기는 좀 힘들었습니다 dp[i][j] : i ~ j까지 부분 배열에 팰린드롬을 만들기 위해 필요한 최소 개수라 하면 입력된 배열을 arr 이라 할 때 arr[i] = arr[j] 이면 i, j 번쨰 값이 같으므로 i+1, j-1 번째까지 배열로 팰린드롬을 만드는데 필요한 개수와 같습니다. 그리고 arr[..