언어와 프레임워크, SDK와 개발 방식·도구의 변화를 다룹니다.
David G. Andersen은 Rust로 Scrabble 사전 178,690개 항목의 아나그램 인덱스를 만들고, 자신의 MacBook Pro M1에서 최종 구현의 구축 시간을 1.96ms(항목당 10.9ns)로 측정했습니다. 글자별 소수를 곱하는 64비트 키는 해당 사전에서 오버플로가 나지 않도록 배정표를 조정한 결과입니다. 중간 구현부터 실제 아나그램 그룹만 반환해 초기 방식과 출력 범위가 달라졌습니다.
Antti Laaksonen의 무료 알고리즘 학습서로, 시간 복잡도와 자료구조부터 그래프·문자열·기하 알고리즘까지 경쟁 프로그래밍 주제를 폭넓게 다룹니다. C++11 예제와 단계별 풀이를 통해 알고리즘을 고르고 구현하는 과정을 익힐 수 있습니다.
역연산이 없는 집계도 두 스택으로 슬라이딩 윈도에서 유지하는 알고리즘을 소개합니다. 결합 연산이 결합 법칙을 만족하면 집계 조회는 O(1), 삽입·삭제는 분할 상환 O(1)이며 메모리는 O(w)입니다. 윈도 밖 값이 부동소수점 오차나 NaN을 계속 전파하지 않는 장점도 설명합니다.
Aho-Corasick 알고리즘은 여러 문자열을 Trie에 저장하고, 실패 시 이동할 접미사 링크와 매칭 결과를 모으는 출력 링크를 구성해 한 번의 입력 순회로 문자열을 찾습니다. 글은 링크를 계산하는 BFS 절차와 이를 결정적 유한 오토마톤으로 바꾸는 방법을 설명합니다.
Forisek와 Jancina가 제안한 결정론적 소수 판정법은 32비트 정수에서 소수 2, 3, 5, 7로 나누어 확인한 뒤 해시로 밑을 고르고 강한 probable-prime 검사를 수행합니다. 밑을 담은 조회 테이블은 512바이트만 차지하며, 글에는 C 구현이 실려 있습니다.
SVG 경로를 복소수 좌표로 샘플링한 뒤 이산 푸리에 변환(DFT)으로 주파수별 계수를 구하면, 회전하는 원들을 이어 원래 윤곽을 그릴 수 있습니다. 글은 복소수와 내적부터 DFT 구현까지 설명하며, 주파수를 더할수록 라마 그림의 세부가 살아나는 과정을 보여줍니다.
HashSet으로 유니크 방문자를 정확히 세면 메모리가 선형으로 늘어나 1,000억 건 규모에서는 사실상 불가능합니다. HyperLogLog는 해시의 선행 0비트 연속 길이를 수천 개 버킷에서 관찰해 조화평균으로 추정함으로써, 약 0.81%의 고정된 오차 안에서 단 수 KB 메모리로 카디널리티를 구합니다. Redis의 PFADD·PFCOUNT·PFMERGE와 BigQuery·Presto·Spark의 근사 집계 함수가 모두 이 알고리즘을 사용합니다.
Factorio: Space Age의 품질(quality) 시스템은 아이템 제작 시 무작위로 높은 등급을 부여하는데, 저자는 이 '무작위'가 실은 결정론적 PRNG임을 밝혀내고 taus88 생성기의 내부 상태를 역산해 미래 결과를 예측했습니다. Ghidra로 바이너리를 분석해 사용 알고리즘을 확인하고, LFSR의 선형성을 이용해 출력 3개만으로 내부 상태를 복원한 뒤 게임 내 회로 네트워크로 예측기를 구현했습니다. 단, Factorio 2.1에서 RNG 사용 방식이 바뀌어 게임 내 구현은 2.0에서만 동작합니다.
개발자 vantezzen이 전 세계 국기를 '몇 비트로 표현할 수 있을까'라는 질문에서 출발해 커스텀 바이너리 포맷을 설계한 프로젝트입니다. 가로세로 비율·색상 팔레트·레이어를 각각 허프만(Huffman) 트리로 부호화해 평균 76비트, 중앙값 55비트로 128개국 국기를 인코딩했고, 가장 짧은 인도네시아 국기는 단 8비트에 불과합니다.
4x4 스도쿠의 해는 전부 288개지만, 숫자 치환을 같은 것으로 치면 구조적으로 다른 해는 12개뿐입니다. 저자는 브루트포스 Python 코드로 이를 직접 세고, 유일해를 갖는 최소 퍼즐 85,632개를 열거하면서 비트마스크로 부분집합 여부를 효율적으로 검사하는 트릭을 소개합니다.