cgiosy.dev

https://challenges.reply.com/tamtamy/challenges/category/coding_teen#about 3월 3일에 junseo가 웬 처음 보는 대회를 들고 여기 같이 해보자며 팀하자고 DM이 왔다. 귀찮아서 좀 고민하다가 상금을 봤는데, 1등 5000 유로 / 2등 2000 유로 / 3등 1000 유로씩 준다길래 덥썩 물었다. 온라인 대회에 이 수준이면 상당히 후한 축에 속한다. 대충 보니까 아웃풋 온리에 휴리스틱 대회 같아서 조금 불안했는데, 내가 아는 휴리스틱이라곤 '어떤 알고리즘'밖에 없기 때문이다. 무슨 이상한 가지치기나 애드혹 관찰을 섞은 컨스트럭티브, 플로우 어쩌구로 최적화해야 하는 게 아닌가 싶어 좀 쫄았는데... 다행히 이는 기우였음이 드러났다. 이전 대회들..

함수형 프로그래밍에서 반복문 대신 재귀를 쓸 때, 꼬리재귀 최적화가 없다면 메모리나 속도가 망하기 쉽다. 재귀 깊이 제한이 있다면 함수가 뻥뻥 터지기도 한다. 반복문으로 바꾸면 된다지만 썩 맘에 들지 않는 건 어쩔 수 없다. 함수형을 맛보기 좋은 걸로 알려진 JS에(정확히는 가장 널리 쓰이는 JS 엔진인 V8에) 이런 꼬리재귀 최적화가 없다는 건 상당히 이율배반적인 소리로 들린다. 때문에, 적절한 규격을 가진 재귀함수를 내부적으로 반복문처럼 처리하는 유틸리티 함수를 만들어볼 수 있다. 목표는 T(self => (n, acc = 0) => (n ? self(n - 1, acc + n) : acc))(100000000)을 했을 때 콜스택이 터지지 않고 잘 돌아가도록 T 함수를 만드는 것이다. const T ..

https://github.com/cgiosy/xxh32 JS 최적화 상식 정수 vs. 실수 JS는 기본적으로는 정수와 실수 구분이 없다. 사실상 모든 연산이 64비트 실수형 위에서 돌아간다고 보면 편하다. 그래도 비트 연산을 사용하면 32비트 정수라도 쓸 수 있게끔 되어 있다. 아래에서 두 번째가 첫 번째보다 두 배 가까이 빠르다. const N = 16384; const arr = new Uint32Array(N); for (let i = 0; i < N; i += 1) arr[i] = i; let s = 0; // Case #1 for (let i = 0; i < N; i += 1) s += arr[i] + 1; // Case #2 for (let i = 0; i < N; i = i + 1 | 0)..

처음으로 참가한 대학생 대회이자, 첫 팀 대회이자, 다른 PS러를 자의로(ㅋㅋ) 만난 첫 대회이다. 대회 직후에 바로 후기 써야지 했는데 힘들어서 다음 날로 미루고, 또 미루다가 이제서야 쓴다 ㅎㅎ; 기본적인 팀 설명 등은 지난 예선 후기에 작성했기 때문에 생략한다. 팀원인 주때의 후기도 함께 보면 좋을 듯. 팀노트 본선 대회를 하루 남겨둔 저녁, 위기감을 느낀 우리는 어떻게든 팀노트를 만들기 시작했다. 코드를 전부 우리가 다 짰으면 좋았겠지만, 팀노트는 한 페이지도 완성 안 돼있고 대회가 코앞인 상황에 그럴 시간은 없었다. 일단 예전에 짜둔 내 코드 30%, 주때의 작년 팀인 Longest path to WF의 팀노트, kactl에서 코드를 열심히 수혈받아왔다. 특히 출제자 목록을 보고 플로우는 꼭 넣..

아래에서 $N$은 테이블에 저장된 키 개수, $M$은 테이블 크기를 의미한다. $N$개의 키에 대한 해시값이 모두 $M$ 미만이고 distinct하다면, 즉 해시가 Perfect Hash Function이면 단순히 크기 $M$의 배열 각각에 키에 대한 값을 저장하면 된다. Perfect Hash Function을 사용하는 해시 테이블은 보통 FKS 해싱 기반인데, 이에 대해선 여기서 설명하지 않겠다. 그보단 대체로 xxHash나 wyhash처럼 매우 빠르며 충분히 랜덤함을 보장하는 해시 함수를 쓰게 된다. 문자열의 특정 부분만 뽑아 쓰는 해시도 있긴 한데, 이 글에선 해시 함수가 서로 다른 키에 대해 완전히 랜덤한 출력을 보장함을 가정한다. 생일 문제에 의해, $N = \sqrt{M}$ 정도만 돼도 테이..

어떤 집합에서 결합법칙을 만족하는 이항연산 $+$와 역연산 $-$가 있고, $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}$이 답이다. 풀이가 쉬워서 대회 끝나고 한 &#39;A는 실5~4쯤 되지 않나?&#39..