-
더 빠른 문제 풀이 코드를 위한 상수 줄이기 2
개요 지난 글에서는 문제 풀이에 있어 상수가 가지는 의미와, 상수 차이에 의해 현저히 드러나는 퍼포먼스의 차이를 몇 가지 실험을 통해 보았습니다. 먼저 입출력 방법에 따라 수십 배 이상도 차이가 벌어질 수 있음을 보았고, std::set과 같이 Red–black tree를 쓰는 자료구조는 std::priority_queue에 비해 같은 연산을 하더라도 훨씬 느리다는 것을 보았습니다. 또한 광범위한 영역의 메모리를 빠르게 특정 값으로 채우거나, 복사하거나, 옮기는 데에는 1바이트씩 반복문을 통해 수행하는 것보다 memset, memcpy, memmove 등의 함수를 사용하는 것이 월등히 빠르다는 것도 살펴보았습니다....
-
Judger와 Express를 이용한 채점 서버 구현 후기
목차 1. 개요 2. Judger 3. Express 서버 구현 4. 테스트 5. 후기 개요 채점 서버는 OJ(Online Judge)를 만들때 제일 핵심적인 기능입니다. 학교 졸업 프로젝트의 일환으로, 프로그래밍 학원 선생님한테 유용하게 쓰일법한 웹 어플리케이션을 구상하는 과정에서 OJ의 채점 기능이 반드시 필요하게 되었습니다. 이번에 구현한 채점 서버는 Node.JS의 Express 기반 채점 서버입니다. 클라이언트로부터 소스코드를 받을 때, 시스템 콜 혹은 메모리 오버플로, 버퍼 오버플로등의 문제에서 발생할 수 있는 보안적 이슈를 해결하기 위하여 칭다오 대학에서 만든 OJ에서 SECCOMP기반의 Judger를...
-
Wavelet Tree
Wavelet Tree란? Wavelet tree란, 문자열을 저장하는 자료구조입니다. 이진 트리 형태로, 문자열의 길이 $L$에 대해 $L + o(L)$의 메모리를 사용하여(이런 특성이 있는 자료구조를 간결한 자료구조(succinct data structure)라고 합니다) 아래 두 연산을 지원합니다. $\mathbf{rank}_c(x)$: 문자열의 첫 인덱스부터 $x$번째 인덱스까지 문자 $c$가 등장하는 횟수를 반환합니다. $\mathbf{select}_c(x)$: 문자 $c$가 $x$번째로 등장하는 인덱스를 반환합니다. Wavelet이라는 이름은 신호를 재귀적으로 저주파수와 고주파수로 나누어 분해하는 wavelet transform의 이름에서 가져왔습니다. Wavelet tree의 구조 이 문단에서는 일반적인 wavelet tree의 개략적인 구조만을 다룹니다. 구조를 이해하셨다면 다음...
-
Karger's Algorithm
안녕하세요? 저는 이번 글에서 Global Minimum Cut을 찾는 Karger’s algorithm에 대해 설명해보려고 합니다. Introduction 그래프를 두 집합 $S$, $T$로 나누는 것을 그래프의 cut이라고 합니다. 간선에 weight가 있는 그래프에서, 두 점 $s$와 $t$가 주어졌을 때 $s \in S$, $t \in T$를 만족하도록 그래프를 cut하는 상황을 생각해봅시다. 한 쪽 노드는 집합 $S$에, 다른 한 쪽은 $T$에 포함된 모든 edge들의 weight의 합을 cut의 크기라고 합니다. 이 때 크기가 가장 작은 최소 cut은 최대 유량과 같다는 사실(Min-cut Max-flow theorem)은...
-
Smooth number and Factorization
서론 이번 HITCON CTF 2019 Quals에서 안타깝게 14등으로 본선을 진출하지 못하게 되었습니다. 결과 링크 아쉬운 부분은 푼 팀이 적은 암호학 문제들을 풀지 못했다는 건데, 그 중 한 문제가 소인수분해와 관련이 있어 이번 포스팅을 작성하게 되었습니다. RSA 위에서 말한 문제는 Lost Key Again이라는, RSA와 관련된 문제입니다. RSA에 대해서 간편하게 살펴보자면, $a \equiv b (\mathbb{mod}\ c)$는 $a$를 $c$로 나눈 나머지와 $b$를 $c$로 나눈 나머지가 같다는 뜻으로 이해할 수 있습니다. 편의상 $a$를 $b$로 나눈 나머지를 $a (\mathbb{mod}\ b)$로...