지구이와 CP 이야기

3-1. Alcohol Separation 시간: 2 cycle + 7 cycle (19 cycle) (-2) + 오버헤드를 2 cycle정도 손해봐서 아쉽지만, 너무 어려워서 포기했습니다. + gif 파일이 10MB가 넘어서 dropbox url로 대체했습니다. 3-2. Water Purifier 시간: 7 cycle + 3 cycle (45 cycle) 3-3. Seal Solvent 시간: 8 cycle + 2 cycle (50 cycle) 3-4. Climbing Rope Fiber 시간: 12 cycle + 2 cycle (74 cycle) 3-5. Warming Tonic 시간: 4 cycle + 3 cycle (27 cycle) 3-6. Life-Sensing Potion 시간: 4 cycl..

2-1. Hair Product 시간: 8 cycle + 2 cycle (50 cycle) 2-2. Rocket Propellant 시간: 5 cycle + 3 cycle (33 cycle) 2-3. Mist of Incapacitation 시간: 4 cycle + 2 cycle (26 cycle) 2-4. Explosive Phial 시간: 3 cycle + 5 cycle (23 cycle) (-1) 2-5. Armor Filament 시간: 8 cycle + 2 cycle (50 cycle) (-1) 2-6. Courage Potion 시간: 4 cycle + 2 cycle (26 cycle) 2-7. Surrender Flare 시간: 3 cycle + 6 cycle (24 cycle) (-7) 2..

0. Opus Magnum이라는 게임입니다. 게임은 상점 페이지가 대신 설명해 주는것으로 하고 넘어가겠습니다. 이 게임의 목표는 원소를 적절히 조합해서 목표 생산물을 만드는 생산 공장을 만드는 것입니다. 물론, 그냥 만들면 재미가 없으니까(..?) 최소 시간을 목표로 풀고 있습니다. 인게임에서는 6개를 만드는 데 걸리는 시간을 측정해서 랭킹을 매깁니다. 원소는 2cycle에 하나씩 나오기 때문에 (생산물에 사용되는 원소 개수) * 2cycle보다 빠르게 만들 수 없습니다. 이유는, 잡고 꺼내기만 해도 이미 2cycle이기 때문이죠. 그래서 일반적인 목표는 모든 원소를 2cycle에 하나씩 꺼내 생산물을 만드는 겁니다. 시간은 (개당 소요 시간) + (추가 소요 시간)으로 적었습니다. 만드는 데에 시간이 ..

0. 서론 Competitive Programming(이하 CP)을 공부하는 분들에게 기하는 큰 골칫거리입니다. ICPC나 Codeforces에 무시하지 못할 만큼 출제되면서 동시에 기하에 대한 양질의 정보가 부족한 것이 이유라고 생각하고 있습니다. 그래서 이번 기회에 기하 문제를 편하게 풀기 위한 많은 정보와 팁을 정리하려고 합니다. 이 글을 통해 많은 분들이 기하를 까다롭게 느끼지 않았으면 좋겠습니다. 제가 조사한 기하가 어려운 이유는 다음과 같습니다. 대부분의 문제가 실수 오차에 매우 민감하다. 예외 처리할 것이 매우 많다. 코딩을 깔끔하게 하기 어렵다. 다른 분야와 공유하는 부분이 없어 생소하다. 이 글의 목표는 위의 이유들을 해결하는 것입니다. 제 글을 통해 여러분이 더 이상 기하를 까다롭다고 ..

D-7 PS도 접었고 1인 대회에 나가기에는 구현 실력에 문제가 있어서 대회에 잘 출전하지 않고 있었는데, 몇 안되는 팀대회인 UCPC가 열리길래 dotorya, alex9801으로 팀을 만들었다. 이번 년도 UCPC는 온라인으로 열린 만큼 3대의 컴퓨터를 쓸 수 있었지만, 우리 팀은 (나때매) 컴퓨터 3대를 활용하기 힘든 팀이어서 불안했다. 그래서 alex9801이 팀연습을 하자고 했지만, PS를 너무 많이해서 질려버린 내가 극구 반대했기 때문에 결국 팀연습은 없었다. (ㅈㅅ!!) CafeMountain이 팀명을 여기가월파2020인가요로 지었다고 하길래, 말이 이어지도록 아뇨, 뚱인데요?로 팀명을 짓고 이론치를 하자고 했다. 사실 UCPC에 잘하는 팀이 너무 많아서 2등상은 어렵다고 생각한 게, 대회 ..

https://github.com/zigui-ps/VoronoiDiagram zigui-ps/VoronoiDiagram Fortune's Algorithm. Contribute to zigui-ps/VoronoiDiagram development by creating an account on GitHub. github.com 자세한 내용은 깃헙 readme를 참고해주세요. 제가 나름대로 데이터를 넣어보긴 했습니다만, 그래도 검수가 부족해서 팀노트에 넣기 전에 한번 정도는 검수를 부탁드립니다. (깃헙 watch, star나 fork는 깃헙 저자에게 큰 도움이 됩니다.) 점 100만개가 제 노트북에서 3초쯤 걸리니까 아마 웬만한 문제에서 시간때문에 틀리는 일은 없을 것 같습니다. 다만 200줄이나 되는 코드..

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나 실행 환경 같은 것들은 어떻게 만들어야 하는지 모르겠습니다. 이번 학기가 끝나야 관리가 될 거 같은데, 그건 그때 가서 생각하기로 했습니다.

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를..

0. 서론 실수 자료형을 사용하는 이진탐색은 오차때문에 틀릴 수 있습니다. 또한, 정확한 분수를 구해야 하는 문제의 경우는 실수 자료형을 쓸 수도 없습니다. 이런 경우 사용할 수 있는 방법으로는, 실수 대신 분수로 이진탐색을 하는 것입니다. (단, 분모의 상한이 확실하게 존재해야 합니다. 분모나 분자의 상한을 모른다면 답을 구할 수 없겠죠.) 증명은 정수론 학부과정에 포함되지만, 여기서는 다루지 않고 직관적으로 가능하다는 것으로 넘어가겠습니다. 실무에서는 딱히 중요하지 않을 것 같고, PS로도 자주 나오는 테크닉은 아닙니다. 그리고 코드도 실수 이진탐색보다 훨씬 더 길고 복잡합니다. 하지만 분수로 이진탐색이 된다는 것은 꽤 좋은 도구라고 생각하기 때문에 배우면 언젠가는 도움이 될 것 같습니다. 그리고, ..

0. 문제를 풀 때는 다른 문제로 바꿔서 푸는 경우가 많이 있습니다. 미로 최단거리를 그래프로 바꿔서 bfs로 푸는 것이 그 예시입니다. 하지만 문제를 바꿔서 풀 때는 조심해야 합니다. 문제를 바꾸는 과정에서 정보 손실이 일어날 수 있고, 일부 만족해야 하는 성질이 사라져 못푸는 문제가 되어버릴 수 있습니다. UCPC F 문제로 나온 parentheses recover의 풀이를 설명하면서, N^3 풀이와 N^2 풀이의 모델링에 나타나는 차이를 설명해 볼 것입니다. (스포 방지선) 1. 가능-불가능 여부 확인 문제를 풀기 위해서는 먼저 괄호 문자열 S, T가 주어졌을 때 조건을 만족하는지 알 수 있어야 합니다. (그리고 일반적으로 풀이를 이런 단순한 문제에서 시작하는 것은 매우 좋은 습관입니다.) 이 문제..