cgiosy.dev

어떤 집합에서 결합법칙을 만족하는 이항연산 $+$와 역연산 $-$가 있고, $f(x + y) = f(x) + f(y)$를 만족하는 함수 $f$가 있을 때, $f^n(x)$를 빠르게 계산할 수 있다면 길이 $N$의 문자열 $S$에 대해 $h = \sum_{k=1}^{N}{f^{N-k}(S[k])}$를 롤링 해시로 활용할 수 있다. $f(h) + S[N + 1]$로 뒤에 문자를 추가할 수 있고, $h - f^{N-1}(S[1])$로 앞에서 문자를 삭제할 수 있다. 당연히 중간에서 삭제 및 대체도 가능하지만, 앞뒤 추가 및 삭제에 비해 거의 안 쓰이는 편이다. 예시 위키피디아의 롤링 해시 문서에선 다음 두 가지 다항식 기반 롤링 해시를 소개한다. 다항식 롤링 해시 적당한 상수 $p$, $q$가 있을 때, mo..

처음으로 참가한 대학생 대회다. 팀 구성은 4월 초쯤에 이뤄졌다. 내가 올해에 PS를 열심히 할 것 같지도 않고, 맥레 오렌지밖에 안 되는 평범한 양민 새내기가 빡겜팟을 찾는 건 에바같아서 지인들 채팅방에서 즐겜팟을 모집했다. 글을 올리고 금방 cgiosy, ahgus89, kyo20111 세 명으로 팀을 만들게 됐다. 각각 소개해 보자면, cgiosy: 오렌지 주차시켜둔 퍼플 실력 / 웰노운이랑 이상한 걸 위주로 한다. ahgus89: 찐렌지에 가까운 오렌지 / 수학(특히 정수론)이랑 애드혹을 잘한다. kyo20111: 그냥 레드 / 웰노운이랑 구현을 잘하는 것 같다. 생각보다 꽤 안정적인 팀이 갖춰져서 신기했다. 주때(kyo20111)는 개인대회에선 SCPC 2등 및 코포 레드, 팀대회에선 ICPC ..

지인이 연 백준 대회인데, 홍보를 열심히 하고 다니길래 궁금해서 A만 풀고 스코어보드 구경이나 하려고 했다. 정신을 차리니 ABCFH를 풀고 D를 뇌절하며 눈물을 흘리고 있었다. A. 루나의 게임 세팅 $N$과 $K$가 주어질 때, $1$부터 $N$까지의 수에서 $K$개를 골라 만들 수 있는 바이토닉 순열의 개수를 출력하라. $N$개에서 $K$개 고르는 방법 수는 그냥 조합이고, 고른 다음에 바이토닉하게 $K$개를 재정렬하는 방법의 수가 핵심이었다. 생각해보면 그냥 제일 큰 거 고정하고 양쪽에 큰거부터 추가하는 것과 동치였다. $K - 1$개 왼쪽 / 오른쪽 선택하는 거니까 결국 $2^{K-1}{N \choose K}$이 답이다. 풀이가 쉬워서 대회 끝나고 한 'A는 실5~4쯤 되지 않나?&#39..

현대 CPU는 코어 당 한 사이클에 최대 3 - 4개 정도의 micro intrinsics를 처리 가능하다. 하지만 고도로 최적화된 프로그램이 아닌 한, 상당수가 기껏해야 0.5개 정도를 쓰는 것에 그친다. 여기엔 여러 이유가 있으나, 보통 메모리 레이턴시가 주 원인이다. CPU가 아무리 병렬화, OoO를 위해 노력해도 메모리를 읽어와야 해서 흐름이 끊기거나, 명령어들이 서로 아주 긴밀하게 얽혀 있는 등의 상황에선 성능을 완전히 활용할 수 없는 것이다. 이를 위해 메모리 읽기를 비롯한 각종 연산 사이에 동일 코어에 배정된 다른 스레드를 실행하는 기술이 고안됐고, 이것이 하이퍼스레딩이다. 활성화할 경우 한 코어 위에서 여러 프로그램들이 돌아갈 때나, 멀티스레드 프로그램의 경우 성능이 유의미하게 향상되는 편..

$k$차원 평면에서 점 $N$개, 초직사각형 $Q$개가 주어진다. 단, 각 초직사각형에 대해 원소가 $\infty$ 혹은 $-\infty$로만 이뤄진 점이 하나 존재해야 한다. 주어진 점 집합에 단일 점을 추가하는 어떤 연산 $*$에 대해, 각 초직사각형 내부의 점들을 해당 연산으로 합친 결과를 구해야 한다. 여기서 모스(Mo's) 알고리즘을 사용하면, 특정 연산들을 사용 가능할 때 $O(NQ^{1 - \frac{1}{k}})$ 정도에 문제를 해결할 수 있다. 2차원 모스 알고리즘이 가장 자주 사용되는 상황으로 예를 들어보자. 크기 $N$의 배열 $A$와 $[l, r]$ 구간 쿼리 $Q$개가 주어진다. 그러면 2차원 평면에서 $A$의 $i$번째 원소는 좌표 $(i, i)$에 위치하며 값 $A_i$..

순서 보존 (문자열, 순열 등) 이 경우, 라빈 카프 해싱으로 잘 알려진 $\sum_{i=1}^{n}{c^{n-i} A_i}$를 쓰는 게 일반적이다. 그냥 쓰긴 너무 크니까 보통 적당한 자연수 $m$로 나눈 나머지를 쓰는데, $c$와 $m$이 서로소이며 $A_i$의 최댓값보다 커야 품질이 좋다. $A_i$보다 작으면 서로 다른 $A$가 동일한 해시값을 가질 수 있다. ($\mod m$을 안 붙였을 때 기준) 즉 중복이 발생한다. $c$와 $m$이 서로소가 아니면 $\mod m$ 했을 때 0 나오기 쉽다. 그리고 굳이 이게 아니어도 딱히 좋진 않을 듯 $c$를 $m$의 원시근으로 잡으면 좋긴 한데, 사실 PS 범위에선 그까진 필요없고 $c^0, ..., c^{1,000,000}$에서 중복이 없는 정도면 충..

HTTP Proxy Server Benchmarks h2load를 사용해 리버스 프록시 서버로서의 H2O와 Nginx를 벤치마크 및 비교해 보았다. HTTP/2와 HTTP/3 각각에 대해 테스트하였고, 벤치마크 명령어를 다섯 번 실행하여 시간이 가장 적게 소모된 경우를 뽑았다. Configurations H2O 2022년 1월 8일 기준 최신 커밋을 빌드하였으며, ECDH Curves 관련 PR을 적용했다. h2o.conf send-server-name: OFF access-log: /app/log/h2o-access.log error-log: /app/log/h2o-error.log error-log.emit-request-errors: ON hosts: "localhost": listen: &www_..

인터넷을 확인해보아도 정확한 자료가 없어 직접 측정 후 정리해 보았다. 적절한 폭과 높이는 흔히 알려진 기준을 기반으로, 두 시간정도 모니터를 뚫어지게 쳐다보며 직접 값을 튜닝해본 결과를 썼다. 영문(알파벳 + 특수 문자, 커닝 포함) 글의 글자 당 평균 너비: 산세리프 (Arial, Pretendard, 산돌네오): 0.45em 세리프 (Times New Roman): 0.4em Reuters-21578 데이터를 넣고 손수 측정해본 결과이다. 굵기는 400 기준이며, 700으로 할 시 0.02em 이내의 차이가 발생했다. 한국어(한글 + 영문자 포함) 글의 글자 당 평균 너비: 산세리프 (Pretendard, 산돌네오, 본고딕): 0.7em 뉴스를 위주로 해 임의의 인터넷 글들을 넣어보며 측정했다. 화..