복습용 블로그

www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 거친 제목의 문제 이름에 이끌려 들어가보았지만, 쉬운 문제였습니다. (그렇지만 틀렸었다.) 듣도 못한 사람을 listen 벡터에 넣었습니다. 처음에는 listen 벡터 외에 see 벡터를 추가하여 보도 못한 사람들의 벡터를 만들어 이분 탐색을 진행하였지만, 시간 초과가 났습니다. (시간 초과가 이것 때문은 아니고, 처음에는 이분 탐색 알고리즘을 직접 구현했었지만, 시간초과나서 그냥 algorithm 라이브러리..

지난 번 포스팅에서 CPA를 이용하여 주어진 암호화된 hwp 파일을 복호화하였습니다. 해당 hwp파일은 다음과 같습니다. (아래 hwp 파일은 복호화 후 제가 글씨체와 글씨 크기를 변경한 것입니다. 실제 복호화된 hwp 파일은 글씨체와 크기가 다를 수 있습니다.) 열심히 주어진 문제를 푸니 또다른 문제가 나왔습니다. 하지만 위 문제는 저도 ecdsa에 대해 잘 모르던 때였지만, 이틀 만에 풀었을 정도로 어렵지 않은 문제입니다. 1. 문제 접근 위 문제는 ECDSA를 이용한 전자서명 문제입니다. 우선 ECDSA에 대해 간략히 소개하면 다음과 같습니다. ECDSA는 ECC 알고리즘을 이용한 전자서명입니다. ECC란 타원곡선 알고리즘에 기반한 공개키 암호 방식입니다. 타원곡선(elliptic curve)이라하..

출처 : cryptocontest.kr/ Home - SEC연구소 | 암호분석경진대회 cryptocontest.kr 문제 해결을 위한 첨부파일이 있지만 용량 문제로 업로드 하지 않았습니다. SEC 연구소 홈페이지에서 다운 받아주세요. 또한 문제에 문제 해결을 위한 오픈 소스가 올라와있지만, 구 버전 matlab이라 최신 버전 matlab에서 호환 되지 않는 점 참고 바랍니다. (저는 그냥 python으로 직접 짜서 풀었습니다. 이 문제도 변수 이름 등을 너무 중구난방으로 잡아서 정리가 된 후 깃헙에 올리도록 하겠습니다.) 여름 동안 머리를 싸매고 풀었던 4번 부채널분석문제입니다. 문제 해결을 위해 첨부파일을 풀면 hwp.encrypted 파일과 PowerConsumption.csv 파일을 얻을 수 있습니..

www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 단순히 계산하면 n개의 숫자 사이에 n-2 개의 +, - 가 존재합니다. (마지막 부호는 = ) 그러므로 $O(2^n)$ 이지만 n=100이므로 시간초과가 날 게 뻔해보입니다. 그러므로 DP를 이용해 봅시다. 상근이는 0~20까지의 숫자만 알고 있으므로 possible 배열을 이용하여 0~20에 다음 숫자를 계산했을 때 가능하면 dp 경우를 더해줍니다. 그 값을 dp배열에 복사하여 dp배열 내에서 0보다..

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 삼성 SW 기출문제로도 유명한 아기 상어 문제입니다. 상어 위치로부터 문제로부터 요구하는 물고기의 위치까지 최단 거리를 구하여 계속 더하면 되므로 bfs를 사용하였습니다. 처음에는 상어의 현재 위치에서 $n^2$개 중 먹을 수 있는 물고기를 체크하고, 이 물고기들을 bfs를 이용하여 최단 거리와 어떤 물고기를 먹을 지 구한 뒤 while문으로 동일하게 반복하였습니다. 그러니 $O(n^6)$이 되어 시간초..