지구이와 CP 이야기

먼저 디스코드 초대 링크입니다. Competitive Programming 커뮤니티에는 누구나 자유롭게 질문할 수 있고, 뛰어난 실력을 가진 분들이 상시 접속해 있어 좋은 퀄리티의 답변을 하는 커뮤니티가 있었습니다. BOJ Slack의 #qna 채널이 그 커뮤니티입니다. CP 커뮤니티에 기여를 했던 (혹은 했다고 착각하는?) 저로서는, 그런 커뮤니티가 활발하다는 것에 만족하고 있었습니다. 하지만 꽤 오래 전 불의의 사고로 BOJ Slack이 사라지게 되면서 자유롭게 질문할 수 있는 공간이 없어지게 되었습니다. 그리고 현재 실력 있는 CP 유저들이 활동하고 있는 오픈 커뮤니티는 거의 없고, 접근성도 매우 떨어집니다. CP 생태계가 이런 모습이길 바라지는 않기 때문에, Discord에서 #qna와 비슷한 일..

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

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

-1. 잡담 https://www.acmicpc.net/blog/view/45 1년 반 전, 질문게시판 답변률이 20%가 안되던 때에 쓰여진 글입니다. 여기서 각 문장의 의도가 무엇인지 하나씩 적어보겠습니다. 최근에는 대부분의 질문글이 가이드라인을 잘 지켜서 답변하기가 매우 수월합니다. 이런 점은 좋지만, 가이드라인에 맞지 않는 질문이 무시당하는 느낌이 들기도 합니다. PS를 어느정도 한 사람이 보면 가이드라인은 당연한 것들이지만, PS를 갓 시작한 사람들에게는 당연하지 않을 수 있다고 생각합니다. 제가 질문에 답변할 때는, 질문 내용 뿐만이 아니라, 코드와 질문자의 태도 전체를 확인합니다. 단순히 "시간초과가 납니다"라는 내용이 있고, 시간복잡도에 대해 모르는 것 같다면, 시간복잡도에 대해 공부해보라는..

-1. PS는 Problem Solving의 약자로, 프로그래밍으로 문제를 푸는 분야를 말합니다. 0. 서론 (+잡담) 드디어 PS를 접고 PS4를 열심히 하고 있습니다. 최근에는 플스4로 아틀리에 신기시리즈를 열심히 하고 있는데, 취향에 맞아서 재밌게 즐기고 있습니다. 지금까지 문제 풀면서 힘든적이 엄청 많았던 거 같은데, 요즘은 문제의 N도 안보는 생활을 하고 있어서 매우 만족하고 있습니다. 이제 재밌게 대회를 하기에는 너무 멀리 왔다고 생각합니다. 사실 저는 대회에 참가하는 것을 즐기는 성격이 아닙니다. 성격상 대회에서 못하면 힘들고, 잘하면 딱히 좋아하지 않아서, 결국 힘들기만 합니다. 그래도 작년 1년 6개월동안은 대회는 싫은데 대회를 나가야해서, 인지부조화에 시달리면서 열심히 생각한 것들이 있..

0. 서론 + 잡담 제가 처음으로 프로그래밍을 시작한 것은 08년도 1월입니다. 10년째 프로그래밍을 했고, 고비도 엄청 많았지만, (자세한 내용은 나중에 말해보기로 하고) 드디어 이 대회를 그만할 수 있게 되어 영광입니다. 이제 선수생활은 그만하기로 했고, 더이상 병신같은 새로운 내용을 공부하지 않고, 대회는 하고싶을 때 칠 것 같습니다. 이제 진짜 하고싶은 것들에 매진할 생각입니다. 그 전에, 머리를 비우기 위해 ICPC를 하면서 생각했던 것들을 몇 가지 쓰고 있습니다. 잠깐 변명을 하자면, ICPC World Final을 이끌고 있는 사람들의 생각이 저희팀과는 많이 달랐고, 때문에 출제진에게 뒤통수를 얻어맞은 것이라고 생각합니다. 저희가 잘못했다고 생각하지 않습니다. ICPC World Final에..

MolaMola 팀 팀노트입니다. (링크) (18년 10월 3일 수정. docx 파일로 복사-붙여넣기가 가능합니다.) 5년 전 kcm님 팀노트에서 시작되어 조금씩 수정하던 것 같습니다. 감사합니다. 0. Algorithm Checklist 풀이 생각할 때 도움이 되라고 쓴 겁니다. 안 풀릴 때 한번씩 읽으려고 했는데, 아직 도움이 된 적은 없네요. 1. JavaIO, Set k-th element 지금보니 목차가 잘못되어있네요.. BigInteger 사용 용도와 std::set에서 k번째 원소 찾는 방법을 넣어둔 것입니다.Java는 그렇다고 하고, std::set은 쓸 때 실행시간에 주의하시기 바랍니다. 저번 코포에서 틀린 적이 한 번 있어서.. 2. Splay tree, link-cut tree Spl..