링크: 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..

https://www.acmicpc.net/problem/11012 문제 2차원 평면에서 점들의 위치가 주어지고, [left, right]×[bottom, top] 으로 그려지는 사각형 내에 있는 점의 개수를 쿼리마다 출력하는 문제이다. 이 문제는 PST(Persistent Segment Tree)로 해결할 수 있다. PST의 이해를 위해서는 Segment Tree를 먼저 알아야한다. 이 글에서는 자세한 설명은 생략하고, 도움이 될 만한 글로 대체한다. 사실 같은 내용을 이 문제에 대해서만 다시 정리하는 것이라 봐도 무방하다. 혼동이 있을 수 있지만, 이 글에서는(필자는) 세로/수직 방향을 \(y\)축으로 가로/수평 방향을 \(x\)축으로 한다. 즉, \((0,~0)\)은 왼쪽 아래를 의미한다. y축을 ..

오랜만의 코딩으로 풀어보기 시리즈이다. 오늘은 아주 간단하고 쉬운 문제이다. 문제 1부터 9까지의 숫자를 한번씩만 사용해서, 수식을 성립시키는 문제이다. 이런 유형의 문제는 "복면산 문제"라고 불리는 수학 퍼즐의 한 종류이다. 여담이지만, 개인적으로 좋아하는 문제이다. 이와 관련한 알고리즘 문제를 출제한 적도 있다. 완전 탐색류 알고리즘을 연습하기 좋은 문제라고 생각한다. 아래 링크에서 풀어볼 수 있다. BOJ 15811 - 복면산?! (https://www.acmicpc.net/problem/15811) 위 문제는 9개의 숫자와 9개의 알파벳이니 더 쉽다. 1부터 9까지 A부터 I까지 모두 대응시켜보며 만들어지는 세 값이 일치하는 지 확인하면 된다. 즉, 모든 순열을 확인하면 된다. 경우의 수는 \(9..