-
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)$로...
-
유용한 Github 관련 크롬 익스텐션 소개
안녕하세요! 제 이름은 taeguk입니다~ (갑자기?) 오늘은 가벼운 주제로 포스팅해보려고 합니다. 다들 github 많이 사용하실텐데요~ 오늘은 제가 사용하는 크롬 확장 프로그램들중에서 github 를 사용할 때 아주 유용한 것들을 소개해드리는 시간을 가져보려고 합니다^^ » 이 글을 좀 더 좋은 가독성으로 읽기 « 1. Refined Github 이거는 진짜 필수입니다!! 이 확장 프로그램은 github 웹페이지 자체를 아주 화끈하게(?) 바꿔버립니다! 정말 UI 가 더 예쁘고 사용성있게 변경되는데요. 그 외에도 다양한 기능들을 추가로 제공해줍니다. 예를 들면 다음과 같습니다. 아래 사진은 익스텐션...