시애틀 시의회, 식료품 감시 가격 책정 금지안 통과
시애틀 시의회가 개인 데이터를 이용해 식료품과 필수품 가격을 달리 책정하는 행위를 금지하는 법안을 통과시켰습니다. 시장 서명을 앞둔 이 법안은 소비자 프로파일링을 제한하고 할인 조건의 투명성을 높이지만, 로열티 프로그램 같은 할인은 허용합니다.
최신 글
1,000억 개를 12KB로 세는 방법 — HyperLogLog의 원리
HashSet으로 유니크 방문자를 정확히 세면 메모리가 선형으로 늘어나 1,000억 건 규모에서는 사실상 불가능합니다. HyperLogLog는 해시의 선행 0비트 연속 길이를 수천 개 버킷에서 관찰해 조화평균으로 추정함으로써, 약 0.81%의 고정된 오차 안에서 단 수 KB 메모리로 카디널리티를 구합니다. Redis의 PFADD·PFCOUNT·PFMERGE와 BigQuery·Presto·Spark의 근사 집계 함수가 모두 이 알고리즘을 사용합니다.
Factorio의 난수 생성기 리버싱하기 — LFSR 선형성을 이용한 게임 내 RNG 예측
Factorio: Space Age의 품질(quality) 시스템은 아이템 제작 시 무작위로 높은 등급을 부여하는데, 저자는 이 '무작위'가 실은 결정론적 PRNG임을 밝혀내고 taus88 생성기의 내부 상태를 역산해 미래 결과를 예측했습니다. Ghidra로 바이너리를 분석해 사용 알고리즘을 확인하고, LFSR의 선형성을 이용해 출력 3개만으로 내부 상태를 복원한 뒤 게임 내 회로 네트워크로 예측기를 구현했습니다. 단, Factorio 2.1에서 RNG 사용 방식이 바뀌어 게임 내 구현은 2.0에서만 동작합니다.
팩토리얼은 얼마나 클까 — 계산기 없이 자릿수를 추정하는 수학
52!처럼 일상 계산기 범위를 넘는 팩토리얼의 자릿수를 암산으로 꽤 정확하게 추정하는 방법을 소개하는 수학 에세이입니다. 간단한 근사식 n·log10(n/e)에서 출발해, 그 뒤에 있는 감마 함수(Gamma function)와 라플라스 방법(Laplace's method)을 통한 스털링 근사(Stirling's approximation) 유도 과정까지 차근차근 설명합니다.
국기를 11비트로 압축하기 — 허프만 코딩으로 만든 초소형 국기 포맷
개발자 vantezzen이 전 세계 국기를 '몇 비트로 표현할 수 있을까'라는 질문에서 출발해 커스텀 바이너리 포맷을 설계한 프로젝트입니다. 가로세로 비율·색상 팔레트·레이어를 각각 허프만(Huffman) 트리로 부호화해 평균 76비트, 중앙값 55비트로 128개국 국기를 인코딩했고, 가장 짧은 인도네시아 국기는 단 8비트에 불과합니다.
4x4 스도쿠는 단 12개뿐이다 — 최소 부분집합을 찾는 멋진 트릭과 함께
4x4 스도쿠의 해는 전부 288개지만, 숫자 치환을 같은 것으로 치면 구조적으로 다른 해는 12개뿐입니다. 저자는 브루트포스 Python 코드로 이를 직접 세고, 유일해를 갖는 최소 퍼즐 85,632개를 열거하면서 비트마스크로 부분집합 여부를 효율적으로 검사하는 트릭을 소개합니다.