링크: 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로 설정했다. 이를 자세히 각 단계별로 쪼개면 이렇다. 준비 - 나눠 담을 크기를 계산 분리 - 큰 세그먼트 단위로 나누어 쪼개어 담는다. 정렬 - 쪼개진 각 파일을 ..