0. 저번 글에서 코드 공개를 대충 한 것이 마음에 걸려서, 하나로 정리해서 오픈소스로 만들었습니다. https://github.com/zigui-ps/githashjoke zigui-ps/githashjoke Contribute to zigui-ps/githashjoke development by creating an account on GitHub. github.com 다만, 제가 오픈소스를 관리해 본 적이 단 한번도 없어서 README나 실행 환경 같은 것들은 어떻게 만들어야 하는지 모르겠습니다. 이번 학기가 끝나야 관리가 될 거 같은데, 그건 그때 가서 생각하기로 했습니다.
GPU와 kudeki-chain
0. 18년 2학기에 GPU 프로그래밍을 배워서, 이참에 kudeki-chain도 풀어봤습니다. GTX 1060으로, 약 16시간 정도 돌려서 풀었습니다. 최적화를 덜 했기 때문에 더 빨라질 여지가 있긴 합니다. sha1을 GPU로 옮기는 것이 꽤나 귀찮았는데, 코딩을 오랫만에 해서 그런지 실수가 꽤 많아 오래 걸렸던 것 같습니다. 제 개같은 틀린 코드를 디버깅해준 cubelover에게 감사의 말을 전하며 시작하겠습니다. 1. kudeki-chain 문제를 한 줄로 요약하면 다음과 같습니다. "sha1 해시값의 앞 n자리가 0이 되는 (커밋)메세지를 찾아라." n은 푼 사람이 생길수록 1씩 늘어나서, 제가 문제를 풀 때는 n이 11과 12였습니다. (현재 n이 12인 경우까지 해결하였기 때문에 n=12를..
분수 이진탐색과 Stern–Brocot tree
0. 서론 실수 자료형을 사용하는 이진탐색은 오차때문에 틀릴 수 있습니다. 또한, 정확한 분수를 구해야 하는 문제의 경우는 실수 자료형을 쓸 수도 없습니다. 이런 경우 사용할 수 있는 방법으로는, 실수 대신 분수로 이진탐색을 하는 것입니다. (단, 분모의 상한이 확실하게 존재해야 합니다. 분모나 분자의 상한을 모른다면 답을 구할 수 없겠죠.) 증명은 정수론 학부과정에 포함되지만, 여기서는 다루지 않고 직관적으로 가능하다는 것으로 넘어가겠습니다. 실무에서는 딱히 중요하지 않을 것 같고, PS로도 자주 나오는 테크닉은 아닙니다. 그리고 코드도 실수 이진탐색보다 훨씬 더 길고 복잡합니다. 하지만 분수로 이진탐색이 된다는 것은 꽤 좋은 도구라고 생각하기 때문에 배우면 언젠가는 도움이 될 것 같습니다. 그리고, ..