오늘은 기존에 개발했던 게임의 로그 제공을 업데이트하면서 있었던 일을 정리하고자 한다. 배경 https://www.joonas.io/buffalo-chess/ Buffalo Chess Try to keep your village from the herd of rampaging buffalo www.joonas.io 기존에 만든 버팔로 체스는 Replay와 Share Replay 기능을 제공한다. 턴제 게임으로, 각 턴마다 어떤 타일이 움직였는지와 그 상태를 로그로 기록하고 있다. 그리고 replay 기능에서 이를 다시 읽어서 그대로 시뮬레이션한다. 문제는 Share 기능인데, 서버가 없어서 로그를 URL 파라미터로 아래처럼 직접 전달하고 있었다. https://www.joonas.io/buffalo-ch..

링크: https://www.acmicpc.net/problem/13976 문제 2133번 문제와 같이 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이지만, N의 범위가 \(10^{18}\) 이다. 풀이 이전에 작성한 2133번 문제의 2번째 풀이 방법과 같지만 그것을 빠르게 계산해야한다. 피보나치 수를 빠르게 구하는 방법과 마찬가지로, 행렬을 이용한 거듭 제곱 트릭을 사용하면 된다. 수열의 값은 같으므로, 편의상 OEIS A001835 수열 \( f(n) = 4 \cdot f(n-1) - f(n-2) \) 을 사용하겠다. 이것을 행렬로 나타내면 아래와 같다. $$\begin{eqnarray} \left( \begin{array}{ccc} f_{n} \\ f_{n-1}..

링크: https://www.acmicpc.net/problem/2133 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 풀이 3×N 벽을 채우는 경우를 \(f(n)\), 한 칸이 빈 3×N 벽을 채우는 경우를 \(g(n)\) 라고 하자. 왼쪽부터 2×1 또는 1×2 크기의 타일을 하나씩 채워보면서 가능한 경우를 살펴본다. \(g(0)\)와 \(g(2)\)는 타일을 채울 방법이 없으므로 \(g(0) = g(2) = 0\) 이다. 이것을 식으로 나타내면 이렇다. $$f(n) = \begin{cases} 0 & \text{if $n$ < 2} \\ 2g(n-1) + f(n-2) \end{cases}$$ $$g(n) = \begin{cases} 1 & \text{i..

403 에러 원인에는 다양한 것이 있겠지만, 내 경우에는 구글 시크릿 모드가 원인이었다. 시크릿 모드에서 쿠키를 차단해서 생기는 오류였다. "크롬 브라우저 설정 > 쿠키 및 기타 사이트 데이터 > 모든 쿠키 허용" 에서 설정 가능하다. 도움이 된 글: https://stackoverflow.com/questions/64218755/getting-error-403-in-google-colab-with-tensorboard-with-firefox 여기에 다른 브라우저 (FIreFox 등) 의 해결법도 나와있다.

파일 내용이 10GB가 되는 것은 어떻게 정렬할까? 메모리에 올릴 수 있는 크기가 한정되어 있기 때문에, 10GB 짜리의 큰 파일을 한번에 읽어서 quick sort 같은 인메모리(in-memory) 정렬을 할 수 없다. Linux/Mac에는 sort 라는 명령어가 있고, Windows에서는 git bash를 깔면 사용할 수 있다. 이미 있는 커맨드인지 모르고 python으로 직접 구현했다. 더보기 과정 메모리에 올릴 수 있는 만큼만 쪼개어서 올린 후, 각각을 정렬하고 다시 합친다. 여기서 "메모리에 올릴 수 있는 만큼"은 적당히 128MB로 설정했다. 이를 자세히 각 단계별로 쪼개면 이렇다. 준비 - 나눠 담을 크기를 계산 분리 - 큰 세그먼트 단위로 나누어 쪼개어 담는다. 정렬 - 쪼개진 각 파일을 ..

백준 온라인 저지(https://www.acmicpc.net) 사이트의 기능을 보완/확장하는 목적으로 BOJ-Extended를 만들었다. BOJ Extended 백준 온라인 저지(BOJ)를 확장된 기능과 함께 사용해보세요. chrome.google.com 처음에는 (원래는 있었지만 잠시 사라진) 프로필에서 문제 제목이 보이도록 하고 싶어서 시작했는데, 이거 하나만을 위한 확장 프로그램은 뭔가 아까워서 기능을 이것저것 붙이다보니 현재의 상태가 되었다. 뭐가 있을까 고민하다가 다크모드(어두운 테마)를 추가해봤고, 그 외에도 문제 타이머, 넓게 보기, 채점 현황과 게시판에서도 문제 제목으로 바로 보기, 채점 결과 텍스트 바꾸기 등 계속 추가하고 있다. 언제 추가될 지 모르겠지만, 업데이트 예정으로는 (미리 저..

문제 소인수가 2 또는 3 또는 5로만 이루어진 수를 "못생긴 수"라고 했을 때, N번째 못생긴 수를 출력하는 문제이다. New Zealand 1990 Division I에 등장했던 문제로, 여러 저지에서 풀어볼 수 있다. UVa 136 - Ugly Numbers POJ 1338 - Ugly Numbers 정올 1318 - 못생긴 수 풀이 빨간색을 현재까지 살펴본 수, 파란색을 앞으로 살펴볼 수라고 했을 때 그림을 위와 같다. 파란색으로 색칠된 수 중에서 가장 작은 수부터 순서대로 살피면, 그 순서대로 N번째 못생긴 수가 결정된다. 이는 다익스트라 알고리즘에서 그림이 어떻게 그려지는 지를 떠올리면 이해가 쉽다. 수의 중복을 제거하기 위해서 이전에 5를 곱해서 만들어진 수에는 2나 3을 곱하지 않았다. 2..

Linux 환경을 세팅하기 귀찮아서 Windows 10에서 Docker를 설치하고 예전에 저장한 이미지로 컨테이너를 바로 띄우려했다. https://hub.docker.com/editions/community/docker-ce-desktop-windows/ 에서 도커를 설치하고 재부팅하고, CMD를 관리자 권한으로 실행했는데 아래와 같은 오류가 났다. C:\Windows\system32>docker ps Error response from daemon: open \\.\pipe\docker_engine_linux: The system cannot find the file specified. 다음처럼 해결할 수 있었다. (https://github.com/docker/for-win/issues/1825#i..