-
C++ STL 컨테이너의 메모리 사용량 (1)
C++로 Problem Solving을 하는 사람도, 일반적인 프로그래밍을 하는 사람도 C++의 컨테이너는 매우 유용하게 사용합니다. 대표적인 예시가 동적 배열인 vector, 이진 탐색 트리인 set 등입니다. 이러한 자료구조를 적재적소에 사용하지 않으면 시간/공간 복잡도가 예상을 뛰어넘을 수 있습니다. 대표적인 예시가 “priority_queue가 set보다 빠르다”는 말입니다. 이는 일반적으로 사실이지만, 왜 그럴까요? 이와 관련된 질문에 답하기 위해 C++ 컨테이너가 메모리를 원소별로 얼마나 할당하고 그 이유는 무엇일지 gmem이라는 라이브러리를 통해 파트별로 알아보도록 하겠습니다. gmem 라이브러리 gmem은 동적으로 메모리를 할당할 때마다 로그를 남기고,...
-
2019 ACM-ICPC Seoul Regional 풀이
서론 2019년 2019년 11월 9일 토요일에 ACM-ICPC 서울 리저널이 진행 되었다. 대회에 대한 정보는 http://icpckorea.org 에서 찾아볼 수 있다. (학교 기준으로) 1등은 모든 문제를 해결한 서울대학교의 Cafe Mountain, 2등은 9문제를 패널티 1004분으로 해결한 연세대학교의 Inseop is Korea top, 3등은 9문제를 패널티 1464분으로 해결한 KAIST의 CMD이다. 올해에는 12문제가 출제 되었고, 이 문제들에 대한 풀이를 작성해보려고 한다. A - Fire on Field 문제 $A[0] = 1, A[1] = 1$ 이고, 2 이상의 $i$에 대해, $A[i]$ 를 모든...
-
더 빠른 문제 풀이 코드를 위한 상수 줄이기 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의 개략적인 구조만을 다룹니다. 구조를 이해하셨다면 다음...